Question

Describe how RSA works. In your own words.

Why do we believe RSA is secure? What techniques are used to perform cryptanalysis on RSA?

Answer 1

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 npq, 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 n61110923. Clearly, it would take very long to factor n, but imagine what would happen if p 982451653, q961748941 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 n109417386415785274218970732284035761200373294544920599091384213147634 9984288934784717997257891267332497625752899781833797876537244827146743 531593354333897 Had prime factors p102639592829741105772054196573991675900716567888038066803341933521790711307779, q - 196603488380168454820927229368012878679207958575989291522270608237193062808643 . In this case n had only 155 digits. Many values of n have over 280 digits, making the RSA algorithm nearly unbreakable