Menu
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
688
Primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse.
The recommended RSA modulus size for most settings is 2048 bits to 4096 bits. Thus, the primes to be generated need to be 1024 bit to 2048 bit long.
The central importance of prime numbers to number theory and mathematics in general stems from the fundamental theorem of arithmetic. This theorem states that every integer larger than 1 can be written as a product of one or more primes.
RSA relies on the relative ease of finding large primes and the comparative difficulty of factoring integers for its security. To use this system we first find two large primes p and q and form their product n = pq. Next we choose a random integer e which is relatively prime to (p-1)( q-1) (this is phi(n)).
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.
97
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
