Schedule
Before the next class (Monday, Jan 26):

Read: Satoshi Nakamoto, Bitcoin: A PeertoPeer Electronic Cash System, 2008. The is the original bitcoin paper, which is quite readable.

Read: Chapter 5: Transactions from Andreas Antonopoulos' book.
Asymmetric Cryptosystems Recap
For asymmetric cryptography, we need a oneway 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^{2} = x^{3} + 7 (this is the curve used in bitcoin).
For real numbers, this is easy to solve: y = sqrt(x^{3} + 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:

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

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

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

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:

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

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

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_{3} 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 xaxis.
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