Hello! I just have a couple quick questions, that hopefully someone can quickly answer!

1. In RSA Cryptography just how large of prime numbers do you need for it to be secure? 16-bit? 64-bit? 1024-bit? 8192-bit?

2. In common RSA implementations they offer varying key-sizes, ranging up to about 8192-bits. When they mean key-size, is the entire key generated from several large, 8192-bit prime numbers resulting in a 8192-bit key (one for each element, d, e, and n). OR, is it simply several smaller keys that collectively add up to 8192-bits, then is treated like a block-cipher? (like 256 32-bit primes totaling at a key of 8192-bits).

I have successfully implemented a nice working test-case scenario using 16-bit primes, but wonder if I need to implement a BigNumber class to support larger prime numbers for more security, or if I can just create a block-cipher style key that's composed of several 64-bit key elements.

3. If I do need to increase the bit-size of the primes, are there any good algorithms out there for fast RSA-key generation? Heck, with maximum hand-coded optimizations a 16-bit key-generator implemented the obvious way takes 10-30 seconds to generate a single key... xD

4. Is it possible to keep RSA from encoding to a larger bit-size? For example, encoding a 16-bit variable with a 16-bit key results in a 32-bit encoded variable. This is much less than desirable. OR, am I doing something wrong, and RSA does encode to the same bit-size?

5. Only about 4.7% of the numbers from 0 to 2^32 are prime, reducing the number of possible keys from 4,294,967,295 to about 203,280,220 for 32-bit keys. On a symmetrical algorithm that would effectively reduce the security by ~95.3%. With that said, is RSA secure at all?!?

Thanks beforehand!

[Edited by - Conoktra on November 9, 2010 2:26:05 PM]

You seem to have some pretty big gaps left in your understanding of RSA and what makes it secure. Since you have managed to make it work with tiny primes, you probably understand the basic behavior, so I won't describe it.

The method works because it's easy to generate large prime numbers, but it's hard to factor the product of two such primes. For it to be secure, you need to use prime numbers that are large enough that their product won't be easy to factor. The quadratic sieve is one of the best factorization algorithms known, and it has been used to factor numbers of the order of 10^135, so I would suggest never using prime numbers smaller than 100 digits each. The product of two 100-digit numbers is a 200-digit number, which is about 665 bits long. I believe the number typically quoted as the length of an RSA key is the size of M, so 1024 bits seems OK. 8192 bits will likely be safe for a very long time.

You definitely need to use a bignum library for this. GMP works just fine, and it even provides a function to compute pow(a,b)%c, which is exactly what you need.

Generating 16-bit prime numbers shouldn't take 30 seconds. If it takes 30 milliseconds you are probably still doing it wrong. Primality testing is quick to check. I suggest you look into the probabilistic Miller-Rabin test, which can find enormous primes in a few seconds.

For RSA to be secure it is important that p and q are of similar size, that p-1 and q-1 don't have only small factors and perhaps other things I am forgetting.

I haven't looked at these things in over 10 years, so perhaps you should do some more reading in case some of what I said is outdated or just incorrect. But I think this post should help you develop some sense for the order of magnitude of things.

Thank you! That answered several of my questions. It looks like I just need to implement a BigNumber library and do those massive 1024+ modular exponentiations.

I am pretty sure your post was more helpful than anything else I've read on the subject, so thank you! (I'll be sure to double-check too :P)

To answer question 5: Factorizing a 32-bit number is trivial. You only need to check for divisibility with primes up to sqrt(2^32) = 65536, which is obviously going to be very quick. However linearly increasing the number of bits exponentially increases the difficulty of the factorization - to factorize a 64-bit number needs you to test all primes below 2^32 (ignoring the more advanced factorization algorithms).

By the way unless this is only for fun / learning, I'd recommend not implementing encryption yourself.

Hmmm... All very interesting, thank you!

The more I learn about RSA the less I like about it. It sounds as if a hybrid-system would work best, using RSA to exchange a set of padded AES keys, than just encoding everything after that using 256-bit triple-AES (with key-strengthening of course :P). That way you don't have the nasty overhead costs of RSA -- not to mention the increased bit-size -- and still have considerable security.

Thank you again for everyone's help! :)