Advertisement
Guest User

Untitled

a guest
Jun 7th, 2017
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.42 KB | None | 0 0
  1. #from https://crypto.stackexchange.com/questions/48006/encrypting-a-small-value-m-in-1-dots-100-using-textbook-rsa
  2.  
  3. #Generate RSA Key (not all security checks are done)
  4. def genRSAkey(e,N_BITS):
  5.     e = ZZ(e)
  6.     while True:
  7.       q = ZZ(random_prime(2^(N_BITS/2)-1, proof=False, lbound = ceil(sqrt(2) * 2^(N_BITS/2-1)) ))
  8.       p = ZZ(random_prime(2^(N_BITS/2)-1, proof=False, lbound = ceil(sqrt(2) * 2^(N_BITS/2-1)) ))
  9.       N = p*q
  10.       if (N.nbits() != N_BITS):
  11.           continue    
  12.       phi_n = (p-1) * (q-1)
  13.       if (phi_n % e == 0):
  14.           continue
  15.       d = inverse_mod(e,phi_n)
  16.       return(N,d)
  17.  
  18. #Basic GCD which should work if "%" is implemented      
  19. def composite_poly_gcd(a,b):
  20.     while b != 0:
  21.         r = a % b
  22.         a=b
  23.         b=r
  24.     return a
  25.  
  26. #Generate Key
  27. e = 17
  28. N,d = genRSAkey(e,512)
  29. #Generate Random x
  30. x = ZZ(randint(0,N-101))
  31. #Generate secret message m
  32. m = ZZ(randint(0,100))
  33. #Encrypt x and x+m
  34. c1 = power_mod(x,e,N)
  35. c2 = power_mod(x+m,e,N)
  36.  
  37. #Define our univariate polynomial ring in y
  38. PolyRing.<y> = PolynomialRing(IntegerModRing(N))
  39.  
  40. print "We want to find message m =", m, "and random x =", x
  41. #Solve
  42. for i in range(101):
  43.     result = composite_poly_gcd(y^e-c1,(y+i)^e-c2)
  44.     if result.degree() == 1:
  45.         print "We have a solution! it is:"
  46.         print "m =", i, "x =", -(result*inverse_mod(ZZ(result.leading_coefficient()),N)).constant_coefficient()
  47.         break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement