Want more features on Pastebin? Sign Up, it's FREE!
Guest

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

By: a guest on Jul 9th, 2014  |  syntax: Python  |  size: 1.75 KB  |  views: 211  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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