Slashdot Mirror
Factorization of a 768-Bit RSA Modulus
dtmos writes "The 768-bit, 232-digit number RSA-768 has been factored. 'The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours . . . . Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.'"
I hope this is a joke. If not, you are confusing the strength of symmetric key encryption and public key encryption. The latter requires larger key sizes because the public and private key pair are mathetmically related whereas in symmetric encryption, there is a single key, and it ought to be randomly generated, and have no mathematical relation to any other value.
The key sizes are given for RSA/DSA encryption. Elliptical curve crypto can use much smaller key sizes while maintaining equivalent security levels. Unfortunately, most ECC is patent encumbered.
Everyone likes to show off how stupid they are, I guess. You don't measure public key keyspace like that. Not all possible bit patterns are valid keys. In fact, VERY FEW bit patterns are valid keys.
So I just did a Wikipedia Crash course on RSA (I knew it was for public/private key encryption) and how it all works mathematically.
But I still don't know what they mean by Factorization, or what that exactly means.
I'm guessing they found all and compiled and tested the possible values and now have a nice big chart? Is 768-bit RSA now considered "broken"?
AES is a symmetric block cipher, meaning, you both need a shared key. While yes, the actual encryption on the data may be AES (I don't know this for sure), you still need to use a public key encryption method like RSA in order to handshake and transfer keys to each other before using AES.
Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.
1024 bit RSA keys are already considered insecure due to the possibility of finding more efficient algorithms. 2048 is considered secure enough.
I was always a fan of twofish, My Niece on the other hand like the red and blue fishes better
Atleast she doesn't do blowfish.
They're comparing the relative strength of a 768 bit RSA key to a 1024 bit RSA key. Because of the mathematical correlation between the public and private keys, the strength is nowhere near 2^768 or 2^1024. RSA has created a comparison table for RSA -> symetric cipher strength.
1024 bit ----> 80 bit
2048 bit ----> 112 bit
3072 bit ----> 128 bit
However, "1000 times stronger" seems far too small, in any case.
Source: http://www.rsa.com/RSALABS/node.asp?id=2004
It is more like O(a^(n/b))
No, factorization is more like O(a^(n^b)). For GNFS on RSA-sized inputs, 1000^(n^(1/3) - 2.5) is a good estimate of the number of operations required.
Tarsnap: Online backups for the truly paranoid
I'd agree with that for government and it's true that the military should phase out 1024, but does the general public need to worry?
How much is your data worth? Back it up now.
Well, djb wrote a particular algorithm, Curve25519, that's in the public domain.
(Yeah, yeah, save your comments about djb's personality. Like it or not, the guy's a crypto and security genius.)
My blog
AES-256 uses a 256-bit key. It has a fixed block size of 128 bits, but that's unrelated to the key length.
There is a related-key weakness in AES-256 and AES-192, bringing their effective strength down to 2^119 and 2^176 respectively. So AES-192 is your best bet right now, though 2^119 or 2^128 are not exactly feasible attack keyspaces either.
That's why we need to be more proactive; instead of trying to eliminate all the invalid keys, we should just pick the strongest possible key and standardize on it.
Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.
That is only helpful if the person sniffing the SSL connection doesn't capture the initial handshake.
The problem with symmetric crypto is key exchange. With SSL the client generates a premaster key, encrypts it with the server's public key, and sends it to the server. Then the client and server use this to derive a session key (at least, that is my reading of the relevant docs - I think the specifics depend on the exact cipher used). So, if you can crack the RSA key, then you can obtain the session key, which makes the entire session obtainable.
To use symmetric crypto you either need a shared secret, or you need to use a key-exchange technique. I believe all the key-exchange techniques are vulnerable to factoring (or P=NP issues in general), although their details vary. If factoring becomes easy we'll never be able to encrypt communications between parties unless they have a secure channel to exchange keys (typically involving plane tickets).
Disclaimer, I'm not a cryptographer and if somebody has more to add I'm all ears.
He said patent encumbered, not copyrighted.
Something can be open source and if it implements something protected by patent in the US or in other nations with laws that allow software patents or have agreements to make US patents enforceable, then it can still be illegal to distribute, and you'd probably be liable for damages if you built commercial software, but IANAL.
I think the patent encumbrances of ECC are the reason it's mysteriously absent from a lot of commercial software that deals with security and even a lot of Linux distros and software. I'd have to double-check, but for example, I don't think Windows Certificate Services supports ECC.
P.S.: Isn't it horrible that Error Correcting Codes and Elliptic Curve Cryptography have the same acronym? IMHO, we should rename one of the TLAs before it becomes a PITA.
Cryptographic strength, as applied to RSA keys, is measured by the time needed to factor the public modulus. The fastest way to do this is today is using the general number field sieve. The run time of the general number field sieve can be estimated as T(b) = exp(1.923 * ln(2^b)^(1/3) * (ln( ln(2^b)))^(2/3)), where b is the size of the input in bits. See Aoki's paper on a kilobit SNFS factorization for details. Chug through this estimate for b = 1024 and b = 768, and you'll find that the ratio is approximately 1000 (I got 1221.15). That's why 1024 bit RSA keys are approximately 1000 times stronger.