Spoorthi Satheesha

Sporadic writer
Serial anthropomorphizer

Share: 

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
,