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."

Comments

fp?

[Anonymous Coward]

Naked lady!

Re:fp?

[Anonymous Coward]

Your browser sent a request that this server could not understand.

Apache/1.3.23 Server

Why am I not surprised?

Re:fp?

[Anonymous Coward]

Fixed!

Now with bonus naked lady!

Re:fp?

[Anonymous Coward]

who is she, and where can I get some more pics? [The mirror bitch, not the one with the dildo up her honey-hole]

Re:fp?

[Anonymous Coward]

Her (pornstar) name is Swan. You can find pictures of her on www.exposedpornstars.com. Use the url format "www.exposedporntars.com/swan$/swan$1.htm", replacing the "$" with an interger between 1 and 11 to see each gallery.

fp?

[Anonymous Coward]

maybe, lucky one?

Is DJBernstein a genius?

[Anonymous Coward]

Is DJ Bernstein a genius?

Dear Fred

[Fecal Troll Matter]

Here is the link I promised you.
Toodles.
-Heidi

Bernstein needs some help

[Anonymous Coward]

Web usability expert needed. ASAP.

Although,

I guess

that some

people like

having to

click on

a new

link every

other minute.

I wonder

[Anonymous Coward]

could it be possible to mod stories down as well??

Re:I wonder

[Anonymous Coward]

try this

Kill all the KIKES

[Anonymous Coward]

The main problem is the Jew.

Read about the Jew: Who Rules America

Listen and learn about the Jew in this mp3.

Let's all join hands to solve the Jewish Problem !!

Summary

[Anonymous Coward]

I can summarize by saying...

HUH??!!?

What in the name of FUCK are you talking about??

Re:Summary

[Anonymous Coward]

Slashdot has confused itself with a respectable scientific journal.

This happens every now and then.

Your Microsoft bashing/music stealing/piracy justifying/Linus fellating article will be along shortly.

Your patience is appreciated.

Cool but

[DinZy]

A quantum computer could do this in no time. Of course someone would have to build a really big one to do a 1024 bit number.

Re:Cool but

[Uller-RM]

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.

Re:Cool but

[SamBeckett]

Could you elaborate more on the "reverse log" problem... If you know the base and the result of [Log x], whats the problem?

Re:Cool but

[ninkendo84]

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.

Re:Cool but

[God! Awful]

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

Re:Cool but

[Uller-RM]

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.

Re:Cool but

[Anonymous Coward]

Or you could get incredibly lucky and derive the correct key in a few seconds.

Re:Cool but

[Anonymous Coward]

I modded this up, but I'll be goddamned if I could tell if he's making this up.

Re:Cool but

[God! Awful]

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

[Uller-RM]

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. ;) )

Re:Cool but

[colmore]

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?

Re:Cool but

[blair1q]

That doesn't make sense.

Did you mean "0 = y mod p"?

Re:Cool but

[God! Awful]

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

[Scott Carnahan]

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?

Re:Cool but

[kryps]

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

Re:Cool but

[God! Awful]

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

Re:Cool but

[Scott Carnahan]

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.

Maybe ninth or tenth

[Anonymous Coward]

post yeah keep it up the trolls got to get to owning some more stories around here. Trolling seems to have been slacking off quite a bit as of late.

Rapid fire trolling

[Anonymous Coward]

go yeah keep it up trolls will own you.

You got to ask yourself a question

[Anonymous Coward]

Can you mod faster than I can post. Well can you PUNK!

Headhunters visiting the site?

[Blue 1ce]

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?

Re:Headhunters visiting the site?

[Anonymous Coward]

Using encryption at all is evidence of paranoia.

What do you possibly do that you think someone would be interested in you and your files?

Re:Headhunters visiting the site?

[Anonymous Coward]

it also means you are a terrorist

Re:Headhunters visiting the site?

[Anonymous Coward]

My wife could use my vast cache of encrypted pornographic movie files to prove that I was unfaithful in our marriage. Or the government could decrypt the messages I've been sending to my friends on where to download the latest top40 mp3's off my secret FTP site. If either of these things happened the consequences could be disastrous.

Re:Headhunters visiting the site?

[gr]

So using 4096 bit encryption wasn't as paranoid as everybody told me...

