ZK-Bootcamp - Homework 4 - Elliptic Curves
Use this resource as a reference for implementing the algorithm: https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages
The following may also be helpful:
https://www.rareskills.io/post/finite-fields
https://www.rareskills.io/post/elliptic-curve-addition
https://www.rareskills.io/post/elliptic-curves-finite-fields
https://rareskills.io/post/ecdsa-tutorial
Implement ECDSA from scratch. You want to use the secp256k1 curve (which specifies the values for the curve). When starting off, use the Elliptic curve multiplication library used in the blog post linked here: https://www.rareskills.io/post/generate-ethereum-address-from-private-key-python
1) pick a private key
2) generate the public key using that private key (not the eth address, the public key)
3) pick message m and hash it to produce h (h can be though of as a 256 bit number)
4) sign m using your private key and a randomly chosen nonce k. produce (r, s, h, PubKey)
5) verify (r, s, h, PubKey) is valid
You may use a library for point multiplication, but everything else you must do from scratch. Remember, when you compute the multiplicative inverse, you need to do it with respect to the curve order.
Pay close attention to the distinction between the curve order and the prime number $p$ we compute the modulus of $y^2=x^3+b \pmod p$.
!python -m pip install numpy
!python -m pip install ecpy
# secp256k1 => y^2 = x^3 + 7 (mod 2^256 + 2^32 - 977)
a = 0
b = 7
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
from ecpy.curves import Curve
from hashlib import sha256
import random
cv = Curve.get_curve('secp256k1')
curve_order = cv.order
g = cv.generator
def scalar_multiplication(scalar):
new_point = g.mul(scalar)
return new_point
def get_public_key(private_key):
return scalar_multiplication(private_key)
def hash_msg(msg):
return sha256(msg).digest()
def sign_message(message, private_key):
h = hash_msg(message)
h_int = int.from_bytes(h, 'big') # Convert bytes to integer
k = h_int + private_key
R = scalar_multiplication(k)
r = R.x % p
k_inv = pow(k, -1, curve_order)
s = k_inv * (h_int + r * private_key) % curve_order
return (r, s)
def verify_signature(message, r, s, public_key):
h = hash_msg(message)
h_int = int.from_bytes(h, 'big')
s1 = pow(s, -1, curve_order)
R_ = scalar_multiplication(h_int * s1) + (r * s1) * public_key
r_ = R_.x % curve_order
return r_ == r
private_key = random.getrandbits(256) # Generate a random private key
public_key = get_public_key(private_key)
print('private key: ', hex(private_key))
print('public key: ', public_key)
message = b'Hello, world!'
hashed_message = hash_msg(message)
print('hashed message: ', hashed_message.hex())
r,s = sign_message(message, private_key)
print('signature: (r, s) = ', (hex(r), hex(s)))
assert verify_signature(message, r, s, public_key) == True
new_private_key = random.getrandbits(256) # create a new secret key
new_public_key = get_public_key(new_private_key)
assert verify_signature(message, r, s, new_public_key) == False