🔢Elliptic Curves Unit 2 – Elliptic Curves in Finite Fields

Key Concepts and Definitions

• Elliptic curves are cubic equations of the form $y^2 = x^3 + ax + b$ where $a$ and $b$ are constants and the discriminant $\Delta = 4a^3 + 27b^2 \neq 0$
• Finite fields, denoted $\mathbb{F}_q$, consist of a finite set of elements with well-defined addition and multiplication operations
  • The order of a finite field is the number of elements it contains, always a prime power $q = p^n$ for some prime $p$ and positive integer $n$
• Elliptic curves over finite fields are the set of points $(x, y)$ satisfying the elliptic curve equation, along with a special point called the "point at infinity" denoted $\mathcal{O}$
• The group law defines addition of points on an elliptic curve, giving the set of points an abelian group structure
• Elliptic Curve Discrete Logarithm Problem (ECDLP) states that given points $P$ and $Q$ on an elliptic curve, it is computationally infeasible to find an integer $k$ such that $Q = kP$
• 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
• Elliptic Curve Digital Signature Algorithm (ECDSA) is a widely used digital signature scheme based on the ECDLP

Historical Context and Applications

• Elliptic curves have been studied in mathematics for centuries, with early work done by Diophantus (3rd century AD) and Fermat (17th century)
• In the 1980s, elliptic curves were proposed for use in cryptography independently by Neal Koblitz and Victor Miller
  • Elliptic curve cryptography offers the same level of security as other systems (RSA) with smaller key sizes, leading to more efficient implementations
• Elliptic curves over finite fields have applications in
  • Cryptography (ECDH key exchange, ECDSA digital signatures)
  • Factoring integers
  • Primality testing (Goldwasser-Kilian algorithm)
• In the 1990s and 2000s, ECC became widely standardized and adopted (NIST, ANSI, IEEE, SECG)
• Elliptic curves are used in modern cryptographic protocols like Transport Layer Security (TLS) and Bitcoin's secp256k1 curve

Finite Fields Fundamentals

• Finite fields are fields with a finite number of elements, satisfying the field axioms (associativity, commutativity, distributivity, identity, inverses)
• The order of a finite field is always a prime power $q = p^n$
  • For $n=1$, the finite field $\mathbb{F}_p$ is the set of integers modulo $p$ with addition and multiplication performed modulo $p$
  • For $n>1$, the finite field $\mathbb{F}_{p^n}$ can be constructed as a polynomial ring modulo an irreducible polynomial of degree $n$ over $\mathbb{F}_p$
• Finite fields are unique up to isomorphism for a given order $q$
• Every element in a finite field has a multiplicative inverse, except for the zero element
• The multiplicative group of a finite field is cyclic, generated by a primitive element
• Finite fields have numerous applications in coding theory, cryptography, and combinatorics

Elliptic Curve Equations and Properties

• An elliptic curve over a field $K$ is a smooth, projective, algebraic curve of genus one with a specified base point
• The Weierstrass equation for an elliptic curve is $y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$ with $a_i \in K$
  • The simplified Weierstrass equation over a finite field of characteristic $\neq 2, 3$ is $y^2 = x^3 + ax + b$
• The discriminant $\Delta = -16(4a^3 + 27b^2)$ of an elliptic curve must be nonzero for the curve to be smooth
• The j-invariant $j(E) = 1728 \frac{4a^3}{4a^3 + 27b^2}$ characterizes elliptic curves up to isomorphism over an algebraically closed field
• The number of points on an elliptic curve over a finite field $\mathbb{F}_q$, denoted $\#E(\mathbb{F}_q)$, satisfies Hasse's theorem $|\#E(\mathbb{F}_q) - (q+1)| \leq 2\sqrt{q}$
• Elliptic curves can be classified by their endomorphism ring over the complex numbers (ordinary, supersingular)

Group Structure on Elliptic Curves

• The set of points on an elliptic curve forms an abelian group under the addition law
  • The identity element is the point at infinity $\mathcal{O}$
  • The inverse of a point $P = (x, y)$ is the point $-P = (x, -y)$
