Why RSA Encryption is secure

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
9984288934784717997257891267332497625752899781833797076537244027146743
531593354333897

Had prime factors

p = 102639592829741105772054196573991675900716567808038066803341933521790711307779,
q = 106603488380168454820927220360012878679207958575989291522270608237193062808643.

In this case n had only 155 digits. Many values of n have over 200 digits, making the RSA algorithm nearly unbreakable.
Proof of the RSA Algorithm

References
1.  http://certauth.epfl.ch/CA/rsa/node3.html
Comments