Coppersmith's method when the most significant digits of a prime are unknown¶

In [1]:
# First, we generate two random primes
p = random_prime(2^512)
q = random_prime(2^512)

# Next, we combine them to form the public part of RSA keypair
n = p*q

# Instead of what we usually do, now we only give the bottom 512-160 bits. This is 11/16 bits.
a = p % 2^(512-160)
hex(p), hex(a)
Out[1]:
('0xa41a269c440628dab28ae06a856851797b69309eb5af35be8ce93a795c9cbd3fdb36a5727ea264390424a67a7951e4b943d844a7614d59aa9f397b06a09e3c77',
 '0xb5af35be8ce93a795c9cbd3fdb36a5727ea264390424a67a7951e4b943d844a7614d59aa9f397b06a09e3c77')
In [2]:
# The upper bound on the missing part, which consists of 160 bits
X = 2^160
In [3]:
# We have that 512-160 bits are known, so the missing part start from the bits that correspond to 2^(512-160) and higher
x_base = 2^(512-160)
hex(x_base)
Out[3]:
'0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
In [4]:
# The matrix is constructed quite similarly to the one used when finding a stereotyped message;
# Every polynomial is divided by x_base so that the leading coefficient becomes monic.
# This division takes the inverse of x_base mod n. 
M = matrix([
    [int(Zmod(n)(x_base/x_base))*X^2, int(Zmod(n)(a/x_base))*X, 0],
    [0, int(Zmod(n)(x_base/x_base))*X, int(Zmod(n)(a/x_base))],
    [0, 0, n]
])
In [5]:
# First, we apply the LLL algorithm to the matrix.
B = M.LLL()

# Next, we take a look at the first row vector of the output matrix.
B[0]
Out[5]:
(-48647816849703067569002253412570650721907565372226689986396655764528307562321198238015877803913742984914766842444043007242320225185035525019066695680, 40592521010112230013859798575530085394575375069071707611673272059485305501356125261930982510597195410783693915742000733451817786428416887366315147264, -6030819078333390986925894708338928212776022218925137890311345013024679821661013144904733538907316473294443576214480332826474426282934086025629062670)
In [6]:
# We define the polynomial, like we usually do.
Q = B[0][0]*x^2/X^2 + B[0][1]*x/X + B[0][2]
Q
Out[6]:
-22775333385265156080221072073390961152184476849368430*x^2 + 27774529958273017657202657176204019276058812194934508331733698221244680057504435812617003775612994989*x - 6030819078333390986925894708338928212776022218925137890311345013024679821661013144904733538907316473294443576214480332826474426282934086025629062670
In [7]:
Q.roots(ring=ZZ)
Out[7]:
[(936857669231605610849593682414616437482597200030, 1)]
In [8]:
Q.roots(ring=ZZ)[0][0]
Out[8]:
936857669231605610849593682414616437482597200030
In [9]:
# We compute the solution.
# This requires multiplying the found root with x_base, then adding a (effectively, in a sense, we are computing the value of the original polynomial f(x) = a + x_base*x )
solution = x_base * Q.roots(ring=ZZ)[0][0] + a
hex(solution)
Out[9]:
'0xa41a269c440628dab28ae06a856851797b69309eb5af35be8ce93a795c9cbd3fdb36a5727ea264390424a67a7951e4b943d844a7614d59aa9f397b06a09e3c77'
In [10]:
# Let's check whether the solution corresponds to the prime we started with
solution == p
Out[10]:
True