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.
Copyright 2015, James Wooland.
All rights reserved.
Not to be distributed for commercial purposes.