#!/usr/bin/env python3
import hashlib
import random

# secp256k1 curve parameters
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

def mod_inverse(k, p):
    """Calculate modular inverse: k^-1 mod p"""
    return pow(k, p - 2, p)

def point_add(p1_x, p1_y, p2_x, p2_y):
    """Add two points on the curve"""
    if p1_x is None:
        return p2_x, p2_y
    if p2_x is None:
        return p1_x, p1_y
       
    if p1_x == p2_x and p1_y != p2_y:
        return None, None  # Point at infinity
       
    if p1_x == p2_x:
        # Point doubling
        lam = (3 * p1_x * p1_x) * mod_inverse(2 * p1_y, p) % p
    else:
        # Point addition
        lam = ((p2_y - p1_y) * mod_inverse((p2_x - p1_x) % p, p)) % p
       
    x3 = (lam * lam - p1_x - p2_x) % p
    y3 = (lam * (p1_x - x3) - p1_y) % p
   
    return x3, y3

def scalar_mult(k, p_x, p_y):
    """Multiply point by scalar"""
    nx, ny = None, None
   
    while k > 0:
        if k & 1:
            nx, ny = point_add(nx, ny, p_x, p_y)
        k = k >> 1
        p_x, p_y = point_add(p_x, p_y, p_x, p_y)
       
    return nx, ny

def generate_keypair():
    """Generate private key and public key"""
    private_key = random.randint(1, n - 1)
   
    public_key_x, public_key_y = scalar_mult(private_key, G_x, G_y)
   
    print(f"Private key: {hex(private_key)}")
    print(f"Public key: ({hex(public_key_x)}, {hex(public_key_y)})")
   
    return private_key, (public_key_x, public_key_y)

def sign_message(private_key, message):
    """Sign a message using ECDSA"""
    message_hash = int(hashlib.sha256(message.encode()).hexdigest(), 16)
   
    # Generate random k (nonce)
    k = random.randint(1, n - 1)
   
    # Calculate point R = k * G
    r_x, r_y = scalar_mult(k, G_x, G_y)
   
    # r is the x-coordinate modulo n
    r = r_x % n
   
    # Calculate s = k^(-1) * (hash + r * private_key) mod n
    s = (mod_inverse(k, n) * (message_hash + r * private_key) % n) % n
   
    # Calculate values used in verification
    w = mod_inverse(s, n)  # s^(-1) mod n
    u1 = (message_hash * w) % n
    u2 = (r * w) % n
   
    print(f"Message: {message}")
    print(f"k Nonce: {hex(k)}")
    print(f"r: {hex(r)}")
    print(f"s: {hex(s)}")
    print(f"z: {hex(message_hash)}")
    print(f"Verification values:")
    print(f"  u1: {hex(u1)}")
    print(f"  u2: {hex(u2)}")
   
    return r, s, message_hash, u1, u2

def main():
    """Main function"""
    # Generate keys and sign a message
    private_key, public_key = generate_keypair()
    message = "BitcoinTalk"
    r, s, z, u1, u2 = sign_message(private_key, message)
   
    print("\nPart 2: Generating signatures using public key, u1 and u2 values")
    print("=" * 60)
   
    def fast_add(p1, p2):
        return point_add(p1[0], p1[1], p2[0], p2[1])
   
    def fast_multiply(point, scalar):
        return scalar_mult(scalar, point[0], point[1])
   
    G = (G_x, G_y)
    Q = public_key
   
    # Use u1 and u2 values from first signature
    a = u1
    b = u2
   
    # Calculate the signature using a and b
    sig_point = fast_add(fast_multiply(G, a), fast_multiply(Q, b))
    r1 = sig_point[0] % n
    s1= (r1 * mod_inverse(b, n)) % n
   
    # Calculate z (message hash) from the result
    z1 = (a * r1 * mod_inverse(b, n)) % n
   
    # Verify the signature
    w1 = mod_inverse(s1, n)
    u1_1 = (z1 * w1) % n
    u2_1 = (r1 * w1) % n
   
    verify_point = fast_add(fast_multiply(G, u1_1), fast_multiply(Q, u2_1))
   
    # verification
    verification_success = (r1 == verify_point[0] % n)
   
    print(f"a = {hex(a)}")
    print(f"b = {hex(b)}")
    print(f"Generated Signature:")
    print(f"r1 = {hex(r1)}")
    print(f"s1 = {hex(s1)}")
    print(f"z1 = {hex(z1)}")

if __name__ == "__main__":
    main()