Elliptic Curve Cryptography: An Introduction

Elliptic Curve Cryptography (ECC) is a powerful approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. This post explains the mathematical foundations of ECC and its practical applications in modern cryptography.

Elliptic Curves: The Basics

An elliptic curve over a field $K$ is defined by the Weierstrass equation:

$$ E: y^2 = x^3 + ax + b $$

where $a, b \in K$ and the discriminant $\Delta = -16(4a^3 + 27b^2) \neq 0$ (ensuring the curve is non-singular).

In cryptography, we typically work with elliptic curves over finite fields $\mathbb{F}_p$ (where $p$ is a prime) or $\mathbb{F}_{2^m}$ (binary fields). For simplicity, we'll focus on curves over $\mathbb{F}_p$, which gives us:

$$ E(\mathbb{F}_p): y^2 \equiv x^3 + ax + b \pmod{p} $$

The set of points on the curve, along with a special point at infinity $\mathcal{O}$, forms an abelian group.

Group Law: Point Addition

The fundamental operation in ECC is point addition. Given two points $P$ and $Q$ on an elliptic curve, their sum $P + Q$ is defined geometrically:

  1. Draw a line through $P$ and $Q$
  2. Find the third intersection point of this line with the curve
  3. Reflect this point across the x-axis to get $P + Q$

Algebraically, if $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ with $P \neq Q$, then $P + Q = (x_3, y_3)$ where:

$$ \lambda = \frac{y_2 - y_1}{x_2 - x_1} $$ $$ x_3 = \lambda^2 - x_1 - x_2 $$ $$ y_3 = \lambda(x_1 - x_3) - y_1 $$

If $P = Q$, we use the tangent line (point doubling):

$$ \lambda = \frac{3x_1^2 + a}{2y_1} $$ $$ x_3 = \lambda^2 - 2x_1 $$ $$ y_3 = \lambda(x_1 - x_3) - y_1 $$

The point at infinity $\mathcal{O}$ serves as the identity element such that $P + \mathcal{O} = P$ for any point $P$.

Scalar Multiplication

The operation central to ECC is scalar multiplication: computing $nP$ (a point $P$ added to itself $n$ times). While addition can be computed in polynomial time, there is no known efficient algorithm to compute $n$ given $P$ and $nP$ for large $n$. This is the discrete logarithm problem for elliptic curves (ECDLP), and its computational difficulty forms the basis of ECC security.

Scalar multiplication can be efficiently computed using the double-and-add algorithm:

  1. Express $n$ in binary: $n = \sum_{i=0}^{t} n_i 2^i$ where $n_i \in {0,1}$
  2. Initialize $Q = \mathcal{O}$
  3. For $i$ from $t$ down to 0:
    • $Q = 2Q$ (doubling)
    • If $n_i = 1$, then $Q = Q + P$ (addition)
  4. Return $Q = nP$

This algorithm computes $nP$ in $O(\log n)$ operations.

Finite Field Arithmetic

In practice, all calculations are performed in finite fields, and the formulas must be adapted accordingly. For a curve over $\mathbb{F}_p$, all arithmetic operations are performed modulo $p$.

For $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ on $E(\mathbb{F}_p)$, the addition formulas become:

$$ \lambda = \frac{y_2 - y_1}{x_2 - x_1} \mod p $$ $$ x_3 = (\lambda^2 - x_1 - x_2) \mod p $$ $$ y_3 = (\lambda(x_1 - x_3) - y_1) \mod p $$

And for doubling $P$:

$$ \lambda = \frac{3x_1^2 + a}{2y_1} \mod p $$ $$ x_3 = (\lambda^2 - 2x_1) \mod p $$ $$ y_3 = (\lambda(x_1 - x_3) - y_1) \mod p $$

ECC Key Generation and Exchange

The cryptographic power of ECC lies in its key generation and exchange protocols:

  1. Key Generation:

    • Choose a secure elliptic curve $E$ over a finite field and a base point $G$ of large order $n$
    • Select a random integer $d \in [1, n-1]$ as the private key
    • Compute the public key $Q = dG$

  2. Diffie-Hellman Key Exchange:

    • Alice generates key pair $(d_A, Q_A = d_A G)$
    • Bob generates key pair $(d_B, Q_B = d_B G)$
    • They exchange public keys $Q_A$ and $Q_B$
    • Alice computes $S = d_A Q_B = d_A d_B G$
    • Bob computes $S = d_B Q_A = d_B d_A G$
    • Both arrive at the same shared secret $S$

An eavesdropper would need to solve the ECDLP to derive the private keys.

Elliptic Curve Digital Signature Algorithm (ECDSA)

ECDSA is a variant of the Digital Signature Algorithm (DSA) that uses elliptic curve cryptography:

  1. Signature Generation (by Alice):

    • Choose a random $k \in [1, n-1]$
    • Compute $R = kG$ and extract the x-coordinate $r = x_R \mod n$
    • Compute $s = k^{-1}(H(m) + d_A \cdot r) \mod n$, where $H(m)$ is the hash of message $m$
    • The signature is the pair $(r, s)$

  2. Signature Verification (by Bob):

    • Compute $u_1 = s^{-1} \cdot H(m) \mod n$ and $u_2 = s^{-1} \cdot r \mod n$
    • Compute $R' = u_1 G + u_2 Q_A$
    • The signature is valid if $r \equiv x_{R'} \pmod{n}$

Standard Curves and Security Considerations

Commonly used standardized elliptic curves include:

  • NIST curves: P-256, P-384, P-521
  • Curve25519/Ed25519: Designed for efficiency and security by Daniel J. Bernstein
  • secp256k1: Used in Bitcoin and other cryptocurrencies

The security of an elliptic curve system depends on:

  1. Curve selection: Avoid curves with known vulnerabilities
  2. Field size: For general security, the prime $p$ should be at least 256 bits
  3. Implementation: Must be resistant to side-channel attacks
  4. Random number generation: Critical for key generation and signing

The discrete logarithm problem on a well-chosen elliptic curve with a 256-bit field size is believed to provide security equivalent to RSA with a 3072-bit modulus.

Advantages of ECC over RSA

ECC offers several advantages over traditional RSA cryptography:

  1. Smaller key sizes: A 256-bit ECC key provides comparable security to a 3072-bit RSA key
  2. Greater efficiency: Faster computations, especially for signature generation
  3. Lower bandwidth and storage requirements: Smaller keys and signatures
  4. Lower power consumption: Important for resource-constrained devices

These advantages make ECC particularly suitable for:

  • Mobile and IoT devices
  • Smart cards
  • TLS/SSL connections
  • Cryptocurrency systems
  • VPN protocols

Conclusion

Elliptic curve cryptography represents one of the most elegant applications of advanced mathematics to practical security problems. Its efficiency and strong security properties have made it the cryptographic method of choice for many modern applications, from securing web traffic to enabling digital currencies.

The mathematical beauty of elliptic curves combined with their cryptographic utility demonstrates how pure mathematics can lead to powerful real-world applications that shape our digital infrastructure.