Slashdot Mirror
More on Bernstein's Number Field Sieve
Russ Nelson writes "Dan Bernstein has a response to Bernstein's
NFS analyzed by Lenstra and Shamir, entitled Circuits for integer
factorization. He notes that the issue of the cost of
factorization is still open, and that it may in fact be inexpensive to
factor 1024-bit keys. We don't know, and that's what his research is
intended to explore."
... this is. I especially like the mixture of theoretical, practical and yet unknowen aspects of the whole problem.
My impression is that so far DJB has done a good job of being honest and clear. Although "the press" is sadly lacking in experts these days and often will not even notice they have not understood the problem. I have to admit that I did not quite follow
Lenstra-Shamir-Tomlinson-Tromer, but I think DJB's original proposal is still the best source on what is going on. No real surprises so far for practical purposes, but I will follow this closely.
Incidentally I don't fear for my 4096/1024 bit ElGamal/DSA gpg key in the near future. I am confident that installing a keyboard sniffer without me noticing is far easier than breaking that key.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted and ignored otherwise.
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
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.
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.
#define sig "Every social system runs on the people's belief in it."