Elliptic Curve Cryptography

Why elliptic curvesSearch on YouTubeBookmarkSaved

Most public-key schemes (RSA, Diffie-Hellman) use integer or polynomial arithmetic with very large numbers or polynomials. This puts a significant load on the storage and processing of keys and messages.

Elliptic curves are an alternative. They give the same security with smaller bit sizes.

Elliptic curve arithmeticSearch on YouTubeBookmarkSaved

Real elliptic curvesSearch on YouTubeBookmarkSaved

An equation in two variables $x$ and $y$, with coefficients, defines an elliptic curve. The slides use a cubic elliptic curve of this form:

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

Here $x$, $y$, $a$ and $b$ are all real numbers. The scheme also defines a zero point $O$.

• $E(a,b)$ is the set of points $(x, y)$ that satisfy the equation.
• The set has an addition operation.
• Geometrically, the sum $P + Q$ is the reflection of the intersection $R$.

The line through $P$ and $Q$ meets the curve again at a third point $R$. The reflection of $R$ across the $x$-axis is $P + Q$.

Real curve exampleSearch on YouTubeBookmarkSaved

The slide figure shows the curve $y^2 = x^3 + x + 1$.

• The points $P$ and $Q$ are on the curve.
• The dashed line through $P$ and $Q$ meets the curve a third time, in the upper branch. The figure labels this point $-(P+Q)$.
• The vertical dashed line reflects this point across the $x$-axis. The result in the lower branch is $P+Q$.

Addition over GF(p)Search on YouTubeBookmarkSaved

Cryptography uses a finite field, not real numbers. The same equation is used over $GF(p)$ with a prime $p$. All arithmetic is mod $p$.

Let $P(x_P, y_P)$ and $Q(x_Q, y_Q)$ be two points on the curve. Then $R(x_R, y_R) = P + Q$ is:

$x_R = (\lambda^2 - x_P - x_Q) \bmod p$

$y_R = \left(\lambda\left(x_P - x_R\right) - y_P\right) \bmod p$

The slope $\lambda$ depends on whether the two points are equal:

$\lambda = \begin{cases} \left(\frac{y_Q - y_P}{x_Q - x_P}\right) \bmod p & \text{if } P \ne Q \\[6pt] \left(\frac{3x_P^2 + a}{2y_P}\right) \bmod p & \text{if } P = Q \end{cases}$

Both cases need a multiplicative inverse mod $p$.

Worked example in $E_{23}(1,1)$Search on YouTubeBookmarkSaved

The slide example uses the curve $y^2 = x^3 + x + 1$ over $GF(23)$. The name of this curve is $E_{23}(1,1)$. Let $P = (3, 10)$ and $Q = (9, 7)$.

Step 1: add $P$ and $Q$.

Step 2: double $P$.

The last slope step uses the multiplicative inverse of $4$ in $Z_{23}$. The extended Euclidean algorithm finds it. To confirm: $(6 \times 4) \bmod 23 = 24 \bmod 23 = 1$.

Repeated additionSearch on YouTubeBookmarkSaved

Multiplication of a point by an integer is repeated addition. For example:

$4P = P + P + P + P$

ECC schemesSearch on YouTubeBookmarkSaved

The hard problemSearch on YouTubeBookmarkSaved

The slides compare ECC arithmetic with modular arithmetic:

ECC needs a "hard" problem that is equivalent to the discrete log:

• $Q = kP$, where $Q$ and $P$ belong to a prime curve.
• It is "easy" to compute $Q$ from $k$ and $P$.
• It is "hard" to find $k$ from $Q$ and $P$.
• The name of this problem is the elliptic curve logarithm problem.

The slide gives the Certicom example curve $E_{23}(9,17)$. This is $y^2 = x^3 + 9x + 17$ over $GF(23)$.

ECC Diffie-HellmanSearch on YouTubeBookmarkSaved

ECC can do a key exchange that is analogous to Diffie-Hellman.

The two keys are the same, because:

$K = n_A P_B = n_A (n_B G) = n_A n_B G = n_B (n_A G) = n_B P_A$

An attacker who sees $G$, $P_A$ and $P_B$ must find $k$. This is the hard problem.

Encryption and decryptionSearch on YouTubeBookmarkSaved

There are several alternatives for ECC encryption. The slides use the simplest one:

1. Encode the message $M$ as a point $P_m$ on the elliptic curve.
2. Select a suitable curve and point $G$, as in Diffie-Hellman.
3. Each user chooses a private key $n_A < n$.
4. Each user computes the public key $P_A = n_A G$.

To encrypt $P_m$, the sender selects a random $k$ and sends:

$C_m = \{\, kG, \; P_m + kP_b \,\}$

To decrypt $C_m$, the receiver uses the private key $n_b$ and computes:

