Dual_EC_DRBG_2006_with_backdoor.sagews

import hashlib
from datetime import datetime

bitmask = (2^(30*8) - 1);

#internal state
s_i = None;

#additional input
second = datetime.now().second;
microsecond = datetime.now().microsecond;
counter = 0;
pid = os.getpid();

def Dual_EC_DRBG(P, Q, h_adin=0, s_0=None):

    global s_i;

    if(s_0 == None):
        s_0 = int(floor((2^16-1)*random()));

    if(s_i == None):
        s_i = s_0;

    t_i = s_i ^^ h_adin;
    s_i = (t_i*P)[0].lift();
    r_i = (s_i*Q)[0].lift();
    r_i = r_i & bitmask;

    return r_i;

def Random_Generator(P, Q, byte, h_adin=0):

    result = 0;
    req = (byte/30).ceil();

    for i in range(req):
        if(i == 0):
            result = (result << (30*8)) | Dual_EC_DRBG(P, Q, h_adin)
        else:
            result = (result << (30*8)) | Dual_EC_DRBG(P, Q)

    result = result >> ((30*req - byte)*8)

    return result;

def Get_H_Adin():

    global second;
    global microsecond;
    global counter;
    global pid;
    second = datetime.now().second;
    microsecond = datetime.now().microsecond;
    counter = counter + 1;
    pid = os.getpid();
    adin = (second << (12*8)) | (microsecond << (8*8)) | (counter << (4*8)) | pid;
    h = hashlib.sha256();
    h.update(str(adin));
    return int(h.hexdigest(), 16);

def Predict_Current(P, Q, byte, p, b, curve, r, d):

    result = [];
    req = (byte/30).ceil();
    r_1 = r >> (len(hex(r))*4 - 30*8);
    r_2 = r & (2^(len(hex(r))*4 - 30*8) - 1);

    for i in range(2^16):
        mb = i << (30*8);
        x_cand = mb | r_1;
        y = Mod(x_cand^3 - 3*x_cand + b, p);
        if(y.is_square()):
            y_cand = y.sqrt();
            try:
                R = curve(x_cand, y_cand);
                s_cand = (d*R)[0].lift();
                r_cand = (s_cand*Q)[0].lift();
                r_cand = r_cand & bitmask;
                if((hex(r_cand).startswith(hex(r_2))) or (hex(r_2).startswith(hex(r_cand)))):
                    r = 0;
                    r = (r << (30*8)) | r_1
                    r = (r << (30*8)) | r_cand
                    for j in range(req):
                        s_cand = (s_cand*P)[0].lift();
                        r_cand = (s_cand*Q)[0].lift();
                        r_cand = r_cand & bitmask;
                        r = (r << (30*8)) | r_cand
                    r = r >> ((30*req - byte)*8)
                    result.append(r);
            except:
                continue;
    return result;

def Get_Internal_State(P, Q, p, b, curve, r, d):

    result = [];
    r_1 = r >> (len(hex(r))*4 - 30*8);
    r_2 = r & (2^(len(hex(r))*4 - 30*8) - 1);

    for i in range(2^16):
        mb = i << (30*8);
        x_cand = mb | r_1;
        y = Mod(x_cand^3 - 3*x_cand + b, p);
        if(y.is_square()):
            y_cand = y.sqrt();
            try:
                R = curve(x_cand, y_cand);
                s_cand = (d*R)[0].lift();
                r_cand = (s_cand*Q)[0].lift();
                r_cand = r_cand & bitmask;
                if((hex(r_cand).startswith(hex(r_2))) or (hex(r_2).startswith(hex(r_cand)))):
                    result.append(s_cand);
            except:
                continue;
    return result;

def Predict_Next(P, Q, byte, s_cand, h_adin):

    result = 0;
    req = (byte/30).ceil();

    for i in range(req):
        if(i == 0):
            t_cand = s_cand ^^ h_adin;
            s_cand = (t_cand*P)[0].lift();
            r_cand = (s_cand*Q)[0].lift();
            r_cand = r_cand & bitmask;
            result = (result << (30*8)) | r_cand
        else:
            s_cand = (s_cand*P)[0].lift();
            r_cand = (s_cand*Q)[0].lift();
            r_cand = r_cand & bitmask;
            result = (result << (30*8)) | r_cand

    result = result >> ((30*req - byte)*8)

    return result;

#Curve P-256
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951;
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369;
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b;
Px = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296;
Py = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5;
#Qx = 0xc97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192;
#Qy = 0xb28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046;

# y^2 = x^3 - 3*x + b (mod p)
curve = EllipticCurve(GF(p), [0, 0, 0, -3, b]);
print curve;

P = curve(Px, Py);
#Q = curve(Qx, Qy);

#Backdoor
d = 5;
order = P.additive_order();
e = inverse_mod(d, order);
#P = d*Q;
Q = e*P;

print "P = ", P;
print "Q = ", Q;

h_adin = Get_H_Adin();
print "h_adin = ", hex(h_adin);

r = Random_Generator(P, Q, 32, h_adin);
print "r = ", hex(r);

#%time rp = Predict_Current(P, Q, 120, p, b, curve, r, d);
#for i in range(len(rp)):
#    print "rp = ", hex(rp[i]);

#In case of predictable additional input
h_adin = Get_H_Adin();
print "h_adin = ", hex(h_adin);

%time s = Get_Internal_State(P, Q, p, b, curve, r, d);
for i in range(len(s)):
    print "s = ", hex(s[i]);
    %time rp = Predict_Next(P, Q, 60, s[i], h_adin);
    print "rp = ", hex(rp);

r = Random_Generator(P, Q, 60, h_adin);
print "r = ", hex(r);

Elliptic Curve defined by y^2 = x^3 + 115792089210356248762697446949407573530086143415290314195533631308867097853948*x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 over Finite Field of size 115792089210356248762697446949407573530086143415290314195533631308867097853951 P = (48439561293906451759052585252797914202762949526041747995844080717082404635286 : 36134250956749795798585127919587881956611106672985015071877198253568414405109 : 1) Q = (100222093819885759857726245131128697024676897724593576735535145416600847521071 : 112705950327624587511154978849178363127000253898669394213565898066000545039919 : 1) h_adin = 0xfd33857b6dd41a7f91d8b91fa9423ca9b0c9379d519a271e2855d4b1e3db7a9bL r = f257e6ad74ba8104659e3d94185c8eef61b50729145df38baafb127ff23b3161 h_adin = 0xcbff94d92e5bd9288a3ba9d2aa49ab7a8e139c50a5b02781490d535334161a22L CPU time: 493.43 s, Wall time: 498.76 s s = d671450d17816710250f7b2dff65f99df1d6fc91c1b478ea9753fe7719006cb1 CPU time: 0.06 s, Wall time: 0.06 s rp = 64cd366aca897eb09d7adec942404b0b11817f9f33457d1a40c54e4cb9a79592d9adbed1804bd4cf66652562294a0b9f54dbd6979390170311ef881c r = 64cd366aca897eb09d7adec942404b0b11817f9f33457d1a40c54e4cb9a79592d9adbed1804bd4cf66652562294a0b9f54dbd6979390170311ef881c