I wrote a small script that takes about 1min to solve puzzle 15, but takes forever to solve 130 I want to share it here in case someone can see what I mean to archive, or tell me where i'm going wrong.
this is supposed to reverse the bits (bits_num) used for double and add, or just double. But I'm stuck at getting an education guess of which one to pick. I tried calculating the slope but no success, have a look at 130 or try it with puzzle 15 which is very fast
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()