UIUCTF'17 bulljog

bulljog.sage

from multiprocessing import Process, Lock
from grocid.ecc import hensellift
NUM_THREADS = 28 # lets make some use of my 2695 ;-)

def smart_attack(P, Q, p, prec):
    E = P.curve()
    Eqq = E.change_ring(QQ)
    Eqp = Eqq.change_ring(Qp(p, prec))
    P_Qp = hensellift(P, p, prec) # just normal hensel lift
    Q_Qp = hensellift(Q, p, prec)
    x_P, y_P = (p * P_Qp).xy()
    x_Q, y_Q = (p * P_Qp).xy()
    k = -(x_P / y_P) / -(x_Q / y_Q)
    k = Mod(k, p)
    return k

def prng(s):
    global P
    global Q
    x, y = (s * P).xy()
    s = ZZ(x)
    x, y = (s * Q).xy()
    b = hex(ZZ(x)).replace("0x", "").replace("L", "")
    b = b.zfill(nbits // 4)[-(nbits - 8) // 4:]
    return int(b, 16)

print '[ ] Finding such that d * Q = P...'
assert(ec.order() == p)
d = int(smart_attack(Q, P, p, 8))
print '[+] Found d =', d
assert(d * Q == P)
print '[ ] Finding seed...'

def f(j):
    for i in range(j, 2**8, NUM_THREADS):
        r = first_val
        guess = i * 2**(512-8) + r
        if ec.is_x_coord(guess):
            q = ec.lift_x(guess)
            s = int((d * q).xy()[0])
            r = int((s * Q).xy()[0])
            b = hex(r).replace("0x", "").replace("L", "")
            b = b.zfill(nbits // 4)[-(nbits - 8) // 4:]
            if int(b, 16) == second_val:
                print '[+] Found!', prng(s)
                break

for num in range(NUM_THREADS):
    Process(target=f, args=(num,)).start()


# flag{y_w0uld_u_w4nn4_br3ak_a_p3rf3ct1y_g00d_PRNG?}