RSA

This exercise generator creates questions about the details of RSA encryption/decryption.
For some of the problems (where the numbers are fairly large), you should have access, in another browser window, to a modular arithmetic calculator (google it). If the numbers aren't too large, you should be able to do the work without a calculator.
.



Enter an integer in the field below, then click the "Submit" button. Do not place commas in the number.






Click "refresh" or "reload" to see another problem like this one.

Click here to get a clue

































































































































































































































































































































































































































































































































































































































































































































































































































































































SOLUTION



Summary of RSA cryptography:
We have two large primes, p and q (hundreds of digits in length, unlike the small primes used in this demo).
These two primes are kept secret. Our public modulus is m = pq.
Factoring m to find p and q is computationally infeasible, because p, q and m are so large.
Our private modulus is n = (p − 1)(q − 1).
Our encryption key e is any integer relatively prime to e mod n. Our decryption key d is the multiplicative inverse of e mod n. Our message is an integer M < m.
Our encrypted message is C, where C = Me mod m.
Although any spy can see our encrypted message C = Me mod m, and knows the values of e and m, solving the discrete log equation C = Me mod m to find M is not computationally feasible because the numbers are too large.

To decrypt the encrypted message, we raise it to the d power and reduce mod m.
Decrypted message: Cd mod m = (Me)d mod m = M.

The public modulus m, the encrypted message C = Me mod m, and the encryption key e are all public information.
The encrypted message cannot be deciphered without the decryption key d, which is secret.
In order to find the decryption key d, a spy would first need to find the private modulus n.
In order to find n, a spy would need to know our primes p and q, but that would require factoring m, which is beyond the limits of current computing technology.

The math that makes this all possible is this variation of Fermat's Little Theorem:
Let p, q be primes, let m = pq, and let n = (p − 1)(q − 1).
If e is relatively prime to n and d is the inverse of e mod n, then
(ae)d mod m = a for any positive integer a < m.


Return

Copyright 2015, James Wooland.
All rights reserved.
Not to be distributed for commercial purposes.