On 12/9/2010 9:21 PM, Faramir wrote: > I might be wrong, but I remember Bruce Schneier used thermodynamic to > show it is not feasible to brute-force a 256 bits key...
He just repeated the work of Landauer, Margolus and Levitin. Basically, for a digital computer working in base N, the amount of energy required to clear a unit of information is kT*lnN -- the Boltzmann Constant, multiplied by the temperature in kelvins at which the computer runs, times the natural log of the computer's numerical base. For a conventional digital computer, it requires about 10^-23 joules to erase a bit. That energy must be radiated as heat. If you're going to brute-force a 128-bit keyspace, you're going to be erasing 64 bits per key.[*] About 10^-21 joules per key must be radiated, multiplied by the 10^38 attempts you'd have to try on average, gets you 10^17 joules of heat... or about a 100-megaton nuclear explosion. Since Fort Meade is not a smoking radioactive sea of glass, I conclude the NSA is not brute-forcing 128-bit keys. :) In reality the thermodynamic analysis is even more ridiculous than this, since we're assuming you're not tampering with memory in any other way than just to set bits for a key. That's wildly unrealistic. In theory you can break the Landauer Bound with things like adiabatic computing and supra-Turing processing, but those things are so far out in the realm of science fiction they deserve to be called... well... science fiction. [*] You could brute-force the keyspace in a way that only requires you to erase fewer bits per key, but then the defender would just choose a key close to the end of your brute-force schedule. Hence, it's most efficient to do them more or less at random... > And a question: does the computation power required to factor RSA keys > increase in lineal or more-than-lineal way? Roughly logarithmic. As the moduli get larger, the number of primes get fewer and fewer. This is why a 1024-bit key is roughly proportional to an 80-bit symmetric key, a 2048-bit key is roughly proportional to a 112-bit symmetric key, and a 3072-bit key is roughly proportional to a 128-bit symmetric key. Three times the asymmetric key length only gives you half-again the symmetric length. _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
