Quote from: digaran on Today at 05:24:35 PM

Quote from: dred28 on Today at 04:59:03 PM

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

Code:

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()

Can you explain the logic? I am not familiar with bit_num and rev dbl. Solving puzzle 15 in 1 minute is extremely slow. By working with standard secp256k1 parameters you won't get anywhere, what you need to do is finding a method to convert secp256k1 points to new points with a much smaller size, then you can have 1000 times more speed.

Currently I can generate 1m keys in 20 seconds with my primitive and simple native implementation on an old android phone. So 26867 which is the decimal for #15, would take me half a second to solve.

Welcome!
Don't be shy, come on in, mi woods su woods.😉

I just added an update to explain my script since it has no commenting and strange variable names.