• The addition law for two points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ on an elliptic curve is defined as
  • If $P = \mathcal{O}$, then $P + Q = Q$
  • If $Q = \mathcal{O}$, then $P + Q = P$
  • If $Q = -P$, then $P + Q = \mathcal{O}$
  • Otherwise, $P + Q = (x_3, y_3)$ where
    • $x_3 = \lambda^2 - x_1 - x_2$
    • $y_3 = \lambda(x_1 - x_3) - y_1$
    • $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ if $P \neq Q$, or $\lambda = \frac{3x_1^2 + a}{2y_1}$ if $P = Q$
• The group structure allows for scalar multiplication of points, where for an integer $k$ and a point $P$, $kP = P + P + \cdots + P$ ($k$ times)
• The order of a point $P$ is the smallest positive integer $n$ such that $nP = \mathcal{O}$
• Lagrange's theorem states that the order of a subgroup divides the order of the group, so the order of a point divides the order of the elliptic curve group

Point Operations and Arithmetic

• Point addition on elliptic curves over finite fields can be performed efficiently using the addition law formulas
  • The formulas involve field operations (addition, subtraction, multiplication, inversion) in the underlying finite field
• Point doubling is the special case of adding a point to itself, $P + P = 2P$
• Scalar multiplication $kP$ can be computed efficiently using the double-and-add algorithm or window methods
  • The double-and-add algorithm uses a binary expansion of $k$ and performs a sequence of point doublings and additions
  • Window methods precompute multiples of $P$ and use a windowed expansion of $k$ to reduce the number of point additions
• Efficient implementation of point operations often involves projective coordinates (Jacobian, López-Dahab) to avoid expensive field inversions
• Point compression techniques can be used to reduce the storage and transmission size of elliptic curve points by exploiting the y-coordinate symmetry

Cryptographic Applications

• Elliptic Curve Diffie-Hellman (ECDH) key agreement
  • Alice and Bob agree on an elliptic curve $E$ over a finite field and a base point $P$ of large order
  • Alice chooses a secret integer $a$, computes $aP$, and sends it to Bob
  • Bob chooses a secret integer $b$, computes $bP$, and sends it to Alice
  • Alice and Bob compute the shared secret $abP = (ba)P$
• Elliptic Curve Digital Signature Algorithm (ECDSA)
  • Key generation: choose a secret key $d$ and compute the public key $Q = dP$
  • Signing: choose a random $k$, compute $R = kP$, $r = x_R \bmod n$, $s = k^{-1}(H(m) + dr) \bmod n$, signature is $(r, s)$
  • Verification: compute $w = s^{-1} \bmod n$, $u_1 = H(m)w \bmod n$, $u_2 = rw \bmod n$, $X = u_1P + u_2Q$, accept if $r = x_X \bmod n$
• Elliptic curve cryptography offers the same security level as RSA with much smaller key sizes
  • 256-bit ECC key is equivalent to 3072-bit RSA key
• ECC is used in various protocols and standards (TLS, S/MIME, PGP, Bitcoin)

Advanced Topics and Open Problems

• Pairing-based cryptography uses bilinear pairings on elliptic curves for identity-based encryption, short signatures, and other advanced functionalities
• Supersingular isogeny key exchange (SIKE) is a post-quantum key exchange protocol based on isogenies between supersingular elliptic curves
• Elliptic curve primality proving (ECPP) is a fast probabilistic algorithm for proving the primality of integers using elliptic curves
• Elliptic curve factorization method (ECM) is a subexponential algorithm for factoring integers using elliptic curves
• Schoof's algorithm determines the number of points on an elliptic curve over a finite field in polynomial time
• Open problems in elliptic curve cryptography include
  • Selecting secure curves (avoiding singular curves, anomalous curves, curves with small embedding degree)
  • Efficient implementation and side-channel protection
  • Quantum-safe alternatives (isogeny-based cryptography, lattice-based cryptography)
• The Birch and Swinnerton-Dyer conjecture, one of the Millennium Prize Problems, relates the rank of an elliptic curve to the behavior of its L-function