RSA is a public encryption scheme. Its security assumptions are based on complexity theory: computing the product of two prime numbers is easy (polynomial time), but there is no efficient algorithm for factoring them back (so far, all factorization methods are in the non-polynomial class).
The keys for the RSA algorithm are generated the following way:
1. Choose two different large random prime numbers p and q
2. Calculate n = pq
n is the modulus for the public key and the private keys
3. Calculate the totient: phi =(p-1)(q-1).
4. Choose an integer e such that 1 < e < phi, and e is coprime to phi
e is released as the public key exponent
5. Compute d to satisfy the congruence relation d*e ≡ 1 mod phi (the remainder of d*e / phi is 1)
d is kept as the private key exponent
The public key is made of the modulus n and the public (or encryption) exponent e.
The private key is made of the modulus n and the private (or decryption) exponent d which must be kept secret.
Encrypting a message: c = m ^ e (mod n)
Decrypting a message: m = c ^ d (mod n)
p = 29, q = 31
n = p * q = 29 * 31 = 899
phi = (p -1) * (q – 1) = (29 – 1) * (31 – 1) = 840
e = 11
d * e ≡ 1 mod phi => (d * 11) / phi will give us a remainder of one.
(611 * 11) = 6721 and 6721 / 840 = 8 with remainder 1 => d = 611
C = M^e mod n
C = 119^11 mod 899 = 595
M = C^d mod n
M = 595^611 mod 899 = 119
Problem 1: Decrypting RSA with Known factorization
You have the ciphertext as follows. In order to decrypt it, you need to factorize n into p and q, compute phi and find d.
Then we can find the original message m.
c = 28822365203577929536184039125870638440692316100772583657817939349051546473185
n = 70736025239265239976315088690174594021646654881626421461009089480870633400973
e = 3
1. you can do known factorization here: http://www.factordb.com.
2. Useful gmpy2 functions:
invert(e, phi) returns d such that d * e == 1 modulo phi, or 0 if no such y exists.
powmod(x, y, n) returns (x^y mod n).
mul(x,y) returns x * y.
Problem 2: Decrypting RSA with Fermat Factorization
Implement and try out Fermat's Factorization Algorithm! Then try to break the following RSA key and obtain the original message m.
c = 6545641259678115729576084854615092235417811978956089202968254
n = 1209143407476550975641959824312993703149920344437422193042293
e = 65537
Note: Useful gmpy2 functions
• is_square(x) returns True if x is a perfect square, False otherwise.
• isqrt(x) returns the integer square root of an integer x. x must be >= 0.
This assignment has been answered 3 times in private sessions.
© 2021 Codify Tutor. All rights reserved