Why are "large prime numbers" used in RSA/encryption?
I've learned the theory of public key encryption but I'm missing the connection to the physical world. e.g.
I've been told that good RSA encryption should rely on prime numbers with 300 decimal digits but why? who came up with this number? How long it will take to break such encryption (statistics about different machines).
I've tried Google, but couldn't find what I wanted. anyone?
thanks
Answer
The key of asymmetric cryptography is to have an asymmetric function which allow decrypting message encrypted by the asymmetric key, without allowing to find the other key. In RSA, the function used is based on factorization of prime numbers however it is not the only option (Elliptic curve is another one for example).
So, basically you need two prime numbers for generating a RSA key pair. If you are able to factorize the public key and find these prime numbers, you will then be able to find the private key. The whole security of RSA is based on the fact that it is not easy to factorize large composite numbers, that's why the length of the key highly change the robustness of the RSA algorithm.
There are competitions to factorize large prime numbers with calculators each years with nice price. The last step of factorizing RSA key was done in 2009 by factorizing 768 bits keys. That's why at least 2048 bit keys should be used now.
As usual, Wikipedia is a good reference on RSA.