Administrator

Here is some code on Python. The code is single-threaded, and its main purpose is to introduce anybody who interested in the game.
The code requires no external modules in their simplest variant. If you wish to speed up calculations by a factor 15 approximately, install gmpy2 module, then uncomment lines 3, 44 and comment line 45.
The simplest variant with modular inversion written on Python is also fast enough, 32-bit problem takes ~30 sec on my Core i5-5xxx.
Any questions and ideas are welcomed!

import time import random #import gmpy2 modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 class Point: def __init__(self, x=0, y=0): self.x = x self.y = y PG = Point(Gx,Gy) Z = Point(0,0) # zero-point, infinite in real x,y - plane # return (g, x, y) a*x + b*y = gcd(x, y) def egcd(a, b): if a == 0: return (b, 0, 1) else: g, x, y = egcd(b % a, a) return (g, y - (b // a) * x, x) def rev(b, n = modulo): while b < 0: b += modulo g, x, _ = egcd(b, n) if g == 1: return x % n def mul2(P, p = modulo): R = Point() c = 3*P.x*P.x*rev(2*P.y, p) % p R.x = (c*c-2*P.x) % p R.y = (c*(P.x - R.x)-P.y) % p return R def add(P, Q, p = modulo): R = Point() dx = Q.x - P.x dy = Q.y - P.y #c = dy * gmpy2.invert(dx, p) % p c = dy * rev(dx, p) % p R.x = (c*c - P.x - Q.x) % p R.y = (c*(P.x - R.x) - P.y) % p return R # 6 sub, 3 mul, 1 inv def mulk(k, P = PG, p = modulo): if k == 0: return Z elif k == 1: return P elif (k % 2 == 0): return mulk(k/2, mul2(P, p), p) else: return add(P, mulk( (k-1)/2, mul2(P, p), p), p) def X2Y(X, p = modulo): if p % 4 != 3: print 'prime must be 3 modulo 4' return 0 X = (X**3+7)%p pw = (p + 1) / 4 Y = 1 for w in range(256): if (pw >> w) & 1 == 1: tmp = X for k in range(w): tmp = (tmp**2)%p Y *= tmp Y %= p return Y def comparator(): A, Ak, B, Bk = [], [], [], [] with open('tame.txt') as f: for line in f: L = line.split() a = int(L[0],16) b = int(L[1]) A.append(a) Ak.append(b) with open('wild.txt') as f: for line in f: L = line.split() a = int(L[0],16) b = int(L[1]) B.append(a) Bk.append(b) result = list(set(A) & set(B)) if len(result) > 0: sol_kt = A.index(result[0]) sol_kw = B.index(result[0]) print 'total time: %.2f sec' % (time.time()-starttime) d = Ak[sol_kt] - Bk[sol_kw] print 'SOLVED:', d file = open("results.txt",'a') file.write(('%d'%(Ak[sol_kt] - Bk[sol_kw])) + "\n") file.write("---------------\n") file.close() return True else: return False def check(P, Pindex, DP_rarity, file2save): if P.x % (DP_rarity) == 0: file = open(file2save,'a') file.write(('%064x %d'%(P.x,Pindex)) + "\n") file.close() return comparator() else: return False P = [PG] for k in range(255): P.append(mul2(P[k])) print 'P-table prepared' def search(): global solved DP_rarity = 1 << ((problem - 2*kangoo_power)/2 - 2) hop_modulo = ((problem-1) / 2) + kangoo_power T, t, dt = [], [], [] W, w, dw = [], [], [] for k in range(Nt): t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))#-(1 << (problem - 2)) ) T.append(mulk(t[k])) dt.append(0) for k in range(Nw): w.append(random.randint(1, (1 << (problem - 1)))) W.append(add(W0,mulk(w[k]))) dw.append(0) print 'tame and wild herds are prepared' oldtime = time.time() starttime = oldtime Hops, Hops_old = 0, 0 t0 = time.time() oldtime = time.time() starttime = oldtime while (1): for k in range(Nt): Hops += 1 pw = T[k].x % hop_modulo dt[k] = 1 << pw solved = check(T[k], t[k], DP_rarity, "tame.txt") if solved: break t[k] += dt[k] T[k] = add(P[pw], T[k]) if solved: break for k in range(Nw): Hops += 1 pw = W[k].x % hop_modulo dw[k] = 1 << pw solved = check(W[k], w[k], DP_rarity, "wild.txt") if solved: break w[k] += dw[k] W[k] = add(P[pw], W[k]) if solved: break t1 = time.time() if (t1-t0) > 5: print '%.3f h/s'%((Hops-Hops_old)/(t1-t0)) t0 = t1 Hops_old = Hops hops_list.append(Hops) print 'Hops:', Hops return 'sol. time: %.2f sec' % (time.time()-starttime) problems = [\ ('029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a',16),\ ('036ea839d22847ee1dce3bfc5b11f6cf785b0682db58c35b63d1342eb221c3490c',24),\ ('0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69',32),\ ('03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4',40),\ ('025e466e97ed0e7910d3d90ceb0332df48ddf67d456b9e7303b50a3d89de357336',44),\ ('026ecabd2d22fdb737be21975ce9a694e108eb94f3649c586cc7461c8abf5da71a',45),\ ('03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6',50),\ ('0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b',65),\ ('03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b',105)] problem = 32 for elem in problems: s, n = elem if problem == n: break kangoo_power = 3 Nt = Nw = 2**kangoo_power X = int(s, 16) Y = X2Y(X % (2**256)) if Y % 2 != (X >> 256) % 2: Y = modulo - Y X = X % (2**256) W0 = Point(X,Y) starttime = oldtime = time.time() search_range = 2**(problem-1) Hops = 0 random.seed() hops_list = [] N_tests = 3 for k in range(N_tests): solved = False open("tame.txt",'w').close() open("wild.txt",'w').close() search() M = sum(hops_list)*1.0 / len(hops_list) D = sum((xi - M) ** 2 for xi in hops_list)*1.0 / len(hops_list) print M, '+/-', (D / (len(hops_list)-1))**0.5 print 'Average time to solve: %.2f sec' % ((time.time()-starttime)/N_tests)

