### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Session 2

No description
by

## Jimmy Song

on 6 December 2018

Report abuse

#### Transcript of Session 2

Trillion computers doing a trillion operations every trillionth of a second ( seconds) for a trillion years < operations.
Elliptic Curve
Cryptography
Day 1
Day 2
Session 2 Objectives
Learn Public Key Cryptography
Learn Mathematical Groups
Elliptic Curves over Finite Fields
Equations go through, but all x and y are integers
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.
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
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 =
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
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
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

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]

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

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

Foundational Math
Transaction Parsing
SCRIPT
Transaction Construction

Blocks
SPV