Actually, from my reading of the analysis of DJB's original statement, you're closer to being at risk.

BTW Could the admin of http://cr.yp.to please check the serverlogs for any visitors from nsa.gov?

Which would prove what, exactly? The NSA doesn't get AOL CDs like the rest of us?

Re:Headhunters visiting the site?

[Anonymous Coward]

Owning and viewing pornography is not proof of unfaithfulness. You can always turn any allegation regarding porn around and use it against her, claiming that it was her alienation of affection that drove you to those extreme measures. You keep the kids, house, car, and money. She gets crap for running out on you.

If you are involved in music piracy, then I could see how you'd want to obfuscate your illegal actions to avoid detection.

Re:Headhunters visiting the site?

[Blue 1ce]

OK, you're right. Or as DJB puts it: "This is revisionist history, not a technical dispute."

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?

[larry bagina]

Quantum Computers, Advances in Number Theory; looks like this decade will become interesting

I'll say! Arthur Andersen has advanced number theory further than anyone had imagined it could go!

Casting Call

[Anonymous Coward]

Rectal Impaction Following Enema with Concrete Mix

by Peter J. Stephens, M.D., and Mark L. Taff, M.D.
from the American Journal of Forensic Medicine and Pathology 8(2):179-182, 1987.

This article describes an unusual rectal foreign body resulting from homosexual anal erotic activities. The patient had used an enema containing a concrete mix which became impacted and required surgical removal. The use, abuse, and complications of enemas are reviewed.

During the last 20 years, sexual habits have changed in western society. Homosexuals have shown an increasing interest in anal erotic practices, including the use of enemas for sexual enjoyment. We report a case of a klismaphiliac who had an impacted foreign body in his rectum followin an enema with a concrete mix.

CASE REPORT

A 20-year-old man presented to the emergency room complaining of rectal pain. A well-nourished, well-developed man without signs of intoxication was admitted in no apparent distress. Digital examination of the rectum revealed a stony hard mass. Abdominal plain films showed a vertically oriented, low-lying radiopaque object in the rectum. A spherical radiolucency was noted in the upper pole of the mass. A blood alcohol level was negative. No other drug testing was performed.

Upon further questioning, the patient said that approximately 4 hrs earlier he and his boyfriend had been "fooling around." After stirring a batch of concrete mix, the patient laid on his back with his feet against the wall at a 45-degree angle while his boyfriend poured the mixture through a funnel into his rectum. After the concrete mass hardened, it became so painful that he sought medical care.

Under general anesthesia, the anus was dilated and two Foley catheters were inserted alongside the rectal mass to relieve suction. A concrete case of the rectum was delivered without incident. The rectal mucosa was intact with a hyperemic and edematous appearance.

The patient was kept overnight and discharged uneventfully the following morning. The attending physician recommended a psychiatric consultation, but the patient declined.

PATHOLOGIC EXAMINATION

Examination of the specimen revealed a perfect concrete cast of the rectum, measuring 12 X 7 X 5 cm and weighing 275 g. A thin layer of feces coated the surface and crevices. Grooves in the mass were consistent with rectal mucosal folds. A layer of concrete was chipped off the upper part of the specimen and revealed a white plastic ping-pong ball. This corresponded to the radiolucency observed in the abdominal x-ray.

some people...

[Anonymous Coward]

....Really need to get outside more

Damn straight LA is the bottleneck

[Anonymous Coward]

"Why is it difficult to carry out a 1024-bit NFS calculation? Because, they claim, 1024-bit NFS sieving is difficult. "

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.

Re:Damn straight LA is the bottleneck

[paladin_tom]

The key phrase is if you had enough resources.

Crypto has always been a battle of resources between encoder and cracker. RSA works specifically because, as another post pointed out, factoring an n-bit number is an O(2^n) operation (hence factoring polynomials back in high school is a royal pain). This gives the edge to the encoder, because by increasing his resource usage in a linear fashion, (s)he forces the adversary to pay an exponential increase in resources.

That's why people introduce tricks like this NFS sieve -- the adversary must find a way to cheat.

Of course, since computing power tends to increase exponentially with time, we keep needing bigger keys. And if quantum computing is developed, it'll be a whole new ball game (since the adversary will have an exponential amount of resources).