• Quote

Administrator

niidt:

---

out of the box is your code looking for problem 32? How to add other problems? Sorry, I'm new to this.

• Quote

Administrator

Look at the transaction dated 31.05.2019:

https://www.blockchain.com/btc/tx/17e4e3...1b4b65717a4b3d3

There are small outputs from wallets with 0.65, 0.70,..., 1.6 BTC. Each of output transfers is signed, and you can find details at bottom of the page. For each output we see something like:
ScriptSig: PUSHDATA(71)[304402201e8ad3749c24db4ae05de85ee2ec33277688630f97f8ce4f883fa36c6e193d3a02202f66ac26be1b44df871473a42c5e8e2cbc703465e415b064dc4854b1d8b3c99f01] PUSHDATA(33)[03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b]

The field PUSHDATA(33) contains X-coordinate (hex) of EC-point in compressed form, and this is exactly we need for our Python code. This point P corresponds to the secret key of wallet: P = secret * G, where G is generator point and (*) means scalar multiplication in EC-group.

/// продолжу писать на английском, раз уж всех зазвал сюда

• Quote

Administrator

niidt:

---

At what point does your code start searching?
With the first key 00000000000000000000000000000000000000000000000000000000000000000000000000000001?
And for example, you can not specify a range?

• Quote

Administrator

rex12:

---

Не,почему.можно и на русском.Зазвал не только англичан.вот у нас в группе возник вопрос что вроде люди уперлись в границу 255 бит в попытке переделать код, а 256 не работает.Ведь в основном нам известен только публичный ключ а не пространство приватного ключа.

• Quote