Factorization of a 768-Bit RSA Modulus 192
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.'"
Re:Bad math... (Score:4, Insightful)
Re:Meanwhile in Canada... (Score:3, Insightful)
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.
Re:Bad math... (Score:4, Insightful)
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.
Re:New algorithms? (Score:5, Insightful)
Re:Can someone explain this to me? (Score:2, Insightful)
Sort of, the key sizes are being increased because it is an effective way to offset the increases in computing power, not for marketing reasons.
If something convincingly better comes out, I'm sure people would use it.
Re:The real scary part is 3 years to obsolecence (Score:5, Insightful)
In the security world, there's always a tradeoff between the cost of the security, the cost to an attacker to break the security, and the value of the thing being protected.
In the military world, there are many secrets which need to be (are seen as needing to be) kept for many years. For these, an encryption that takes a year and $10M to break may not be good enough, because after a year and $10M, an enemy might have information worth more than that. For my bank account, encryption that takes a year and $10M to break is more than sufficient, because the value to an attacker is approximately $47.32, plus the overdraft fees that they can stick me with.
There is no current concern for the average person, unless you're dealing in nuclear secrets or are protecting a politicians date book. Given a choice in the future, moving to a larger RSA key size is prudent change, but that's about it.
Re:Can someone explain this to me? (Score:4, Insightful)
That is like saying RSA-16 (if such a thing existed) is not broken because the fasted way of cracking it is factorization. Brute force is a legitimate form of cryptoanalysis, particularly when it is computationally feasible. Calling an encryption scheme "broken" when an attack such as this is demonstrated is quite reasonable, no matter how inelegant you may find the attack.
Suggesting that DES is not broken is very silly because "not being broken" implies on some level that it is still acceptable to use.
Not at all.
You're assuming there is only a single definition of "broken", which is absolutely not the case in cryptography. The definition you're using is what cryptographers would call a "practical break" and it is almost orthogonal to the definitions that cryptographers normally use. Many cryptographic breaks are not practical, for example, but they're still considered perfectly valid breaks. On the other hand many unbroken ciphers exist which are worthless in practical terms, such as RSA-16.
DES falls somewhere in between. It's not worthless in practical terms, since the effort required to break it is high enough for some purposes, but it has relatively little security value in general. However, the fact that DES is not cryptographically broken does have significant meaning -- because it enables us to have confidence that 3DES is secure. I mention this to make the point that cryptographers' definitions of "broken" (there are many) do have practical implications.
Re:Can someone explain this to me? (Score:3, Insightful)
Like say, a botnet.
Let’s calculate this: ...a third of a day. (hundrets of years * 365 / hundrets of thousands of sytems)
So taking you $defaultCPU, whatever that is, a botnet of hundrets of thousands of systems, with (for simplicity let’s say) 1 core, you could crack a 768-bit RSA in... roughly guessed...
I need a botnet! ^^ ;)
By the way: It is possible to infect a botnet by infecting the botnet client itself? Should be doable, right?
Or do those clients have some extreme self-protection form being compromised? (After all, the programmer should be an expert in this area.