Re:Damn straight LA is the bottleneck

[wirelessbuzzers]

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

[Xilman]

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?

[Dthoma]

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.

Re:So what?

[tomstdenis]

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

Re:So what?

[stewby18]

4096-bit keys will be safe until the military discovers how to harness quantum computing.

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't secure. 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?

[cheese_wallet]

What we need is an encryption system that isn't based on math.

Re:So what?

[kistel]

Heh, how do you know they don't have it? Do you think they would announce it right away? The military has always been ahead of the rest of the world.

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).

Re:So what?

[Xilman]

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?

[tomstdenis]

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?

[volsung]

But won't you need a lot of monkeys and typewriters?

Re:So what?

[cheese_wallet]

You took the words out of my mouth.

Re:So what?

[MarkGriz]

Microsoft employed a great deal of monkeys and typewriters as part of their original business plan to develop encryption technologies, but accidentally developed Windows instead. Ironically, much to their embarrassment, Windows ended up with very little in the way of security or encryption.

Damn

[Weffs11]

Should have taken more then trig, then I might understand the story.

Fascinating Discussion...

[gweihir]

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

Re:Fascinating Discussion...

[Anonymous Coward]

Actually the main danger with ElGamal is that I believe it's one of the Public Cryptosystems that hasn't yet been proven to truely rely on the log problem therefore while installing a keyboard sniffer would still be easier there is a chance that the whole algo may totally unravel sooner than the solution of the log problem... (I cannot check my notes at the moment hopefully someone can check for me)

Re:Fascinating Discussion...

[First Person]

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 far more threatening than any cluster of machines at the NSA.

Re:Fascinating Discussion...

[AlgUSF]

Then use a USB keyboard.....

Re:Fascinating Discussion...

[jlcooke]

ElGamal/DSA are based on discrete logs, not factorization. So I'd say you're safe from DJB for now.

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

[gweihir]

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.

Great.

[Anonymous Coward]

Well done, you retarded trolls. You've successfully kept the signal:noise ratio of this post at 1:1. I hope you're proud of yourselves.

Re:Great.

[Anonymous Coward]

ironically, you got moderated -1 troll.

Re:Great.

[Anonymous Coward]

Actually, that is the basis for a fiendishly clever encrypting scheme!

Wasting a logged-in post for the CLIT

[TheSpoogeAwards]

Crap! Linux Is Terrible!

Ever heard of The Sermon on the Mount?

[Anonymous Coward]

Owning and viewing pornography is not proof of unfaithfulness.

Ye have heard that it was said by them of old time, Thou shalt not commit adultery:
but I say unto you, That whosoever looketh on a woman to lust after her hath committed adultery with her already in his heart.

CLiT

[Anonymous Coward]

suck it m0dz, tr0llZ own u.

LoL, you fucking nigger

[Anonymous Coward]

you sir are a gay nigger

CLiT

TRoLL.

Security ...

[YahoKa]

Isn't public key encryption basically security through really extreme obscurity?

Re:Security ...

[Russ Nelson]

No. Security through obscurity means that your task is made easier on every decryption by knowing something which is intended to be a secret. Needing to factor a number every time isn't obscurity. It's just plain hard.
-russ

Re:Security ...

[Anonymous Coward]

Sure, by the same reasoning that all encryption except OTP is security through obscurity. Nobody's proven any given algorithm is impossible to break other than through brute force. Even if one algorithm was, there's nothing preventing someone from guessing the correct key by chance.

Re:Security ...

[Anonymous Coward]

No. Security through obscurity means that your task is made easier on every decryption by knowing something which is intended to be a secret.

Not to be a smartass, but by this definition all encryption is security through obscurity. After all, decryption is much easier if one has the secret key.

Re:Security ...

[scott1853]

Well, every security implementation is technically security through obscurity unless you're using a perfected implementation of biometric authorization. Even passwords and high bit number factorization is simply based on not knowing something (the password or the prime numbers) and doesn't really prevent the wrong person from accessing resources.

Re:Security ...

[paladin_tom]

You can't have an algorithm that cannot be broken by brute force. Here's the proof:

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

[Terri416]

