2015-06-03-135732.sagews

#++++++++  RSA KEY GENERATION ++++++++#
size = 512 #mod size
p = random_prime(2**(size/2),lbound=2**(size/2-1)+2**(size/2-2))
q = random_prime(2*p,lbound=p+1)
#forced p<q<2p, print sizes
print "p size: {:d}".format(p.nbits())
print "q size: {:d}".format(q.nbits())
N = p*q
print "N size: {:d}".format(N.nbits())
 
#++++++++  SETUP KNOWN BITS ++++++++#
knownbits= 134 #the bound is 128 BUT good luck in computing LLL in reasonable time, I use 134 since it's fast
 
sizep=p.nbits()
#p_msb is acutally (p_msb)*2**(sizep-knownbits/2)
p_msb = (p >> (sizep-knownbits/2)) << (sizep-knownbits/2)
p_lsb = p % (2**(knownbits/2))
 
#print sizes
print "p_msb size: {:d}".format( (p >> (sizep-knownbits/2)).nbits() )
print "p_lsb size: {:d}".format(p_lsb.nbits())
 
#++++++++  COPPERSMITH ++++++++#
#we need to define an polynomial == 0 (mod p) that gives us the missing part (x)
# that is:
# f_p(x) = x*2**(knownbits/2) + p_msb + p_lsb
# it's not monic so we need to divide by 2**(knownbits/2)
# set R = 2**(knownbits/2) and invert it modulo N
 
R = 2**(knownbits/2)
invR = inverse_mod(R,N)
 
#Now setup coppersmith
F.<x> = PolynomialRing(Zmod(N))
#define the poly in x modulo p
f = x + (p_msb+p_lsb)*invR
#solve it
x0 = f.small_roots(X=2^(sizep-knownbits)-1, beta=0.44, epsilon=1/64)[0]
#Note: I used beta=0.44 instead of .5 because it's faster, don't know why.
#note: if you reduce epsilon up to 1/512 you will be able to reduce knownbits up to 128
 
print "p    : {:x}".format(p)
print "p_msb: {:x}".format(p_msb)
print "p_lsb: {:x}".format(p_lsb)
#print "R    : {:x}".format(R)
print "found small root: {:x}".format(Integer(x0))
print "reconstructed p: {:x}".format(Integer(x0*R)+p_msb+p_lsb)
print "Is it equal to p ??  %s" %(Integer(x0*R)+p_msb+p_lsb == p)

p size: 256 q size: 257 N size: 513 p_msb size: 67 p_lsb size: 66 p : e1d10bb740715b3b3d277397a44957cac8db960ac6a6e3fa4fd361e4c0ce7f31 p_msb: e1d10bb740715b3b200000000000000000000000000000000000000000000000 p_lsb: 24fd361e4c0ce7f31 found small root: 3a4ee72f4892af9591b72c158d4dc7f reconstructed p: e1d10bb740715b3b3d277397a44957cac8db960ac6a6e3fa4fd361e4c0ce7f31 Is it equal to p ?? True