cry1000.py

import sys
from BSecure import *
from Crypto.Hash import MD5
from Crypto.Cipher import AES
from multiprocessing import Pool, cpu_count

p_check = MD5.new()
p_check.update(hex(Rx)[2:-1])
print "Px == MD5(Rx): %s" % (p_check.hexdigest() == hex(Px)[2:-1])

q_check = MD5.new()
q_check.update(hex(Px)[2:-1])
print "Qx == MD5(Px): %s" % (q_check.hexdigest() == hex(Qx)[2:-1])

encflag = "4900e88f0093bb67c29e7f1b76f8eb0b6ebc40449149c7adbc4f87190f0bb6663f749ec516a498c0e8eddfca963b3a9a287ee2140607".decode('hex')
iv = encflag[:16]
ct = encflag[16:]
x = int(iv.encode('hex'), 16)
# https://crypto.stackexchange.com/questions/6777/how-to-calculate-y-value-from-yy-mod-prime-efficiently
y = pow(( x * x * x + E.a() * x + E.b()), inverse_mod(2, (p-1)/2), p)
point = Point(E, x, y)
print "initial_state*Q: %s" % point

""" Sage code
# Field
F=GF(0xfffffffdffffffffffffffffffffffffL)
# Curve
E=EllipticCurve(F, [0xd6031998d1b3bc232559cc9bbff9aee1L, 0x5eeefca380d0295e442c6558bb6d8a5dL])
# Points
r=E.point([0x4ca91fe907c82a68a7cf562a2b55d436L, 0xf86a643915962ae0bbbb77b9f4a9be80L])
q=E.point([0x6eb63b8498d108459ea891cbcb8319e4L, 0x2d19b5f118bbb6978fc24cc56ef8085bL])
p=E.point([0xe86b0b81c54bcd9b32ec5bac4c508a6eL, 0x4f426faded3ca290eb0bf3c8f65e6b9bL])
i=E.point([0x4900e88f0093bb67c29e7f1b76f8eb0bL, 0xbc7be32c50b2ae3a962f24da4e8dd003L])
# Results
initial_state = discrete_log(i, q, ord=None, operation='+')
nsa_backdoor = discrete_log(q, p, ord=None, operation='+')
r_order = r.order()
"""
initial_state = 182351562652272413624054983759866017253
nsa_backdoor = 301486798690386462368937329302388582917
r_order = 359

assert initial_state*Q == point
assert nsa_backdoor*P == Q

class BSecure_rng( BSecure_rng ):
    def __init__(self):
        self.r = 0
        self.state = 0

    def step( self ):
        rnd = (self.state*Q).x()
        t1 = self.r*R
        t2 = self.state*P
        self.state = (t1 + t2).x()
        return ('%032x' % rnd).decode('hex')

state1_list = []
rng1 = BSecure_rng()
done = 0
for r1 in xrange(0, r_order+1):
    rng1.state = initial_state
    rng1.r = r1
    assert iv == rng1.get_random(16)
    state1_list.append(rng1.state)
    sys.stdout.write("\rLoading jobs.... %i%%" % ((100*done)/r_order))
    sys.stdout.flush()
    done += 1
print

def find_key(state1):
    rng2 = BSecure_rng()
    for r2 in xrange(0, r_order+1):
        rng2.state = state1
        rng2.r = r2
        key = rng2.get_random(32)
        if(AES.new(key, AES.MODE_CFB, iv).decrypt(ct[:4]) == 'HITB'):
            return key
    return False

pool = Pool(cpu_count())
result = pool.imap(find_key, state1_list)
done = 0
key = False
while not key:
    sys.stdout.write("\rFinding key.... %i%%" % ((100*done)/r_order))
    sys.stdout.flush()
    key = result.next()
    done += 1
print
print "Key: %s" % key.encode('hex')
print "Flag: %s\n" % AES.new(key, AES.MODE_CFB, iv).decrypt(ct)

The output:

$ python dec.py 
Px == MD5(Rx): True
Qx == MD5(Px): False
initial_state*Q: (97038360541132742541370619789584165643,250538123339157959815142162557309931523)
Loading jobs.... 100%
Finding key.... 48%
Key: d86f76cad793ba6828b3f6da22b1301a76c255ac88cbdbdbdcc454568aa359cf
Flag: HITB{c4bd9f693a210a8f30f7faa9cfaedd66}