12.2 Elliptic curves over finite fields

Elliptic curves over finite fields are fascinating mathematical objects with powerful applications in cryptography. They form finite abelian groups, allowing for efficient computation and secure key exchange protocols.

These curves play a crucial role in modern cryptography, offering smaller key sizes and faster operations than traditional methods. Understanding their properties and algorithms is essential for designing secure systems in our digital world.

Elliptic Curves and Group Structure

Definition and Properties

Top images from around the web for Definition and Properties

• 

  A simple Elliptic Curve View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Koblitz Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Annotated curve E with points P, Q, R, R' and line L labeled. View original

  Is this image relevant?

• 

  A simple Elliptic Curve View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Koblitz Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Properties

• 

  A simple Elliptic Curve View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Koblitz Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Annotated curve E with points P, Q, R, R' and line L labeled. View original

  Is this image relevant?

• 

  A simple Elliptic Curve View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Koblitz Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

• An elliptic curve over a finite field $\mathbb{F}_q$ is a nonsingular projective algebraic curve of genus 1 with a specified base point
• The set of $\mathbb{F}_q$-rational points on an elliptic curve, together with a special point called the "point at infinity," forms an abelian group under a geometrically defined addition operation
• The group law on an elliptic curve can be described by the chord-and-tangent process three collinear points sum to the identity (point at infinity)
• Elliptic curves over finite fields have a finite number of points, and their group structure is always either cyclic or the product of two cyclic groups (e.g., $\mathbb{Z}/n\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$)

Torsion Points and Finite Order

• The group of points on an elliptic curve over a finite field is a torsion group, meaning every point has finite order
  • A point $P$ on an elliptic curve has order $n$ if $nP = \mathcal{O}$ (point at infinity) and $n$ is the smallest positive integer with this property
• The order of a point divides the total number of points on the elliptic curve
• Lagrange's theorem states that for any finite group $G$ and subgroup $H$, the order of $H$ divides the order of $G$
• The number of points of order dividing $n$ on an elliptic curve is bounded by Hasse's theorem (a consequence of the Hasse-Weil bound)

Point Counting on Elliptic Curves

Exhaustive Search and Schoof's Algorithm

• The number of points on an elliptic curve over a finite field $\mathbb{F}_q$, denoted $\#E(\mathbb{F}_q)$, can be computed using various methods
• Exhaustive search for small finite fields, one can simply count the number of points satisfying the elliptic curve equation, including the point at infinity
• Schoof's algorithm a polynomial-time algorithm that computes $\#E(\mathbb{F}_q)$ by determining the trace of the Frobenius endomorphism modulo certain small primes
  • The Frobenius endomorphism $\phi$ maps a point $(x, y)$ to $(x^q, y^q)$
  • The trace of $\phi$ is related to the number of points by $\#E(\mathbb{F}_q) = q + 1 - \text{tr}(\phi)$

Schoof-Elkies-Atkin (SEA) Algorithm

• Schoof-Elkies-Atkin (SEA) algorithm an improvement of Schoof's algorithm that uses additional techniques, such as isogenies and modular polynomials, to speed up the computation
  • Elkies primes and Atkin primes are used to split the computation into smaller subproblems
  • Isogenies (maps between elliptic curves preserving the group structure) and modular polynomials are used to efficiently compute the trace of Frobenius modulo these primes
• SEA is the most efficient known algorithm for point counting on general elliptic curves over finite fields
• The number of points on an elliptic curve over $\mathbb{F}_q$ is related to the trace of the Frobenius endomorphism $t$ by the equation $\#E(\mathbb{F}_q) = q + 1 - t$

Hasse-Weil Bound and Implications

Bounding the Number of Points

• The Hasse-Weil bound limits the number of points on an elliptic curve over a finite field $\mathbb{F}_q$ $|\#E(\mathbb{F}_q) - (q + 1)| \leq 2\sqrt{q}$
• The bound implies that the number of points on an elliptic curve over $\mathbb{F}_q$ is roughly $q + 1$, with an error term of at most $2\sqrt{q}$
  • For example, an elliptic curve over $\mathbb{F}_{101}$ has between 81 and 121 points (inclusive)
• Elliptic curves with the maximum or minimum number of points allowed by the Hasse-Weil bound are called maximal or minimal curves, respectively

Theoretical Foundations and Consequences

• The Hasse-Weil bound is a consequence of the Riemann hypothesis for the zeta function of the function field of the elliptic curve
  • The zeta function encodes information about the number of points on the elliptic curve over various finite field extensions
• The Sato-Tate conjecture, now a theorem, describes the distribution of the error term in the Hasse-Weil bound as $q$ varies over prime fields
  • The normalized error terms are equidistributed with respect to the Sato-Tate measure (related to the Haar measure on SU(2))
• The Hasse-Weil bound has important applications in elliptic curve cryptography, as it ensures that the ECDLP is well-defined and computationally hard

Elliptic Curves in Applications

Elliptic Curve Cryptography (ECC)

• Elliptic curve cryptography (ECC) is based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP)
• The ECDLP states that given points $P$ and $Q$ on an elliptic curve, it is computationally infeasible to find an integer $n$ such that $Q = nP$, if such an $n$ exists
• ECC requires smaller key sizes compared to other public-key cryptosystems like RSA for similar security levels, making it more efficient in terms of computation and storage (e.g., 256-bit ECC key vs. 3072-bit RSA key for 128-bit security)

Key Agreement and Digital Signatures

• Elliptic curve Diffie-Hellman (ECDH) is a key agreement protocol that allows two parties to establish a shared secret over an insecure channel using the properties of elliptic curves
  • Alice and Bob agree on an elliptic curve $E$ and a base point $P$. They choose secret integers $a$ and $b$, compute $aP$ and $bP$, and exchange these values. The shared secret is $abP = (ab)P$
• Elliptic curve digital signature algorithm (ECDSA) is a widely used digital signature scheme based on ECC, employed in various cryptographic protocols and standards (e.g., Bitcoin, TLS, SSH)
  • ECDSA signatures consist of two components $(r, s)$ computed using the signer's private key, the message hash, and a random nonce. Verification involves checking an equation using the signer's public key

Error-Correcting Codes and Post-Quantum Cryptography

• Elliptic curves are used in the construction of some error-correcting codes, such as Goppa codes, which have applications in post-quantum cryptography
  • Goppa codes are a class of linear codes defined using algebraic curves, including elliptic curves
  • McEliece cryptosystem is a post-quantum public-key encryption scheme based on the hardness of decoding random linear codes, often instantiated with Goppa codes
• Supersingular isogeny Diffie-Hellman (SIDH) is a post-quantum key agreement protocol based on isogenies between supersingular elliptic curves
  • SIDH is believed to be secure against quantum computers, as it relies on the hardness of finding isogenies between supersingular elliptic curves, for which no efficient quantum algorithm is known