The idea of making one of your own encryption algorithms public on the internet seems very strange at first. However, this is acutally one of the most important steps in RSA encryption. If Person C intercepts your message to Person B, they already know the encryption key (exponent e, modulus n). However, what he/she doesn't have is the decryption exponent d. Since you encrypted your message with Person B's encryption key, only Person B has the decryption key (exponent d, modulus n) to decrypt it. Person C is only missing one piece of information, exponent d, which turns out to be the hardest piece of information to find. Person C also knows that de ≡ 1 (mod ϕ(n)), or de ≡ 1 (mod (p - 1)(q - 1)). Since he/she knows that n = pq, the simplest way to find n would be to somehow factor n into the exact primes used by Person B in the algorithm. From there, he/she could simply calculate the congruence to find d. With larger (which are more secure) primes, this turns out to be nearly impossible to do. If p = 7717 and q = 7919, n would be 61110923. If we let e = 5, then all Person C knows is e = 5, n = 61110923. Clearly, it would take very long to factor n, but imagine what would happen if p = 982451653, q = 961748941. Then n would be 944871836856449473. Now factoring n is basically impossible to do by hand. However, even this value of n is smaller than most values of n used in RSA Encryption. It took 290 computers over the internet and a supercomputer 4 months to find that `n = 1094173864157052742180970732204035761200373294544920599091384213147634` `Proof of the RSA Algorithm`
1. http://certauth.epfl.ch/CA/rsa/node3.html |