RSAで秘密鍵dの下位bitがある程度わかっているときに使える
nのbit数の半分程度のbit数がわかっていて、 pとqが近い時に成功したりしなかったりする。MultiPrimeだともうちょっとbit数がいるっぽい。3/4くらい？
from Crypto.Util.number import getPrime, inverse
from math import gcd
import random
e = 1667
p = getPrime(1024)
q = getPrime(1024)
n = p * q
d = inverse(e, (p - 1) * (q - 1))
c1 = pow(2, e, n)
c2 = pow(3, e, n)
low_bits = 1024
low_d = d % (2 ** low_bits)
print("size of n: {}".format(n.bit_length()))
print("size of low_d: {}".format(low_bits))
for k in range(1, e + 1):
if k % 100 == 0:
print(k)
high_d = (k * n + 1) // e
high_d >>= low_bits
high_d <<= low_bits
approx_d = high_d | low_d
if pow(c1, approx_d, n) == 2 and pow(c2, approx_d, n) == 3:
print("FOUND! d={}".format(approx_d))
print(approx_d == d)
break
eが小さくてnのbit数の1/4程度のdがわかっている時
def partial_key_exposure(d_, e, n):
beta = 0.5
epsilon = beta^2/7
n_bits = n.nbits()
d_bits = floor(n_bits*(beta^2+epsilon))
d_ = d_ % (2^d_bits)
P = var('P')
for k in xrange(1, e+1):
print(k)
answers = solve_mod([e*d_*P - k*P*(n-P+1) + k*n == P], 2^d_bits)
for ans in answers:
p_ = ZZ(ans[0])
PR.<x> = PolynomialRing(Zmod(n))
f = 2^d_bits*x + p_
f = f.monic()
roots = f.small_roots(X=2^(n_bits//2-d_bits), beta=beta, epsilon=epsilon) # find root < 2^(nbits//2-d_bits) with factor >= n^0.3
if roots:
root = roots[0]
if root == 0:
continue
p = gcd(2^d_bits*root + p_, n)
return Integer(p)
