from bit import Key
import ecdsa
import binascii
from ecdsa.curves import SECP256k1
import threading

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

curve = ecdsa.SECP256k1.curve
results = []

def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2

    if P1 == P2:
        lam = (3 * x1 * x1) * pow(2 * y1, -1, p)
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p)

    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    return (x3, y3)

def dbl(K):
    x,y = K
    P = ecdsa.ellipticcurve.Point(curve, x, y)
    k_dbl = 2 * P
    return (k_dbl.x(),k_dbl.y())

def mul(k,P):
    x,y = P
    point = ecdsa.ellipticcurve.Point(curve, x,y)
    r_p = point * k
    return (r_p.x(),r_p.y())

def revDbl(K,n):
    return mul((n+1)//2,K)

def sub(K,G,n):
    neg_G = (G[0], -G[1])
    sub_K = add(K,neg_G)

    return sub_K

def unCmp(pub):
    cmp_pub = binascii.unhexlify(pub)
    cmp_vk = ecdsa.VerifyingKey.from_string(cmp_pub, curve=ecdsa.SECP256k1)
    uncmp_pub = cmp_vk.to_string(encoding="uncompressed")
    uncmp_pub_hex = binascii.hexlify(uncmp_pub).decode('utf-8')
    uncmp_pub_hex = uncmp_pub_hex[2:]
    x = int(uncmp_pub_hex[:64],16)
    y = int(uncmp_pub_hex[64:],16)
    return (x,y)

def is_point_on_curve(point):
    x, y = point
    lhs = (y * y) % p
    rhs = (x * x * x + 7) % p
    return lhs == rhs

def runRev(K, bin_str, bits_num):
    hx = 0
    if len(bin_str) != 0:
        hx = hex(int(bin_str,2))

    print(len(bin_str), bin_str, hx, sep="\t")
    
    global results
    
    if len(results) > 0:
        return
    else:
        if len(bin_str) <= bits_num:
            # Rev DBL + ADD
            r_sub = sub(K,G,n)
            da_k = revDbl(r_sub,n)
            da_bin_str = "1" + bin_str
            if da_k == G:
                print("KEY FOUND", hx)
                results.append(da_bin_str)
                return
            elif is_point_on_curve(da_k):
                runRev(da_k, da_bin_str,bits_num)
            else:
                print("NOT ON CURVE")

            # Rev DBL
            d_k = revDbl(K,n)
            d_bin_str = "0"+bin_str
            if d_k == G:
                results.append(d_bin_str)
                return
            elif is_point_on_curve(d_k):
                runRev(d_k, d_bin_str,bits_num)
            else:
                print("NOT ON CURVE")
        else:
            return

def main():
    global results
    pub = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852"
    K = unCmp(pub)

    bits_num = 130
    bin_str = ''
    runRev(K, bin_str, bits_num)
    
    if len(results) > 0:
        print("KEY FOUND",results)

if __name__ == "__main__":
    main()