## More on Bernstein's Number Field Sieve 151

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."*
## Re:Cool but (Score:2)

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.

## Re:Cool but (Score:1)

## Re:Cool but (Score:4, Informative)

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 logproblem 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

## Re:Cool but (Score:4, Informative)

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?

## Re:Cool but (Score:2)

Did you mean "0 = y mod p"?

## Re:Cool but (Score:2)

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

## Re:Cool but (Score:1)

It takes

8perfect shuffles. To continue the series you outlined (2^n mod 51, n=0,...): 1,2,4,8,16,32,13,26,1.-- kryps

## Re:Cool but (Score:2)

-a

## Re:Cool but (Score:1)

the discrete log problem is specifically, given integers y, g, p, find a (preferably minimal)solution x to the problemy = g^x mod p, 0 = y pg 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?

## Re:Cool but (Score:1)

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.

## Re:Cool but (Score:3, Interesting)

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.

## Re:Cool but (Score:2)

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

## Re:Cool but (Score:1)

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.

## Re:Cool but (Score:1)

## Headhunters visiting the site? (Score:1)

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?

## Re:Headhunters visiting the site? (Score:2)

## Re:Headhunters visiting the site? (Score:2, Funny)

But you're wrong concerning the AOL CDs. One of NSA's missions is "protection of U.S. information systems". So no AOL allowed...

## Re:Headhunters visiting the site? (Score:3, Funny)

Quantum Computers, Advances in Number Theory; looks like this decade will become interestingI'll say! Arthur Andersen has advanced number theory further than anyone had imagined it could go!

## Re:Damn straight LA is the bottleneck (Score:1)

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.

## Re:Damn straight LA is the bottleneck (Score:1)

NFS can be helped by distributed computing but the linear algebra can't. That's why the linear algebra is the real bottleneck and not the NFS if you had enough resources.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

## So what? (Score:1)

## Re:So what? (Score:2, Informative)

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

## Its the same problem (Score:1)

## Re:Its the same problem (Score:1)

[cheap plug]

My (free, portable, fairly packed) libtomcrypt lib takes the NIST curves over GF(p) since they are simpler to work with...

http://libtomcrypt.sunsite.dk

[/cheap plug]

Using the other field structure is more important in hardware or say low end microcontrollers.

Tom

## Re:Its the same problem (Score:1)

## Re:So what? (Score:1)

In the realm of things the DLP over GF(p) is harder to solve then the IFP.True, but arguably not significant. With the NFS, both problems have the same asymptotic difficulty. Further, the DLP isn't much harder than the IFP in practice. Solving instances of the N-bit DLP is approximately as hard as solving the IFP with N+30 bits.

Even harder is the DLP over eliptic(sic)curves.Very much the case at present, though more and more curves are found to be vulnerable to variants of known attacks, and more attacks are being discovered all the time. There were some interesting papers at the ANTS-V and ECHIDNA conferences held earlier this month in Sydney.

Paul

## Re:So what? (Score:1)

True, but arguably not significant. With the NFS, both problems have the same asymptotic difficulty. Further, the DLP isn't much harder than the IFP in practice. Solving instances of the N-bit DLP is approximately as hard as solving the IFP with N+30 bits.While in practice the time-wise estimates are the same the space-wise are not. Over a single large prime group the DLP takes p times more memory to solve [where p is the # of bits in the group modulus]. Also the matrix ops in the final stage are not with bits but with p-bit integers.

This makes the last stage "practically" way more difficult than it is for the IFP.

As for type sof curves, [no joke here], I'm not an ECC expert. I just used what NIST gives out as they are more traditional types of curves.

Naturally one must keep an eye open for thr horizon of new attacks but for the time being ECC appears to be way harder than RSA or DH[over GF(p)].

One little rant-addon. You can do DH over ECC despite what most PGP drones want you to think. This really p's me off. Add ECC support to GPG already!

Tom

## Re:So what? (Score:1)

History is littered with the bodies of people who think that a cryptosystem is unbreakable, or essentially unbreakable. Just because we can't break something now doesn't mean a solution won't be found next year, or even next month.

There's a reason that most cryptosystems aren't proveably secure; they

aren'tsecure. It's all a gamble that the next mathematical breakthrough in whatever field will be far enough down the road not to matter to you.Thinking anything else, or becoming complacent with a seemingly secure system, is little better than no cryptography at all.

## Re:So what? (Score:2, Funny)

## Re:So what? (Score:1)

## Re:So what? (Score:2)

## Re:So what? (Score:1)

## Re:So what? (Score:1)