All encryption requires secrets. Good algorithms require that only the keys are secret, and everything else (especially the algorithms themselves) can be published without compromising security.

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

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

[Anonymous Coward]

You forgot the semicolons.

Re:Security ...

[Anonymous Coward]

How do you know that k works?

Look up "one time pad."

Re:Security ...

[_Knots]

Weeeeell... a boring old XOR OTP is "unbreakable" because (k works) is not possible to evaluate - *every possible* plaintext will be generated in your search through S. Now can you pick the right one? Of course not, you'd have to know which one it was ahead of time.

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

[dillon_rinker]

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.

Re:Security ...

[Anonymous Coward]

*smack* you're stupid. (k works) will be true for every message the same length as the message you're trying to decrypt. Look up One Time Pad and think about it.

Re:Security ...

[Russ Nelson]

I'm curious: did you read what I wrote or are you replying to the original poster to whom I was writing?
-russ

Re:Security ...

[Russ Nelson]

No. Security through obscurity is when you run your relaying smtp server on port 27 instead of port 25. Real security is when you only relay when the user has authenticated cryptographically using SMTPAUTH.
-russ

Re:Security ...

[rgmoore]

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.

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:Security ...

[Waffle Iron]

Security through obscurity is when you run your relaying smtp server on port 27 instead of port 25.

That's why I choose real security. 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.)

Re:Security ...

[Anonymous Coward]

So, your server is on port 29 or 31 ? Brilliant.

firth potht

[Anonymous Coward]

dont you *EVER* post anymore shit like this again. this artical is pure shit. i order you faggots to stop posting shitty articals!

Maple?

[Anonymous Coward]

What a nutcase. Who in his right mind uses Maple?

Re:Maple?

[man_ls]

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.

Re:Maple?

[jbolden]

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.

Re:Maple?

[saforrest]

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?

[BoneyM]

FWIW Matlab uses the Maple engine for its symbolic stuff.

Re:Maple?

[jpmorgan]

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.

well, yes and no

[Anonymous Coward]

betcha thought i was gonna post something of relevance here didn't ya? YA DUMBFUCKING GAY NIGGERS

Why?

[ninkendo84]

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.

Re:Why?

[God! Awful]

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

Re:Why?

[wirelessbuzzers]

128 bit encryption is for symmetric (i.e. private) key encryption. It is nearly 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?

[jmauro]

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.

Re:Why?

[muon1183]

The average computer can crack a 128 bit RSA key in about a month. Of course, the average slashdoter's computer can break 128 bit key in about a week, and, in 1999, a beowulf cluster broke a 128 bit key in a matter of a few hours. Of course, with 1024 bit encryption, it is far easier just to stick a key stroke log onto somebody's computer, but, considering that in 1999 a beowulf cluster was able to brute force a 128 bit key in a matter of hours, it is probably possible to break a 1024 bit key in about a year these days (unless, of course, your the NSA, in which case, you can break it in a couple of days).

Re:Why?

[Wyzard]

You're thinking of keys for symmetric ciphers - 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?

[God! Awful]

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.

-a

Re:Why?

[braindead]

You are right, although I would like to point out that the terms "public-key cryptography" and "secret-key cryptography" (note "secret" instead of "private") are preferred because of the lower risk of confusion.

Re:Why?

[Xilman]

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?

[Xilman]

128 bits is only 43 digits

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

Paul

Re:Why?

[^BR]

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.

This may be true for something like PGP because you only send that many email a day, but for a https server it will make a huge difference in the connection rate that you'll be able to sustain, RSA computation being by far where most of the CPU is spent. 4096 keys are not viable in a web context. By the way many toolkits support RSA keysize only up to 2048 bits.

Re:Why?

