Class 3: Elliptic Curves

Schedule

Asymmetric Cryptosystems Recap

For asymmetric cryptography, we need a one-way function with a trapdoor: a function that can be easily inverted given a secret key, but is hard to invert without knowledge of that key.

Signatures: Signer encrypts a message with her own private key. Verifier checks the message using the signer's public key.

Elliptic Curve Cryptography

Elliptic curve: points satisfying an equation like y² = x³ + 7 (this is the curve used in bitcoin).

For real numbers, this is easy to solve: y = sqrt(x³ + 7).

In a finite field, it is complex enough to form the basis of cryptographic operations.

Crash Course in Group Theory

Group: A group is a set, G, on which the operation ⊕ is defined with the following properties:

1. Closure: for all a, b ∈ G, a ⊕ b ∈ G.

2. Associative: for all a, b, c ∈ G, (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c).

3. Identity: there is some element, 0 ∈ G, such that for all a ∈ G, a ⊕ 0 = 0 ⊕ a = a.

4. Inverse: for all a ∈ G, there exists an inverse, -a ∈ G, such that a ⊕ (-a) = 0.

Abelian Group: An abelian (or commutative) group has this additional property:

• Commutative: for all a, b ∈ G, a ⊕ b = b ⊕ a.

Are the integers and addition an abelian group?

Are the whole numbers and addition an abelian group?

Finite Field: A finite field is a set F of N ≥ 2 elements on which the operators ⊕ and × are defined with these properties:

1. F is an abelian group with identity 0 under the ⊕ operation.

2. The set F - { 0 } is an abelian group with identity 1 under the × operation.

3. Distributive: For all a, b, c ∈ F, (a ⊕ b) × c = (a × c) ⊕ (b × c).

(Note that this requires for all a, a × 0 = 0.)

Prime Field Theorem: For every prime number p, the set { 0, 1, …, p - 1 } forms a finite field with the operations addition and multiplication modulo p.

Demonstrate that F₃ is a finite field.

See Introduction to Finite Fields (notes from David Forney's MIT 6.451 course) for a proof that all prime fields, F_p are finite fields, and more thorough introduction to finite fields.

Operations on Elliptic Curves

"Addition" on an elliptic curve is done by finding the a point on the line between the two inputs points, and reflecting that point over the x-axis.

Here's what this looks like for real numbers (but don't be mislead — elliptic curves over finite fields do not look anything like these simple curves):

Image source: Eric Rykwalder, The Math Behind Bitcoin.

P + Q = R

Doing addition on elliptic curves over finite fields is more complex, and there has been a lot of research into how to do these operations efficiently. See the btcec.Add code for how it is done in the library.

Doubling (e.g., P + P = R) is the same idea, except instead of finding the intersection of the line formed by the two addends (which doesn't exist for the single point), finds the intersection between the tangent of the curve.

"Multiplication" is just repeated addition: kP = P + P + ... + P.

Is there a more efficient way to compute 9_P_ than using 8 additions?