Elliptic curves 101

This is very brief overview. There are better, and more complete introductions out there

• ECC - a gentle introduction
• Digital Signatures
• EdDSA standard

Elliptic Curves

• Described by this function
• But x, y are integers
• And x, y are between 0 and some prime number p

The key properties

• Addition (and multiplication by a scalar) is 'easy'
• Division (undoing the multiplication) is 'hard'

Addition

• Geometrically, $P + Q + R = 0$ if P, Q, R all lie on the same "line" (mod p).
• Thus addition looks like: $P + Q = -R$.
• -R is R reflected around the line $y = p / 2$

$P + P$ has no geometric construction, but is analogous to tangent on the continuous curve
(and the math works out the same - mod p)

Scalar Multiplication

Define scalar multiplication as

This can be calculated in $O(\log n)$ time, using the double and add
algorithm.

Multiplication properties

These elliptic curves have the associative property:

but they are also cyclic, meaning for some value n, the results of the multiplication start repeating:

• P is called the base point or generator of the curve.
• n is the order of the cyclic subgroup of the curve generated by P.
• In ECC, P is chosen so that n is large

Discrete logarithm problem

If we know P and Q, and $Q = kP \mod p$, can we easily find k?

i.e. $k = Q/P$

• No known 'easy' algorithm (i.e. runs in polynomial time)
• need to do divide by trial and error (choose k, check, repeat)
• for large k, this takes too long to be feasible

This is the basis of all ECC cryptography

Rules of cryptography (mod 3)

1. Never roll your own crypto
2. Never roll your own crypto
3. Don't. Roll. Your. Own. Crypto.

because
you will shoot yourself in the foot

Exceptions:

• null

Elliptic Curve Cryptography (ECC)

• Private key a random integer $d \in [1, n-1]$ with n the order of the sub-group.
• Public key $P = kG$, where G is base point, or generator of the group

Encryption with Elliptic Curve Diffie-Hellman (ECDH)

DH is a method for two parties to securely exchange keys.

$P_s$ is a shared secret than an eavesdropper has no practical hope of figuring out.

Signing and verifying messages

Alice wants to sign a message, m, that Bob (or anyone else) can verify with her public key, $P_a$.

EdDSA algorithm

Signing

1. Alice has her public and private keys $P_a = k_aG$
2. Calculate a temporary key from random nonce j: $R = rG$
3. Calc $e = \text{Hash}(R || m)$
4. Calc $s = r + ek_a$

Send m, R and s to Bob

EdDSA Verification

Bob has s, R, m, and $P_a$.

He doesn't know $k_a$ or r.

So Bob calculates s.G and e, and compares it to $R+ eP_a$.
If they match, he knows that Alice signed the message.