Elliptic Curves: ECDH, EC Elgamal, Curve25519

17 Dec 2021

Notes Cryptography Elliptic Curves: ECDH, EC Elgamal, Curve25519

§ Motivation

We've seen how we can generate cyclic groups over elliptic curves, but not how these groups can be used in cryptography. We'll see that many algorithms can be generalised over any cyclic group and not just quotient groups.

§ Elliptic Diffie-Hellman Key Exchange

ECDHE

Alice and Bob agree to use a particular elliptic curve $E(\mathbb{F}_p)$ and a particular point $P \in E(\mathbb{F}_p)$ . Alice and Bob then choose private keys $n_A$ and $n_B$ , and then they compute the following public keys

Q_A = n_AP \quad Q_B = n_BP.

They then exchange public keys, Alice can create the shared secret by computing $n_AQ_B$ and Bob by $n_BQ_A$ .

We've substituted exponentiation of an element in a quotient group with the multiplication of a elliptic point.

§ Elliptic Elgamal Public Key System

EC-Elgamal

Alice and Bob agree to use a particular elliptic curve $E(\mathbb{F}_p)$ and a particular point $P \in E(\mathbb{F}_p)$ . Alice chooses a private key $n_A$ and publishes public key $Q_A = n_AP$ . Bob has text given as a point $M \in E(\mathbb{F}_p)$ . Then, Bob encrypts his message by choosing a random element $k$ and computes the vlues

C_1 = kP\quad C_2 = M + kQ_A

Bob then sends the values $(C_1, C_2)$ (which is a 4-1 message expansion) to Alice who computes

C_2 - n_AC_1 = M + K(n_AP) - n_A(kP) = M.

As for the point $M$ , we need to define a function $f : \mathbb{N} \to E(\mathbb{F}_p)$ that is invertible. One such method is to let the message be the $x$ coordinate of the point and then computing the corresponding $y$ value.

§ Curve25519

One popular elliptic curve is Curve25519 which is designed to be used in ECDH, it is defined using the finite field of prime order $2^{255} - 19$ and the by the elliptic equation

E : y^2 = x^3 + 486662x^2 + x.

It uses the base point of $x=9$ , which has an prime order of around $2^{252}$ .

This curve is popular because it is resistant against timing attacks, and can accept any $32$ -byte string as a public key. It is also used as an alternative to the P-256 curve used in the Dual_EC_DRBG algorithm as it was uncovered in 2013 that the NSA built in a backdoor.