This is the archived Spring 2015 version of the course. For the most recent version, see http://bitcoin-class.org.

Class 3: Elliptic Curves

Posted: Wed 21 January 2015

Schedule

Project 1 is due Friday, 30 January.

Before the next class (Monday, Jan 26):


Note: due to a bug in slideshare's updated player, ink markings no longer appear in the viewer.
If you download the slides, they are present though. Hopefully, the player will be fixed someday.

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 y2 = x3 + 7 (this is the curve used in bitcoin).

For real numbers, this is easy to solve: y = sqrt(x3 + 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, bG, abG.

  2. Associative: for all a, b, cG, (ab) ⊕ c = a ⊕ (bc).

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

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

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

  • Commutative: for all a, bG, ab = ba.

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, cF, (ab) × 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 F3 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, Fp 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?

Comments