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."
So using 4096 bit encryption wasn't as paranoid as everybody told me...
Quantum Computers, Advances in Number Theory; looks like this decade will become interesting.
BTW Could the admin of http://cr.yp.to please check the serverlogs for any visitors from nsa.gov?
If you're worried about your 1024-bit keys being broken, switch to using 4096-bit keys. Until quantum computers are developed, factorisation will still remain a near-exponential/superpolynomial time activity, and 4096-bit keys will be safe until the military discovers how to harness quantum computing.
Note to M1-ers: a curt but otherwise insightful message is not "Flamebait" or "Troll".
... 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.
Actually, you need double the number of bits just for a basic implementation of Shor's algorithm. It works by starting with a superposition of numbers and taking the log of that, then collapsing the entangled result, which forces the original superposition into a subset of reverse logs. The reverse log problem's one of the hardest in computer science, and solving that has the nice side effect of making factorization trivial.
In practice you'd need CONSIDERABLY more than 2048 bits. A superposition of numbers is really difficult to keep stable because of noise leaking from the outside world into the system - in practice you need extra bits for error correcting codes.
Could you elaborate more on the "reverse log" problem... If you know the base and the result of [Log x], whats the problem?
Isn't public key encryption basically security through really extreme obscurity?
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 seems to tell me that 128 bit encryption is nearly impossible to break by any standards.
On that same site, they are saying that most encryption cracking comes in the form of key snooping, trojan horses, and packet sniffing, so simply increaing the cipher strength probably won't do much.
$ make love
make: don't know how to make love. Stop
I use Maple -- it's a comparatively inexpensive (I got an Academic version of it for free from a university, actually.) and it's easy to use, while still powerful.
Nobody is comparing it to Mathematica or Matlab...but it's still good.
A 1024 bit key yields 1.8*10^308/ln(1.8*10^308) = 2.5*10^305 different prime numbers. which is 2.5*10^228 times more numbers than there are atoms in the known universe. to truly break 1024 bit encryption, it requires some pretty smart programming, not just fast computers. to brute force such a code would take half an eternity by any computing standards.
$ make love
make: don't know how to make love. Stop
I'm new here, but is this a new form of trolling?
$ make love
make: don't know how to make love. Stop
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.
What happens if you don't know the base? ^_^
Shor's algorithm requires a bit of number theory to prove its correctness, but the first part is the important one. You need 2n+1 qubits to factor a n-bit number - two n-bit registers and a keeper bit. (Note, I'm running from memory here, not my notes, so I may have a step wrong.)
You initialize the first with the Hadamard transform, creating a superposition of all possible n-bit numbers. You then raise that superposition to the power of your number to factor, modulo 2^n, and store the result in the second register, which will itself be a superposition (and entangled with the first register). You then measure the second register - and as long as it doesn't measure to be zero, its collapse will trigger a partial collapse in the first register, resulting in a set of bases which are congruent modulo the second register's collapsed result. You then perform a discrete Fourier transform on the first register, and the rest is all logic and repetition.
And if quantum computing is developed, it'll be a whole new ball game (since the adversary will have an exponential amount of resources).
Not really. Quantum computing is not all that. It does not give the user an exponential amount of resources, but it does speed up factoring by a ridiculous amount, breaking RSA. There is no currently published algorithm to break, say, DH/DSS (i.e. discrete logarithms) with it.
That said, it isn't clear that quantum computing is actually practical. It certainly is not parallelizable, and it may turn out to be computationally harder to get the atoms in the right states than it would be to factor your number in the first place. But use DH just to be sure.
I hereby place the above post in the public domain.
Usually you just want p=2 in which case GF(2^m) is embedable in 2^n for large enough n.
Why not? At least in the early 90's Maple was slightly better. I've looked at Mathematica and it doesn't seem to have advanced all that much.
- one cleaned up record
- a whinnebago (burgandy interior)
- a date with an armed woman named Mary
- a trip to Europe (plus Tahiti)
- peace on earth, good will towards man.
OhYeah, I once thought it was secure, but it looks like now I might have to replace my rot13 encryption with rot26, or even rot52...
Click here if you just like to click on shit.
Actually a lot of people are comparing it to Mathematica; some even favourably.
The real question is: what does the NSA use for symbolic computation? :)
What happens if you don't know the base? ^_^
If the base is kept secret then it's not public key crypto any more, is it.
I guess the other reply proves that you can't moderate and post to the same conversation, even if you post as AC.
-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
It's actually a neat way of doing it.
;) )
There's two big things a quantum computer can do effortlessly that a normal one can't. (This doesn't mean a normal one can't emulate one, mind.) The first is superposition - a n-bit register can hold multiple values at once. In fact, more than that - it can hold them in unequal proportions.
The odd bit about a superposition is that if you measure it, it'll "collapse" into one of its possible values according to probability, after which it's identical to that value. 100% probability.
The other thing a QC can do is entanglement. In theory any quantum system is entangled, but when people talk about it with respect to algorithms, they mean this: if you run an algorithm on a superposition of values, you'll get back out another superposition. However, the input and output registers are now "entangled" and any change to one will be instantaneously reflected in the other.
Shor's algorithm uses this last property to effectively do operators in reverse. One way you can factor a number is by finding out if its log in a given base is 0 in a certain modulo. So, you just create a superposition of all possible n-bit numbers, raise them to that base, then measure the result. A certain subset of those numbers will have a integral log - when you measure the results and get a single log, the source (which was previously all n-bit #s) will then become all n-bit numbers that have a log base N.
(This is all gross oversimplification, but it's still pretty accurate. To be fully accurate I'd have to start writing down tensor products of matrices, and well, Slashdot sucks.
Not quite true. There are now implementations of parallel blocked-Lanczos which run very successfully on Beowulf clusters of relatively ordinary machines. The implementation I use was written principally by Peter Montgomery (who, incidentally, is an employee of Microsoft Research) and a cluster of 16 dual-proc PIII-1000 connected by gigabit ethernet yields performance comparable to the high-end Cray C90 which was used for many large-scale NFS factorizations over the last few years. We already know how to improve the implementation to the point where we expect to be able to double the speed or more.
Paul
Lasciate ogne speranza, voi ch'intrate
I wonder if there's a encryption program that use multi-K bit key, such as 8192-bits or 64Kb ?
Many years ago I downloaded a PGP variant that accepts 8192 bit key. So far, I don't know if there's any GPG or PGP or whatever encryption program out there that capable of having more than 8192-bits key.
Any info ?
Muchas Gracias, Señor Edward Snowden !
http://www.bearnol.pwp.blueyonder.co.uk/Math/Facto r/Factorfa.htmly onder.co.uk/Math/Facto r/Factorwa.html
and
http://www.bearnol.pwp.blue
But there is not much cost at doing a NFS on 899.
Things would change if you provided the ip number your smtp server was on. But since it is not on port 25 i only have to scan every ip (2^32 -1) for an smtp server on port 31 or 29.
If you were on port 25 i would have no way to tell it was your smtp. But by setting it up on an obscure port you just gave information.
Y0u have been 0Wned! All you 5MTPz Be10ng to U5. (sorry, i am a beginner at 1337)
FWIW Matlab uses the Maple engine for its symbolic stuff.
It just sounds way too complicated. What does cost factorization have to do with cute little bears anyway?
--- What?
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!
Um, just wondering... how was the above comment flamebait? I could see it as stupid, offtopic, or whatever... oh well, why am I arguing? It's not like karma matters...
I hereby place the above post in the public domain.
Why shouldn't they comapare Maple to Mathematica? Maple may not be as pretty as Mathematica, but it's a more powerful symbolic computation engine.
And I'm not sure how you got the academic version for free, since the academic version costs almost $200! You can imagine how much a non-academic license costs.
That doesn't make sense.
Did you mean "0 = y mod p"?
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?
Okay, I give up. I can see how a fair shuffle can be regarded as a multiplication by two mod 51 for any given card (since the first card in the deck and the last card are both zeros). The loop starting at 1 (second card in the deck) goes: 1,2,4,8,16,32,13,26. So after 7 shuffles it seems like the card that was originally at position 1 will be in position 26. What gives?
-a
How to rationalize theft.
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
g really ought to be a generator of (Z/pZ)* if you want the discrete log to be well-defined.
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.
Wrong. The shuffle you describe produces a 52-cycle in S_52. In particular, you have to repeat it 52 times to get the original order. However, if the bottom half drops the first card, you get 2 fixed points, a transposition, and 6 8-cycles, meaning 8 shuffles are required.
I don't see many patterns that are immediately obvious for n cards, except for the 2m-periodicity when n=2^m. Is there a general solution?
"Your notation sucks!" -- Serge Lang (1927-2005)
Give this guy a break.
It takes 8 perfect shuffles. To continue the series you outlined (2^n mod 51, n=0,...): 1,2,4,8,16,32,13,26,1.
-- kryps
Well, sure. I figured that out before I posted, and later confirmed it with a google search (I was still trying to figure out the puzzle without "cheating"). But here he goes asking me to generalize to an N card deck and the one data point he gives me is wrong. I spent quite a while looking for relations between Euler's phi function and the number 7 before I thought to confirm this result. Plus when I eventually looked the problem up, it doesn't look like there's a closed form solution anyway.
-a
How to rationalize theft.
Okay, I see why your puzzle is related to the discrete log problem. You're looking for the order of 2 in (Z/(n+1)Z)* with the shuffle you described, or (Z/(n-1)Z)* with the shuffle you meant to describe. It doesn't seem to work too well with odd n.
"Your notation sucks!" -- Serge Lang (1927-2005)