Anyways, once i read a theory that suggested using a graph-theory based encryption scheme. The idea was interesting, particulary because - as others mentioned - we simply have no proof that factorization is an NP-full task, while on the ther hand, we _have_ proof that the graph theory has some problems like this (e.g. finding Hamilton-circles IIRC).

## Fascinating Discussion... (Score:5, Interesting)

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.

## Re:Fascinating Discussion... (Score:2)

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.I concur. I find this device [thinkgeek.com] far more threatening than any cluster of machines at the NSA.

## Re:Fascinating Discussion... (Score:2)

## Re:Fascinating Discussion... (Score:1)

But it is suspected that factorization is AS STRONG as the DL problem. But no proofs exist yet.

It should be assumed however that if the integer DL is solved, all PK crypto (RSA & factor based ciphers included) would fall with ECC and GF(2^x) DLs to fall shortly after...this is just the general sentiment in the field. FYI

JLC

## Re:Fascinating Discussion... (Score:2)

ElGamal/DSA are based on discrete logs, not factorization. So I'd say you're safe from DJB for now.That is the second reason I feel pretty save. Just trying to see whether anybody notices...

I agree that the if somebody gets a foot into DL anywhere, they likely can open the whole door and presumably some other doors too. Not my field of expertise though.

## Security ... (Score:1)

## Re:Security ... (Score:3, Interesting)

-russ

## Re:Security ... (Score:2)

-russ

## Re:Security ... (Score:3, Funny)

Security through obscurity is when you run your relaying smtp server on port 27 instead of port 25.That's why I choose

realsecurity. My relaying smtp server runs on a prime number port, protected by factoring. In fact, I can go ahead and tell you that the port is one of the prime factors of 899 without reducing my security at all.(The example of 27 is a particularly lame choice, since it's 3x3x3. That's not even nearly prime.)

## Funny!.. but you gave too much information. (Score:1)

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)

## Re:Security ... (Score:2)

## Re:Security ... (Score:2)

-russ

## Re:Security ... (Score:1, Interesting)

let S = the set of all possible keys

for each key k in S

try k

if (k works)

stop

What we have is algorithms that are *hard* to break by brute force. We make them hard by making S as big as possible. And each time you add another bit to your key, the size of S doubles. Hence cracking is an exponential operation.

## Re:Security ... (Score:1)

An interesting area of crypto research is trying to extend the same idea to other cryptosystems - can you generate while you encrypt a message a second "private" key that will yield a perfectly innocuous (sp?) message? If ever questioned, reveal that key, not your real private key. Or use two different private keys simultaneously so that all messages use the same key for their innocuous halves.

--Knots

## Re:Security ... (Score:1)

Security Through Obscurity is bad because every (say, MS Media Player) has the same secret. If that secret is discovered, then

Asymmetric encryption (e.g. Diffie-Hellman) avoids this problem by having a different secret for each end user. If the secret is discovered then only that user is compromised.

The point is that Security Through Obscurity depends upon widely distributed secrets (e.g. the exact behaviour of binary code), whereas competent encryption doesn't.

## Re:Security ... (Score:3, Informative)

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.

## Re:Security ... (Score:2)

To carry the analogy a bit further, your lock would probably be very difficult to pick quickly, no matter how skilled the person trying to pick it is in picking other locks- at least until he figured out how it worked. Once the principle of operation of your lock is known, though, the person trying to pick it can develop a standard approach to picking that style of lock.

The problem then is that there's a very good chance that your new lock design will be easier to pick for somebody who knows how it works than a standard lock would be. Chances are you've made a mistake and left in some vital flaw in your design that makes it easier to pick. After all, your lock would not have the decades of dedicated people trying to figure out how to pick it that are needed to find and correct the weaknesses in its design. And if you try to sell your lock to the public, anyone who's interested in learning how to pick it will be able to buy one, take it apart, and spend as much time as he wants trying to figure out how it works.

## Re:Maple? (Score:2)

Nobody is comparing it to Mathematica or Matlab...but it's still good.

## Re:Maple? (Score:1)

## Re:Maple? (Score:1)

Nobody is comparing it to Mathematica or Matlab...but it's still good.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? :)

## Re:Maple? (Score:1)

## Re:Maple? (Score:1)

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.

## Why? (Score:1)

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.

## Re:Why? (Score:5, Informative)

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 keyencryption is considered virtually unbreakable. 128-bitpublic keyencryption is not. AES is an example of private key encryption; RSA is an example of public key encryption.-a

## Re:Why? (Score:1)

## Re:Why? (Score:2)

I believe your confusing public/private with symetric/asymetric. Public/Private terminology is used with asymetric enryption techinques like RSA, but not witrh symetric techniques like AES or DES.

