> Here's a real question: if you could build a special purpose machine
> to do 1024 bit RSA keys (that is, factor a 1024 bit number), how much
> would that help with discrete logs in a safe prime field?
Solving discrete logs via NFS is structurally similar to factoring.
You start off with a factor base and generate a large number of
relations among the elements in that set. You then look for a linear
dependency among these relations, which amounts to solving a large matrix.
Since the techniques are similar, Dan Bernstein's ideas probably apply
to both cases.
However there are some significant differences, mostly in the second
phase, the matrix reduction. The matrix solution in the case of
factoring is over GF(2). This means that all the elements are 0's and
1's, that "addition" is just XOR, and that "multiplication" is just AND.
This simplifies the problem and Bernstein uses a trick to speed up matrix
multiplication in this field.
Bernstein's insight is that matrix multiplication in GF(2) is essentially
just a matching problem. When you have two 1's being multiplied together,
you keep them; if either one is a 0, you can eliminate that. During the
addition, if you have two matching elements, they cancel; if they are
unlike elements, they produce a 1. So what he does is to put the data
into a giant sorting engine. This brings the corresponding elements
close together. Then a couple of passes of these matching rules gives
the result.
The matrix solution for discrete log is over a larger field, the size of
the large prime that divides p-1; 1023 bits for a strong 1024 bit key.
You don't have just 0's and 1's, and you no longer have simple matching
rules. The field operations are non-trivial.
This will have several effects. First, the cells of the solver will have
to be larger; in addition to storing row and column numbers, they have to
store a large numeric value. Second, the cells will have to include much
more complex logic; instead of just comparing with their neighbors and
looking for matches, they have to do modular multiplication and addition.
And third, the algorithm will change during the addition phase; a series
of values have to be added together, rather than just counting whether
there are an even or odd number. This probably doesn't increase the
asymptotic number of steps, though.
So the matrix solver will be considerably larger, but if the factoring
version were buildable, the DL version probably could be built as well.
Given the increased complexity of the cell, from doing ANDs of ~40 bit
numbers to doing modular multiplication of ~1000 bit values, a very rough
guess is that it will be 1000 times more expensive. It may be possible
to compensate for this greater cost by using a smaller factor base.
The first phase in both algorithms involves finding numbers smooth over a
factor base, so again the success of a factoring engine probably implies
that the discrete log machine would work, too.
Summing up, Bernstein's techniques would require some modification for
solving discrete logs, and the details of the asymptotic analysis would
probably not be exactly the same, but broadly speaking the same general
techniques would apply. If his machine factors 1024 bit numbers at
some reasonable expense, 1024 bit discrete log keys would have to be
considered unsafe as well.