[Hater's Leaving, The]

{{{
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.

here's a quarter

[Anonymous Coward]

Call someone who gives a shit ...

I don't give a rat's ass.

shutup michael

[Anonymous Coward]

so, what sites have you censored lately besides this on?

you will NEVER stop us trolls you fascist goat fucking monster.

Suicide Note

[Anonymous Coward]

Suicide Note (Diaries on Kuro5hin.org)

By Orion Blastar
Sun Jul 28th, 2002 at 04:36:59 PM EST

If you are reading this, it is very likely that I will be gone.

I am tired of living, I am tired of being treated like crap, and I am tired of the way the world is.

I lost my job in November, and I am still unable to get one. Even a small job at a low pay is hard to get, next to impossible.

My depression only seems to be fueled by not having a job, and has continued to get worse.

I've had thoughts of driving my car off a cliff lately, this weekend in fact. Sounds like a good thing to do.
I have a lot of family problems which I don't want to list on here to respect my family's privacy.

My ex-employer, a law firm, may be spreading false rumors about me when someone goes to check with them. I have submitted hundreds of resumes, but only got a few responces back. I suspect they wanted to do the corporate screw job to me long before they let me go. I was out sick with depression, see my other journal entries, before they decided to get rid of me. While against the ADA, I am unable to afford a good lawyer to sue them. The scum suckers didn't even send a "Get Well" card, and when they did call me, they never asked how I was feeling just "when are you coming back to work?"

I tried thinking positive and trying to keep a mental attitude, but that doesn't get very far in this world. I tried my hardest, I really did, and didn't get anywhere.

I don't see the economy getting any better, and all I ever hear about is layoffs. How am I supposed to get a job when companies keep laying people off? I was one of the best VB/ASP developers in my area until we had a flood of H1B Visa Workers and Ex-Dotcommers come into our area. IT salaries are also going down and there is discrimination against IT Workers at some firms like the one I used to work at.

I have serious health issues, and owe a lot in hospital bills. My unemployment runs out in two weeks. I may lose my house, and a while lot more. I really do not see a future for me. Best I can do is end my life and hope that God forgives me and that my friends and family understand.

If by some miricle I still live, I may have to do all this over again in a month or two. My depression cycle seems to be every month or two now.

Re:Suicide Note

[ninkendo84]

I'm new here, but is this a new form of trolling?

Re:Suicide Note

[wirelessbuzzers]

Let's hope so.

Re:Suicide Note

[Anonymous Coward]

What he has said appears consistent with his posting history on kuro5hin so it does not seem to be a troll.

I've had similar thoughts except mine do not involve running my car off a cliff (not many around here) but instead using some variety of firearm.

Re:Suicide Note

[Anonymous Coward]

and all this over his job? Man... at least kill yourself over something more important -- like a realtionship you sunk 4 years into.

Re:Suicide Note

[Anonymous Coward]

Move to a city with more jobs, loser. If you're willing to die, you're willing to not see your friends every day.

Re:Suicide Note

[Anonymous Coward]

advice:

use a credit card to fly to amsterdam.

go to a coffeeshop

keep smoking hash until you change your mind.

the people there will be helpful to talk with.

if you're too straightlaced for that approach go to a hospital. it will be many, many thousands of dollars more expensive but they have new drugs including "risperdal" which you may find very helpful. it will eliminate your current negative mindset. it's not as fun as hash, though.

Re:Suicide Note

[Anonymous Coward]

Oh please. How pathetic. I guaran-frickin'-tee, if this world ever drives me to suicide, I'm taking a whole bunch of motherfuckers with me.

Re:Suicide Note

[Anonymous Coward]

amsterdam has got to be the ass nastiest place on the face of the earth. Soiled diapers in the gutter, stinky people to stoned to shower. Ass Nasty.

Re:Suicide Note

[Anonymous Coward]

i'd like to know what city in this damn country has jobs right now.

yeah maybe if we attack iraq then everything will be all better.

yeah f-ing right.

Re:Suicide Note

[Anonymous Coward]

were you there during tourist season?

besides, here's an algorithm for fixing your problem

while (you give a fuck)
do Smoke-Hash

Re:Suicide Note

[Anonymous Coward]

Read the original an quite a lot of comments at

http://www.kuro5hin.org/story/2002/7/28/163659/7 07

To rthe editors

[peterdaly]

In the future, when editing (you guys do that...right?) Please replace the NFS in this usage with "Number Field Sieve". (That's what this is talking about, right?)

You are confusing all the unix file sharing people. This is like when talking about IP addresses with people who work more with "I"ntelectual "P"roperty.

-Pete

Re:To rthe editors

[Anonymous Coward]

They did, troll boy.

Its the same problem

[jbolden]

Usually you just want p=2 in which case GF(2^m) is embedable in 2^n for large enough n.

Re:Its the same problem

[tomstdenis]

yes you can do ECC over GF(2^m) but you can also do it over GF(p).

[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

[YourMissionForToday]

That must be great for keeping all your child pr0n encrypted, yah dead bastad!

Re:Its the same problem

[Inthewire]

IAgreeWithThisPost

Cost Effective?

[telstar]

We already learned from "Sneakers" what one of these things costs:

• 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.

Oh ... He means performance costs. Nevermind.

Re:Cost Effective?

[Anonymous Coward]

Tahiti is *not* in Europe!

S'funny, I just watched it again two days ago!

Re:Cost Effective?

[Anonymous Coward]

Excuse me sir, when you have the box ... you can give us geography lessons ... until then, this man goes to Tahiti!

-River Phoenix (RIP)

great...

[Anonymous Coward]

now RIAA will make damn sure that new Brittney spears song NEVER gets out of your head.

Re:articals

[Anonymous Coward]

Yeah, tech is supposed to be kewl. Math ain't kewl. No more s#$!!^ ARTICALS!!!!!!! Or I just might find a kewler place with kewler dewds.

all this fs stuff,

[Anonymous Coward]

nfs, afs, bah everyone knows coda is the king. factor that acronym then you wouln't be confused of what nfs is when your reading an article that absolutely doesn't have anything to do with it.

vagina stench?

[Anonymous Coward]

Is your pussy smelly?

Time to update that crypto

[hazyshadeofwinter]

Yeah, I once thought it was secure, but it looks like now I might have to replace my rot13 encryption with rot26, or even rot52...

Re:Time to update that crypto

[richie2000]

I think I'll just write out all my data on paper, bury it in a damp landfill somewhere and let it rot on its own.

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

Re:Time to update that crypto

[hazyshadeofwinter]

Moderation Totals: Funny=3, Overrated=1, Total=4.

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

Re: "Until then"

[Psiven]

Yes indeed, what will happen then? Will the communication be so chaotic that it will be immeasurable, or perhaps it will be so deeply ingrained in the environment that thought police (you know, "them") will have no trouble spying.

Cost model

[blair1q]

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

+1 Informative!

[Anonymous Coward]

MOD THE PARENT UP!!

Reading that post made me wanna get an enema, too.

Key factor

[Taco Cowboy]

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

[a_n_d_e_r_s]

Addding more bits just for the fun of it is not needed.

4096 should suffice for most applications todag.

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

Check out my factorization applets...

[bearnol]

http://www.bearnol.pwp.blueyonder.co.uk/Math/Facto r/Factorfa.html
and
http://www.bearnol.pwp.bluey onder.co.uk/Math/Facto r/Factorwa.html

Funny!.. but you gave too much information.

[leuk_he]

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)

meanwhile, sand niggers are fucking you in the ASS

[Anonymous Coward]

Just thought you'd like to know.

I don't think the kids will like it

[sjonke]

It just sounds way too complicated. What does cost factorization have to do with cute little bears anyway?

Re:Headhunters visiting the site? Off topic

[Anonymous Coward]

I'm so happy about all of these accounting scandals. Not because I like seeing people go out of work, or that I enjoy watching the US economy flush itself down the shitter, but because I have personal reason to hate so many of the banks and firms that are getting slammed. Arthur Andersen consulted for our family business a while back. They charged too much, padded the hell out of the contract, and didn't tell us one thing we didn't know. I have an account with Citibank, 'nuff said. I go to college with the heir to the Chase Manhattan fortune. He's a dick and doesn't deserve a cent.

MODS?

[wirelessbuzzers]

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

The most interesting part

[st.n.]

I think the most interesting part of Bernstein's answer is here. The last paragraph states:

I am astonished that anyone would publish this obvious use of mesh routing as if it were an interesting new result; I am annoyed that my grant proposal has been characterized as presenting slower algorithms than it actually does; and I am particularly disappointed in Lenstra and Shamir for publishing their paper after I informed them in plain language that their claim of an ``improvement'' was false.

And on the same page he cites an email he sent to Arjen Lenstra in April which explains what this all is about in a much more understandable way.