Dual_EC_DRBG backdoor: a proof of concept(blog.0xbadc0de.be)

    n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    p = 2^256 - 2^224 + 2^192  + 2^96 - 1
    a = -3
    b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
    E = EllipticCurve(GF(p), [a,b])
    P = E(48439561293906451759052585252797914202762949526041747995844080717082404635286, 
          36134250956749795798585127919587881956611106672985015071877198253568414405109)
    """
    Q = E(91120319633256209954638481795610364441930342474826146651283703640232629993874, 
          80764272623998874743522585409326200078679332703816718187804498579075161456710)
    """
    e = 0x12345678
    ei = inverse_mod(e, n)
    Q = e*P

    def to_bin(x): return ("%060x" % x).decode('hex')

    def from_bin(x): return int(x.encode('hex'), 16)

    def dual_ec_drbg(s, len):
        out = ''
        for i in range(0, len, 30):
            x, y = (s*P).xy()
            s = Integer(x)
            x, y = (s*Q).xy()
            r = Integer(x) % 2**240
            out += to_bin(r)
        return out[0:len]

    def recover_s(s0, s1):
        for i in range(2**16):  # For all possible 256-bit x
            r = i*2**240 + s0   # 
            if E.is_x_coord(r): # is valid x?
                R = E.lift_x(r) # Lift it to a point
                x, y = (R*ei).xy() # Undo s*Q
                s = Integer(x)
                x, y = (s*Q).xy() # Check if it matches next observed block
                if (Integer(x) % 2**240) == s1: 
                    return s # done
        return None

    import os
    # Get 3 blocks: 2 are for the break, the other to confirm prediction
    s = dual_ec_drbg(from_bin(os.urandom(16)), 30*3)
    s0 = from_bin(s[ 0:30])
    s1 = from_bin(s[30:60])
    s2 = from_bin(s[60:90])
    # Recover internal state
    s = recover_s(s0, s1)
    # Now try predicting something
    t = dual_ec_drbg(s, 30)
    assert( from_bin(t) == s2 )
    print "Done"