Topic: Pollard's kangaroo ECDLP solver - page 11. (Read 58537 times)

import time
import random
import gmpy2
from functools import lru_cache

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

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    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):
    dx = Q.x - P.x
    dy = Q.y - P.y
    #c = (dy * pow(dx, -1, p)) % p
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
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
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

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 search(Nt, Nw, problem, kangoo_power, starttime):
    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))))
        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()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        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", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        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", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power
X = int(compreessed_public_key, 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()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

for k in range(N_tests):
    with open("tame.txt", 'w') as tame_file, open("wild.txt", 'w') as wild_file:
        tame_file.write('')
        wild_file.write('')
    search_result = search(Nt, Nw, problem, kangoo_power, starttime)
    print(search_result)
    M, D = 0, 0
    if len(hops_list) > 0:
        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))