Elliptic curve cryptography

The curve. An elliptic curve $E(a,b)$ is the set of points satisfying $y^{2} = x^{3} + ax + b$ plus one extra point, $O$, the point at infinity. It is not a real coordinate pair, but an identity element added so every point has an inverse under the group operation defined below.

Point addition, geometrically. Take two distinct points $P$ and $Q$ on the curve. Draw the straight line through them. Because the curve is cubic, that line intersects it at exactly one more point. Reflect that third point across the $x$-axis: the result is $P + Q$.

Point negation. The reflection of a point across the $x$-axis is its negative: $-P = (x, -y)$. Three points that lie on one straight line always sum to zero: $P + Q + R = O$ when $P$, $Q$, $R$ are collinear.

Point doubling. When $P = Q$, there is no second point to draw a line through, so use the tangent line at $P$ instead. The tangent meets the curve at one further point; reflecting that point across the $x$-axis gives $2P$. Repeating this, and combining it with ordinary addition, is how $kP$ (the point $P$ added to itself $k$ times) is computed efficiently for large $k$, the same way repeated squaring makes $g^k \bmod p$ fast.

Over a finite field. For cryptography the curve is drawn over $\mathbb{Z}_p$ rather than the reals, written $E_p(a,b)$: $y^{2} \equiv x^{3} + ax + b \pmod{p}$ The curve is now a finite set of points plus $O$, exactly the kind of finite structure a discrete logarithm problem needs.

Over a binary field. Elliptic curves can also be built over $GF(2^m)$, the same binary-field construction used for AES’s finite fields, using a different equation: $y^{2} + xy = x^{3} + ax^{2} + b$ Coordinates and coefficients are field elements (bit strings), and addition is XOR throughout, including subtraction, since the two are identical in a field of characteristic 2: adding an element to itself always gives zero.

Worked check, $GF(2^4)$. Take $f(x) = x^4 + x + 1$ as the irreducible polynomial and $g = x = 0010$ as a generator, so every non-zero field element is some power $g^i$. Take the curve with $a = g^4$, $b = 1$, and check whether $(x,y) = (g^5, g^3)$ lies on it.

First, the powers of $g$ needed, each computed by multiplying the previous one by $x$ and reducing mod $f(x)$ whenever the result overflows 4 bits (in which case $x^4$ is replaced by $x+1 = 0011$, since $x^4 \equiv x+1 \pmod{f(x)}$):

$g^3 = 1000$, $g^4 = 0011$, $g^5 = 0110$, $g^6 = 1100$, $g^8 = 0101$, $g^{14} = 1001$, $g^{15} = 0001 = g^0$.

Substituting into $y^2 + xy = x^3 + ax^2 + b$ with $x = g^5$, $y = g^3$, $a = g^4$, $b = 1$: $(g^3)^2 + g^5 \cdot g^3 = (g^5)^3 + g^4(g^5)^2 + 1$ $g^6 + g^8 = g^{15} + g^{14} + 1$

In binary, using the powers above: $1100 + 0101$ on the left, $0001 + 1001 + 0001$ on the right. XOR each side: $1100 \oplus 0101 = 1001$ on the left; $0001 \oplus 1001 \oplus 0001 = 1001$ on the right. Both sides equal $1001$, so $(g^5, g^3)$ lies on the curve.

The elliptic curve discrete logarithm problem (ECDLP). Given points $P$ and $Q$ on $E_p(a,b)$ with $Q = kP$, finding $k$ is believed infeasible for a large enough curve: no method faster than trying values of $k$ is known. The lecture’s small example, on $E_{23}(9,17)$, finds $k$ for $P = (16,5)$ and $Q = (4,5)$ by brute force, listing every multiple of $P$ in turn:

$P=(16,5) \quad 2P=(20,20) \quad 3P=(14,14) \quad 4P=(19,20) \quad 5P=(13,10)$ $6P=(7,3) \quad 7P=(8,7) \quad 8P=(12,17) \quad 9P=(4,5)$

$9P$ matches $Q$, so $k = 9$. This only worked because the curve is tiny. With $k$ chosen from a space of real-world size, listing every multiple is infeasible, which is exactly the property the scheme relies on.

Elliptic curve Diffie-Hellman (ECDH). Both parties, and any attacker, already know the system-wide public parameters: the curve $E_p(a,b)$, a base point $G$, and $G$‘s order $n$ (the smallest $n$ with $nG = O$, chosen as a large prime). Key agreement mirrors classical Diffie-Hellman with scalar point multiplication in place of modular exponentiation:

• Alice picks a private scalar $n_A$ and publishes $P_A = n_A \cdot G$.
• Bob picks a private scalar $n_B$ and publishes $P_B = n_B \cdot G$.
• Alice computes $n_A \cdot P_B$; Bob computes $n_B \cdot P_A$.

$n_A \cdot P_B = n_A \cdot (n_B \cdot G) = n_B \cdot (n_A \cdot G) = n_B \cdot P_A$

Both reach the same point, for the same reason as classical DH: the two scalars commute. Recovering $n_A$ from $P_A$ and $G$ alone is the ECDLP, believed infeasible.

EC ElGamal encryption. The message is first encoded as a curve point $P_m$. Public parameters: the curve $E_q(a,b)$, a generator $G$ of large order $n$.

The mask $kP_B$ cancels because $n_B \cdot (kG) = k \cdot (n_B G) = kP_B$. Bob reconstructs the same mask Alice applied, using his private key against Alice’s $kG$, and subtracts it back out.

Security and key size. ECC’s security rests on the ECDLP being hard to solve for $k$ given $P$ and $kP$. The lecture states the ECDLP is harder, bit for bit, than the classical discrete logarithm or RSA problems, which is why comparable security needs a much shorter key: 256-bit ECC keys are described as very common, with 384-bit for higher security. The slides go on to compare these figures directly against RSA key sizes in a table that did not survive PDF extraction. That specific side-by-side comparison is not reproduced here, but the general shape of it (ECC keys are much shorter than RSA keys for equivalent security) is the fact the practice quiz tests, and is stated directly above.