Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# RSA Attack: gived part of p, find the remaining part

By: a guest on Jul 9th, 2014  |  syntax: Python  |  size: 1.75 KB  |  views: 267  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #++++++++  RSA KEY GENERATION ++++++++#
2. size = 512 #mod size
3. p = random_prime(2**(size/2),lbound=2**(size/2-1)+2**(size/2-2))
4. q = random_prime(2*p,lbound=p+1)
5. #forced p<q<2p, print sizes
6. print "p size: {:d}".format(p.nbits())
7. print "q size: {:d}".format(q.nbits())
8. N = p*q
9. print "N size: {:d}".format(N.nbits())
10.
11. #++++++++  SETUP KNOWN BITS ++++++++#
12. knownbits= 134 #the bound is 128 BUT good luck in computing LLL in reasonable time, I use 134 since it's fast
13.
14. sizep=p.nbits()
15. #p_msb is acutally (p_msb)*2**(sizep-knownbits/2)
16. p_msb = (p >> (sizep-knownbits/2)) << (sizep-knownbits/2)
17. p_lsb = p % (2**(knownbits/2))
18.
19. #print sizes
20. print "p_msb size: {:d}".format( (p >> (sizep-knownbits/2)).nbits() )
21. print "p_lsb size: {:d}".format(p_lsb.nbits())
22.
23. #++++++++  COPPERSMITH ++++++++#
24. #we need to define an polynomial == 0 (mod p) that gives us the missing part (x)
25. # that is:
26. # f_p(x) = x*2**(knownbits/2) + p_msb + p_lsb
27. # it's not monic so we need to divide by 2**(knownbits/2)
28. # set R = 2**(knownbits/2) and invert it modulo N
29.
30. R = 2**(knownbits/2)
31. invR = inverse_mod(R,N)
32.
33. #Now setup coppersmith
34. F.<x> = PolynomialRing(Zmod(N))
35. #define the poly in x modulo p
36. f = x + (p_msb+p_lsb)*invR
37. #solve it
38. x0 = f.small_roots(X=2^(sizep-knownbits)-1, beta=0.44, epsilon=1/64)[0]
39. #Note: I used beta=0.44 instead of .5 because it's faster, don't know why.
40. #note: if you reduce epsilon up to 1/512 you will be able to reduce knownbits up to 128
41.
42. print "p    : {:x}".format(p)
43. print "p_msb: {:x}".format(p_msb)
44. print "p_lsb: {:x}".format(p_lsb)
45. #print "R    : {:x}".format(R)
46. print "found small root: {:x}".format(Integer(x0))
47. print "reconstructed p: {:x}".format(Integer(x0*R)+p_msb+p_lsb)
48. print "Is it equal to p ??  %s" %(Integer(x0*R)+p_msb+p_lsb == p)
clone this paste RAW Paste Data
Top