Sign in to follow this  
Conoktra

RSA Cryptography Keysize

Recommended Posts

Conoktra    144
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]

Share this post


Link to post
Share on other sites
alvaro    21247
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.

Share this post


Link to post
Share on other sites
Conoktra    144
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)

Share this post


Link to post
Share on other sites
Adam_42    3629
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.

Share this post


Link to post
Share on other sites
KulSeran    3267
Seems alvaro covered well why you need very big numbers for it to be secure.

But
Quote:

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?

The answer is plainly no. But the take away lesson is that you don't want to use RSA to send lots of data.

You use RSA to "sign" data. You take a SHA-256 hash of a data block, then encode that hash with your private key. Anyone with your public key can then hash their copy of the data, decode your hash, and compare the two to determine the validity of the data. Combine this with a Certificate Authority, you can trust that some public key actually belongs to the person you think it does. Thus, you know with quite a bit of certainty that your message came from the right person and wasn't tampered with on the way.

Using a very similar strategy to RSA, Diffie Hellman lets you transfer with some certanty, a password to a symmetric ciper.

Combining these techniques on several levels, combined with a perfect trust system, you can be reasonably assured that your messages are safely getting to the person you want. And you can be assured that the message won't likely be decoded before you can properly act on it.

Share this post


Link to post
Share on other sites
Conoktra    144
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! :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this