Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • 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
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

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

DeleteCancel

Session 2

No description
by

Jimmy Song

on 6 December 2018

Comments (0)

Please log in to add your comment.

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
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
Full transcript