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."
Do you have a
... 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.
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...
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.
Or you can be smart and stop using RSA. In the realm of things the DLP over GF(p) is harder to solve then the IFP.
Even harder is the DLP over eliptic curves. With proper curves [e.g. NIST supplied ones] the best attacks on the math take SQRT work which means a 256-bit ECC key will take roughly 2^128 work to solve for the private key [from the public key], provided the cryptosystem is setup correctly [yadada].
Tom
Someday, I'll have a real sig.
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
Don't piss off The Angry Economist
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.
Could you elaborate more on the "reverse log" problem... If you know the base and the result of [Log x], whats the problem?
The OP got his terminology wrong. It's the discrete log problem that's hard.
Pick a number (e.g. 3.81482), plug it into your calculator and press e^x (result = 45.36874). Now it's easy to get back the original number by using the "ln" key. But imagine instead that you only had the fractional portion of the result (.36874). Now it's next to impossible to figure out what the original number was. The discrete log problem is basically the same this, but using discrete arithmetic instead of real arithmetic.
-a
How to rationalize theft.
I didn't really think there was any need for anything better than 128 bit encryption. It would take a lot of factoring that is practically impossible by human standards to figure out the key for a 32 bit encrypted code, and this site [stack.nl] seems to tell me that 128 bit encryption is nearly impossible to break by any standards.
128-bit private key encryption is considered virtually unbreakable. 128-bit public key encryption is not. AES is an example of private key encryption; RSA is an example of public key encryption.
-a
How to rationalize theft.
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.
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.
I'll say! Arthur Andersen has advanced number theory further than anyone had imagined it could go!
Do you even lift?
These aren't the 'roids you're looking for.
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
How to rationalize theft.
No. The phrase "security through obscurity" generally means that the security algorithm is kept a secret. The lock on your house is a good example - how the lock works is open, public information. The particular key that you use, however, is not. To unlock your door, someone must either learn what key you use or exploit weaknesses in the lock. A standard locksmith text, some standard locksmith tools, and a little time is all that's required to pick the standard lock. How the lock works is not obscured; what key you use is.
:)
Since everyone knows how the lock works, everyone can see what the weaknesses are and everyone can try to correct them (this has been done over the last couple of centuries). If you used a non-standard lock with a mode of operation that only you knew, that would be security through obscurity. No one can learn to pick it by reading standard locksmith texts. The weaknesses would have to be learned through trial and error by someone on your front porch. Any lockpicker would have to learn not only what key you used but how to use it in the lock.
Public key encryption generally uses well-known algoorithms - this is what makes it not obscure. The keys are secret, just as with obscure systems. However, everyone can see whether or not the system is a strong one.
Go read Cryptonomicon for a fictional introduction to the perils of obscured cryptosystems, as well as the benefits of open ones. Then read Applied Cryptography for the real (ie technical and mathematical and correct) deal. Or just take my word for it like a happy little slashdotizen.
BTW, modern locks are the result of a couple hundred years of improvements and refinements; they are currently about as good as they need to be, given weaknesses of the door itself, the convenience of regularly using the mechanism, the cost of the lock and keys, etc. Cryptosystems are nowhere near that level yet. The internet is still a country town, in the sense that everyone leaves their house unlocked and their keys in the ignition of their car. Once everyone's been hacked a couple of times (and I do mean everyone), adoption of crypto will become widespread, and we'll begin to see sufficient standardization to make crypto comparable to real-life locks. Government officials don't whine about locks the way they do about crypto for good reason - they aren't much more than courtesy and inconvenience devices. Give me a good sledgehammer and I'll be in your door in five minutes. Give me a power saw and I'll make my own door. Betcha the standardized crypto will be similar.
I'm curious: did you read what I wrote or are you replying to the original poster to whom I was writing?
-russ
Don't piss off The Angry Economist
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
Don't piss off The Angry Economist
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.
There's no point in questioning authority if you aren't going to listen to the answers.
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.)
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...
Click here if you just like to click on shit.
What we need is an encryption system that isn't based on math.
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
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 !
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!
That doesn't make sense.
Did you mean "0 = y mod p"?
You took the words out of my mouth.
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.
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.