$P_m + kP_b - n_b(kG) = P_m + k(n_b G) - n_b(kG) = P_m$

The value $n_b(kG)$ is equal to the mask $kP_b$. Subtraction removes the mask and gives $P_m$.

Slide example: $E_{257}(0,-4)$Search on YouTubeBookmarkSaved

The handwritten slide does a full example on this curve:

$y^2 = x^3 - 4 \qquad E_q(a,b) = E_{257}(0,-4) \qquad G = (2, 2)$

Key setup.

Both sides get the same shared point $(68, 84)$.

Encryption. Alice encrypts for Bob.

Decryption. Bob computes:

$C_2 - n_B C_1 = (246,174) - 101\,(136,128) = (246,174) - (68,84) = (112, 26)$

Bob gets the plaintext point $(112, 26)$.

ECC securitySearch on YouTubeBookmarkSaved

Security basisSearch on YouTubeBookmarkSaved

• The security of ECC relies on the elliptic curve logarithm problem.
• ECC can use much smaller key sizes than RSA, which relies on factoring.
• For equivalent key lengths, the computations are roughly equivalent.
• Thus, for similar security, ECC gives significant computational advantages.

Comparable key sizesSearch on YouTubeBookmarkSaved

The ECC size is two times the symmetric key size. The RSA/DSA modulus grows much faster. For example, a 160-bit curve gives the same security as an 80-bit symmetric key and a 1024-bit RSA modulus.

Quick self-testSearch on YouTubeBookmarkSaved

Why does ECC give the same security as RSA with smaller bit sizes?

RSA and Diffie-Hellman need very large integers or polynomials. These put a load on storage and processing. The elliptic curve logarithm problem is hard at much smaller sizes. For example, a 256-bit ECC key matches a 3072-bit RSA modulus.

Give the equation of a real elliptic curve and the special point.

$y^2 = x^3 + ax + b$, with $x, y, a, b$ real numbers. The scheme also defines a zero point $O$. $E(a,b)$ is the set of points that satisfy the equation.

Describe the geometric view of $P + Q$ on a real elliptic curve.

Draw the line through $P$ and $Q$. The line meets the curve a third time at $R$. The sum $P+Q$ is the reflection of $R$ across the $x$-axis.

State the point addition and doubling formulas over $GF(p)$.

$x_R = (\lambda^2 - x_P - x_Q) \bmod p$ and $y_R = (\lambda(x_P - x_R) - y_P) \bmod p$. If $P \ne Q$, $\lambda = (y_Q - y_P)(x_Q - x_P)^{-1} \bmod p$. If $P = Q$, $\lambda = (3x_P^2 + a)(2y_P)^{-1} \bmod p$.

Find $P+Q$ and $2P$ for $P=(3,10)$, $Q=(9,7)$ in $E_{23}(1,1)$.

$P+Q$: $\lambda = -1/2 \bmod 23 = 11$. $x_R = 109 \bmod 23 = 17$. $y_R = -164 \bmod 23 = 20$. So $P+Q = (17,20)$. $2P$: $\lambda = 5/20 = 1/4 \bmod 23 = 6$. $x_R = 30 \bmod 23 = 7$. $y_R = -34 \bmod 23 = 12$. So $2P = (7,12)$.

What is the elliptic curve logarithm problem?

$Q = kP$ on a prime curve. It is easy to compute $Q$ from $k$ and $P$. It is hard to find $k$ from $Q$ and $P$. ECC security relies on this problem.

Write the ECC Diffie-Hellman steps.

Select a curve $E_q(a,b)$ and a base point $G$ with a large order $n$, so that $nG = O$. Select private keys $n_A, n_B < n$. Compute public keys $P_A = n_A G$ and $P_B = n_B G$. The shared key is $K = n_A P_B = n_B P_A = n_A n_B G$.

Give the ECC encryption and decryption formulas.

Encode $M$ as a point $P_m$. Encrypt with a random $k$: $C_m = \{kG,\ P_m + kP_b\}$. Decrypt: $P_m + kP_b - n_b(kG) = P_m + k(n_b G) - n_b(kG) = P_m$.

Give the results of the $E_{257}(0,-4)$ slide example.

Curve $y^2 = x^3 - 4$, $G = (2,2)$. Alice: $n_A = 41$, $P_A = (136,128)$. Bob: $n_B = 101$, $P_B = (197,167)$. Shared key: $(68,84)$. Encrypt $P_m = (112,26)$ with $k = 41$: $C_m = \{(136,128),(246,174)\}$. Decrypt: $(246,174) - (68,84) = (112,26)$.

Give the key-size pairs for 80-bit and 128-bit security.

80-bit symmetric: 160-bit ECC, 1024-bit RSA/DSA. 128-bit symmetric: 256-bit ECC, 3072-bit RSA/DSA.