I most certainly am not. Do a little research and you will find that the terms "public key cryptography" and "private key cryptography" are commonly used to refer to asymmetric and symmetric encryption respectively. E.g. see result of google search [google.ca].

-a

## Re:Why? (Score:1)

## Re:Why? (Score:1)

isnearly unbreakable. The problem is that you have to arrange a key with the person to whom you're sending the message, which could be difficult, especially if you don't know him or her.That's where public key crypto comes in. Knowing that my PGP public key ID is 0x84B0FDB8, you could send me a message that only I could decode, unless the NSA has a few very interesting secrets. Since I have to publish information (namely how to encrypt the message), this type of code is inherently easier to break. RSA can be broken by factoring a large number, and a 128-bit number poses little challenge for even the Sieve of Eratosthenes on a fast computer, so longer ones are needed. The question is, how much longer?

Which is why I use DH/DSS, which operates with the (slightly) harder problem of discrete logarithms.

## Re:Why? (Score:1)

RSA can be broken by factoring a large number, and a 128-bit number poses little challenge for even the Sieve of Eratosthenes on a fast computer, so longer ones are needed.

}}}

I hope you regret writing that.

For 128 bits (39 digits), you almost certainly need a better than O(n^(1/3)) algorithm, or an amazing constant factor in something like a Fermat method with sieves (a la Knuth).

Fortunately P-1 and Rho are arguably O(n^(1/4)), and ECM is better still (arguably sub-exponential). However, if you have prior knowledge that the number is unlikely to have small factors, then at 39 digits, you may as well just roll out a QS, which is sub-exponential, and excels when there are no small factors.

Satoshi Tomabechi's PPSIQS would do the job in the bat of an eye.

Mike Scott's QS, accompanying his Miracl library, would do the job too.

THL.

## Re:Why? (Score:1)

## Re:Why? (Score:1)

The average computer can crack a 128 bit RSA key in about a month.Actually, the average computer can crack a 128-bit RSA key in about a minute. Assuming, that is, it's using an algorithm developed in the last twenty years or so. 128 bits is only 43 digits, and factoring 43-digit integers these days really is very easy.

in 1999, a beowulf cluster broke a 128 bit key in a matter of a few hours.References please. This is a new one on me. What kind of key? At this size a RSA key, or a discrete log over the integers, is essentially trivial and a 3DES or AES key is essentially impossible, AFAIK. State of the art for the ECDLP (elliptic curve discrete logarithm problem) is still a few bits short - again, AFAIK.

Paul

## Re:Why? (Score:1)

128 bits is only 43 digitsSigh. I really ought to check before relying on memory, rather than afterwards. A 128-bit integer actually has 39 decimal digits.

Paul

## Re:Why? (Score:1)

You're thinking of keys for

symmetricciphers - the kind where the same key does both the encryption and decryption. For public-key algorithms, more key bits are needed to achieve the same level of security.According to Bruce Schneier in

Applied Cryptography, Second Edition, a 56-bit symmetric key is roughly as secure as a 384-bit asymmetric key, and a 128-bit symmetric key is roughly as secure as a 2304-bit asymmetric key. (Table 7.9 on page 166; there's a copy of the same table on the page you linked to.)Even with a symmetric algorithm, though, breaking a 32-bit key is not "practically impossible by human standards". 56 bits, the key size used by DES, is considered to be insecure since it can be broken in a few days on a PC. I'm not sure where you got your information on that page you referred to, since in the last paragraph the author says "For today's secrets, a 1024-bit is probably safe and a 2048-bit key definitely is." And "today" in this case is January 26, 1997, when the page was last modified.

I'd recommend at least 4096 bits for new keypairs. It may or may not be overkill, but modern computers are fast enough that the time it takes to cipher with a longer key is still insignificant in the course of normal usage.

## Re:Why? (Score:1)

## Cost Effective? (Score:1, Funny)

## Time to update that crypto (Score:3, Funny)

## Re:Time to update that crypto (Score:1)

Why isn't there a "-1 Lame joke" moderation? :-)

## Re:Time to update that crypto (Score:1)

Overrated=1, Total=4.There is, sort of. But I was *really* going for -1, Obvious. Imagine a Beowulf Cluster of those!

## Cost model (Score:4, Funny)

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

## Check out my factorization applets... (Score:1)

and

http://www.bearnol.pwp.blue

## I don't think the kids will like it (Score:1)

## The most interesting part (Score:1)

## Key factor (Score:2)

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 ?

## Re:Key factor (Score:2)

4096 should suffice for most applications todag.

If you want more security I suggest you start looking into one-time-pads.

## Re:Suicide Note (Score:1)

## MODS? (Score:1)