Slashdot Mirror
More on Bernstein's Number Field Sieve
Russ Nelson writes "Dan Bernstein has a response to Bernstein's
NFS analyzed by Lenstra and Shamir, entitled Circuits for integer
factorization. He notes that the issue of the cost of
factorization is still open, and that it may in fact be inexpensive to
factor 1024-bit keys. We don't know, and that's what his research is
intended to explore."
Or you can be smart and stop using RSA. In the realm of things the DLP over GF(p) is harder to solve then the IFP.
Even harder is the DLP over eliptic curves. With proper curves [e.g. NIST supplied ones] the best attacks on the math take SQRT work which means a 256-bit ECC key will take roughly 2^128 work to solve for the private key [from the public key], provided the cryptosystem is setup correctly [yadada].
Tom
Someday, I'll have a real sig.
Could you elaborate more on the "reverse log" problem... If you know the base and the result of [Log x], whats the problem?
The OP got his terminology wrong. It's the discrete log problem that's hard.
Pick a number (e.g. 3.81482), plug it into your calculator and press e^x (result = 45.36874). Now it's easy to get back the original number by using the "ln" key. But imagine instead that you only had the fractional portion of the result (.36874). Now it's next to impossible to figure out what the original number was. The discrete log problem is basically the same this, but using discrete arithmetic instead of real arithmetic.
-a
How to rationalize theft.
I didn't really think there was any need for anything better than 128 bit encryption. It would take a lot of factoring that is practically impossible by human standards to figure out the key for a 32 bit encrypted code, and this site [stack.nl] seems to tell me that 128 bit encryption is nearly impossible to break by any standards.
128-bit private key encryption is considered virtually unbreakable. 128-bit public key encryption is not. AES is an example of private key encryption; RSA is an example of public key encryption.
-a
How to rationalize theft.
No. The phrase "security through obscurity" generally means that the security algorithm is kept a secret. The lock on your house is a good example - how the lock works is open, public information. The particular key that you use, however, is not. To unlock your door, someone must either learn what key you use or exploit weaknesses in the lock. A standard locksmith text, some standard locksmith tools, and a little time is all that's required to pick the standard lock. How the lock works is not obscured; what key you use is.
:)
Since everyone knows how the lock works, everyone can see what the weaknesses are and everyone can try to correct them (this has been done over the last couple of centuries). If you used a non-standard lock with a mode of operation that only you knew, that would be security through obscurity. No one can learn to pick it by reading standard locksmith texts. The weaknesses would have to be learned through trial and error by someone on your front porch. Any lockpicker would have to learn not only what key you used but how to use it in the lock.
Public key encryption generally uses well-known algoorithms - this is what makes it not obscure. The keys are secret, just as with obscure systems. However, everyone can see whether or not the system is a strong one.
Go read Cryptonomicon for a fictional introduction to the perils of obscured cryptosystems, as well as the benefits of open ones. Then read Applied Cryptography for the real (ie technical and mathematical and correct) deal. Or just take my word for it like a happy little slashdotizen.
BTW, modern locks are the result of a couple hundred years of improvements and refinements; they are currently about as good as they need to be, given weaknesses of the door itself, the convenience of regularly using the mechanism, the cost of the lock and keys, etc. Cryptosystems are nowhere near that level yet. The internet is still a country town, in the sense that everyone leaves their house unlocked and their keys in the ignition of their car. Once everyone's been hacked a couple of times (and I do mean everyone), adoption of crypto will become widespread, and we'll begin to see sufficient standardization to make crypto comparable to real-life locks. Government officials don't whine about locks the way they do about crypto for good reason - they aren't much more than courtesy and inconvenience devices. Give me a good sledgehammer and I'll be in your door in five minutes. Give me a power saw and I'll make my own door. Betcha the standardized crypto will be similar.
discrete logs actually have to do with modular spaces (remainder math, in mod 4, you divide any number by 4 and take the remainder. counting in mod 4 goes like: 0, 1, 2, 3, 0, 1, 2, 3...)
the discrete log problem is specifically, given integers y, g, p, find a (preferably minimal)solution x to the problem
y = g^x mod p, 0 = y p
actually the problem is more general than that, but that's the case that most people talk about and has direct application to cryptanalysis.
it doesn't look too hard, but sit down and try. the algorithms that solve the problem amount to basically highly erudite mathematical guess-and-check. if you can find a P time solution to this, you're a billionaire.
It's also a fun problem because, like Fermat's Last Theorem, Goldbach's Conjecture, and the 4-Color problem, it's easy for an amateur to work on, understand, and make some elementary discoveries and proofs, but the problems have difficulties that test the furthest extent of mathematical knowledge.
here's a fun, related problem:
if you shuffle a 52 card deck perfectly 7 times (divide the deck exactly in half, always have the top half drop the first card, drop exactly one card after another) then you end up with the original order of the deck. Given a deck of n cards, how many shuffles are required for the same effect?
In Capitalist America, bank robs you!