Elliptic Curve

Cryptography

**Day 1**

**Day 2**

Session 2 Objectives

Learn Public Key Cryptography

Learn Mathematical Groups

Learn Creating Bitcoin Addresses

Elliptic Curves over Finite Fields

Equations go through, but all x and y are integers

Point addition still works!

Magic!

Curve Over Reals

Curve over Finite Field

Example

Verify (73, 128) is on the curve

Exercise 1

1. Which of these points are on

(192,105), (17,56), (200,119), (1,193), (42,99)

2. Write a test called test_on_curve under ECCTest that tests these points.

Point Addition

Group Law for

Example

What is (73,128)+(46,22)?

(73,128)+(46,22)=(99,49)

Exercise 2

1. Solve these equations:

(192,105) + (17,56)

(47,71) + (117,141)

(143,98) + (76,66)

2. Write a test to test them

Group Law for

Example

What is 2*(73,128)?

2*(73,128)=(103,76)

Exercise 3

1. Solve these equations:

2*(192,105) = ?

2*(143,98) = ?

2*(47,71) = ?

4*(47,71) = ?

8*(47,71) = ?

21*(47,71) = ?

Mathematical Group

Single Operation (+)

Closed (if A, B in G, A+B in G)

Associative ((A+B)+C = A+(B+C))

Commutative (A+B=B+A)

Invertible (if A in G, there’s a -A in G)

Identity (0 exists)

Point addition gets us a group!

Generating the Group

Start with an Elliptic Curve over a Finite Field

Pick a point G (generator point)

Keep adding G until we get "zero" or point at infinity

G+G = 2G, G+G+G = 3G, ... nG = 0

{0, G, 2G, 3G, ... (n-1)G} is a finite group

Example

G=(47,71)

G=(47, 71) 2G=(36, 111) 3G=(15, 137)

4G=(194, 51) 5G=(126, 96) 6G=(139, 137)

7G=(92, 47) 8G=(116, 55) 9G=(69, 86)

10G=(154, 150) 11G=(154, 73) 12G=(69, 137)

13G=(116, 168) 14G=(92, 176) 15G=(139, 86)

16G=(126, 127) 17G=(194, 172) 18G=(15, 86)

19G=(36, 112) 20G=(47, 152) 21G=0

Group has 21 elements n=21

Exercise 4

1. How many elements does the group generated by (15, 86) have?

2. Write the test for __rmul__.

Making Groups Useful

Imagine a really large group ~ 2^256

P = sG where s is really, really large

Finding P when we know s is easy

Referred to as the Discrete Log Problem

Lower case letter for scalar, upper case for Point

Finding s when we know P is not

Elliptic Curve Definition

Elliptic Curve equation's (a and b)

Finite Field prime (p)

Generator Point (G)

Number of points in the group (n)

secp256k1

a=0, b=7

p =

G = (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

is really big

First:

Number of atoms in and on earth ~

Number of atoms in the solar system ~

Number of atoms in the galaxy ~

Number of atoms in the universe ~

Confirming G is on the curve

p = 2**256 - 2**32 - 977

x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

print(y**2 % p == (x**3 + 7) % p) # True

Confirming the order of G is n

from ecc import G

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

print(n*G) # Point(infinity)

Public Key Cryptography

Private key is the scalar (s)

Public key is the resulting point sG=P

Public key is two numbers (x,y)

Example

from ecc import G

secret = 999

point = secret*G

print(point)

Point(9680241112d370b56da22eb535745d9e314380e568229e09f7241066003bc471, ddac2d377f03c201ffa0419d6596d10327d6c70313bb492ff495f946285d8f38)

Exercise 5

1. Get the public point where

s = 7

s = 1485

s = 2**128

s = 2**240+2**31

2. Write the test test_pubpoint

Addresses

Example

Uncompressed SEC format:

045CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA

Exercise 6

1. Find the compressed and uncompressed SEC format for public keys where the private key is:

s = 999**3

s = 123

s = 42424242

2. Write the sec method

SEC Format

P = (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA)

Compressed SEC format:

y-coordinate is even (ends in A) => 02

025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

Example

Exercise 7

1. Find the mainnet and testnet address corresponding to these private keys.

s = 888**3, sec = Compressed

s = 321, sec = Uncompressed

s = 4242424242, sec = Uncompressed

2. Write the “address” method

Address Computation

from helper import encode_base58, hash160, double_sha256

sec = bytes.fromhex('025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC')

h160 = hash160(sec)

raw = b"\x00" + h160

raw = raw + double_sha256(raw)[:4]

addr = encode_base58(raw)

print(addr) # 19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA

Take either compressed or uncompressed SEC format

SHA-256 the result and then RIPEMD160 the result (aka HASH160)

Prepend with network prefix (00 for mainnet, 6F for testnet)

Add a 32-bit double-SHA256 checksum at the end

Encode in Base58

Exercise 8

1. Create a testnet address using your own secret key. Send your address to me.

Record this key and address! You will need it tomorrow.

**Foundational Math**

**Transaction Parsing**

**SCRIPT**

**Transaction Construction**

**Blocks**

**SPV**

**Advanced Topics**