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."
... this is. I especially like the mixture of theoretical, practical and yet unknowen aspects of the whole problem.
My impression is that so far DJB has done a good job of being honest and clear. Although "the press" is sadly lacking in experts these days and often will not even notice they have not understood the problem. I have to admit that I did not quite follow
Lenstra-Shamir-Tomlinson-Tromer, but I think DJB's original proposal is still the best source on what is going on. No real surprises so far for practical purposes, but I will follow this closely.
Incidentally I don't fear for my 4096/1024 bit ElGamal/DSA gpg key in the near future. I am confident that installing a keyboard sniffer without me noticing is far easier than breaking that key.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted and ignored otherwise.
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.
Computation time multiplied by the cost of the computer?
His department comptroller must love him. "No, you can't have a new plastic spoon, because it costs 11 cents and you will be using it for 0.8 years and that's...2.8 million dollar-seconds...we'll buy you a new $40 silver spoon every day and let you use it to stir your coffee for three seconds per...that's only 35K dollar-seconds..." It's pathological.
Okay, if you fully depreciate the computer to the moment you start the computation, or better yet, market-price it, then watch the price as the computation continues along (could drop 10-20% in a few weeks for a given top-end PC type machine), then you're calculating the average replacement cost of the machine over the life of the computation.
It still seems a little verschimmelt. The quasi-rent on such a machine is really the depreciation over the term of the computation.
Need to think more on what cost means to someone who's trying to steal all your base. They probably stole the computer, anyway.
--Blair
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!