Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #from https://crypto.stackexchange.com/questions/48006/encrypting-a-small-value-m-in-1-dots-100-using-textbook-rsa
- #Generate RSA Key (not all security checks are done)
- def genRSAkey(e,N_BITS):
- e = ZZ(e)
- while True:
- q = ZZ(random_prime(2^(N_BITS/2)-1, proof=False, lbound = ceil(sqrt(2) * 2^(N_BITS/2-1)) ))
- p = ZZ(random_prime(2^(N_BITS/2)-1, proof=False, lbound = ceil(sqrt(2) * 2^(N_BITS/2-1)) ))
- N = p*q
- if (N.nbits() != N_BITS):
- continue
- phi_n = (p-1) * (q-1)
- if (phi_n % e == 0):
- continue
- d = inverse_mod(e,phi_n)
- return(N,d)
- #Basic GCD which should work if "%" is implemented
- def composite_poly_gcd(a,b):
- while b != 0:
- r = a % b
- a=b
- b=r
- return a
- #Generate Key
- e = 17
- N,d = genRSAkey(e,512)
- #Generate Random x
- x = ZZ(randint(0,N-101))
- #Generate secret message m
- m = ZZ(randint(0,100))
- #Encrypt x and x+m
- c1 = power_mod(x,e,N)
- c2 = power_mod(x+m,e,N)
- #Define our univariate polynomial ring in y
- PolyRing.<y> = PolynomialRing(IntegerModRing(N))
- print "We want to find message m =", m, "and random x =", x
- #Solve
- for i in range(101):
- result = composite_poly_gcd(y^e-c1,(y+i)^e-c2)
- if result.degree() == 1:
- print "We have a solution! it is:"
- print "m =", i, "x =", -(result*inverse_mod(ZZ(result.leading_coefficient()),N)).constant_coefficient()
- break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement