Does there exist any software which allows you to extend the keylength for RSA past that limit? It seems arbitrarily short, is this a limit of the number of primes or is there some justification for limits on size other than long computational time?
I’ve been using gaim-encrypt and GPG for years and it’s never made sense why there are restrictions in keysizes.
There are an infinite number of primes, which isn’t entirely relevant here.
The only “long computational time” that’s really relevant is how long it would take to brute-force the encryption (try every possible key), which, for keys that long, would take longer than the Sun’s going to be around. Going to keys much longer is pointless unless we know there’s a break in the algorithm that is mitigated by moving to longer keys. In that case, however, we’d probably do better to move to one of the other algorithms we have.
A set keysize allows you to write code that processes the data faster. You can unroll loops, pack multiple ints into a MMX register to process them all at the same time (potentially), create hardware that does all the encryption/decryption, etc. Probably more important than all of that though, is that when you encrypt stuff, generally it’s to communicate with someone else. That someone else might not be using the same package as you. Coding for variable-length keys is harder than coding for set-length keys, so relying on the person having a package that accepts variable length keys is foolhardy. You’re better off to have a standard that says, “This is the ideal length for low-strength keys, the ideal for medium-strength keys, and the ideal for high-strength keys.” If those two or three are implemented, you don’t really need to worry about anything else. If you leave your average non-cryptographer to decide how long to make his key, he’s liable to choose something dangerously short, or pointlessly long.
Finally, someone who advertises that his crypto uses huge keys is probably selling snakeoil. It’s one of the classing warning signs, but it isn’t the only one and it isn’t even the most important one. (The biggest warning sign is proprietary algorithms. The good ones are all freely available for review.) This is an essay on the topic of snakeoil, with more information on how to avoid it.
The plain fact is that no one knows how secure RSA really is. If it is as hard as it appears to be, then even 256 bit keys won’t be broken by brute force for a long, long time, probably after the sun turns into a red giant and swallows the earth. On the other hand, if someone has actually figured out how to factor large numbers quickly, then there is no reason to think that 4096 bit keys will be that much more secure than 2048 bit ones.
If, say, NSA has already done that, you wouldn’t expect them to announce it publicly, would you?
For those curious, so far, the last number to be officially factored on the RSA challenge is a 768-bit number. “The effort took almost 2000 2.2GHz-Opteron-CPU years according to the submitters, just short of 3 years of calendar time.”
Given that the largest RSA challenge number broken so far is 768 bits, 256 is pathetically tiny by comparison. Stating “no one knows how secure RSA really is” ignores the upper bounds on breaking RSA as already established. True there is no strong lower bound, but enough is known in the other direction to make your suggestion very, very bad advice.
I mean, really. RSA-100 was broken in 1991. That’s over 300 bits right there!
Based on the rapid advances in breaking the RSA challenge numbers in recent years, 4096 may be in reach within 10 years. OTOH, given the also rapidly increasing capabilities of a home PC and the small poly time to compute RSA keys and do en/decryption, going with 8192 costs very little.
(I see pulykamell also provided a link while I got around to posting this.)
I don’t think you understand the difference between asymmetric and symmetric encryption. The 768 bits is for RSA, which is asymmetric. The 256 bits is for something like AES, which is symmetric. You are comparing oranges and apples here. 256-bit AES is not broken and likely will never be broken by brute force since that would require WAY MORE than the heat death of the universe.
RSA is a a asymmetric encryption algorithm which means that it requires both a public and a private key. Asymmetric algorithms typically require many more bits in the encryption keys to reach the same level of security as a symmetric one like 256-bit AES. The rough equivalent level of security for RSA compared to 256-bit AES would be to use something like 4096-bit RSA. And in general, 1024-bit RSA is comparable to 128-bit AES, both of which are nowhere close to even being vulnerable to brute force.
And you are also very wrong about “4096 may be in reach within 10 years”. The encryption bit strength is exponential. The 4096 refers to the exponent in something like 2^4096 possible numbers, which is mind boggling bigger than 2^768.
Hari Seldon was talking about RSA.
Plotting the trend in bits Vs. year first broken from the RSA challenge page, the number of bits Vs. year does have a generally linear trend, not an exponential one. But extrapolating, 4096 bits wouldn’t be broken until around the year 2170, so yeah, 10 years isn’t really reasonable.
Processor throughput generally grows exponentially.
This is just … wow. Just wow. I really don’t know where to begin.
Please, read about the actual facts on this before posting something like this.
The strength is not exponential. If it was, RSA-100 (note base 10) would have never been cracked. The people who broke RSA-768 (note base 2) obviously did not run an algorithm that took 2[sup]768[/sup] steps.
Just think for one tiny, tiny second about that. 2[sup]100[/sup] (let alone 10[sup]100[/sup]) is effectively infinity.
The worst case you can think of is not the best case the people who know what they are doing have figured out. Have you read anything about elliptic curve methods?
I have no idea what you comments on symmetric vs. asymmetric are supposed to relevant to, let alone why you think they are correct. None of that relates in any way shape or form to the actual strength of cryptographic systems. You have can have weak/strong symmetric/asymmetric systems.