RSA with half least significant bits of d leaked (optimized for larger e)

rsa_privleak_halflsb.py

#-*- coding:utf-8 -*-

from sage.all import *

BITS = 2048
NLEAK = 1024-22
# E = 0x10001
E = next_prime(2**22)
print "E", E

# -22 bits leaked, E ~ 2**22 -> ~1 minute

# if we arrive slightly off (e.g. if less than half is given)
# probably can be improved with BSGS style for larger E (e.g. time sqrt(E + 2**(1024-NLEAK)))
PRECOMP_BITS = 22


e = E
l = NLEAK
p = next_prime(randint(1, 2**(BITS/2)), proof=False)
q = next_prime(randint(1, 2**(BITS/2)), proof=False)
n = p * q
d = inverse_mod(e, (p-1)*(q-1))
del p
del q

l = NLEAK
mask = (1 << l) - 1
hint = d & mask
del d

l = l
mask = 2**l-1
assert hint & mask == hint

dlo = hint
enc2 = int(pow(2, e, n))
dec1 = int(pow(enc2, dlo, n))
dec2 = int(pow(enc2, 2**l, n))
idec2 = inverse_mod(dec2, n)
test2 = 2 * inverse_mod(dec1, n) % n

print "precomp..."
seen = {test2: 0}
cur = test2
for i in xrange(1, 2**PRECOMP_BITS):
    cur = cur * dec2 % n
    seen[cur] = i
cur = test2
for i in xrange(1, 2**PRECOMP_BITS):
    cur = cur * idec2 % n
    seen[cur] = -i
print "done"

start = 0
e2lo = e * 2**l

phiapp = n
bigmul = pow(dec2, phiapp // e2lo, n)
big = phiapp // e2lo
small = phiapp % e2lo
rem = 0
cur = 1
exp = 0
for k in xrange(start, e):
    if k % 10000 == 0:
        print k

    if cur in seen:
        assert cur == pow(dec2, exp, n)
        assert cur == test2 * pow(dec2, seen[cur], n) % n
        assert pow(dec2, exp - seen[cur], n) * dec1 % n == 2

        d = (exp - seen[cur]) * 2**l + dlo
        print "found some d", d
        assert pow(2, e * d, n) == 2, "weird, d is wrong..."
        print "correct!"
        break

    cur = cur * bigmul % n
    exp += big
    rem += small
    while rem >= e2lo:
        rem -= e2lo
        cur = cur * dec2 % n
        exp += 1
else:
    print "fail..."