Next: Bibliography
Up: Analysis of Bernstein's Factorization
Previous: Hardware for the matrix
Conclusion
We conclude that methods to evaluate the security of RSA moduli that
are based on the traditional operation count are not affected by the
circuits proposed in [1]. Although the traditional estimates
underestimate the difficulty of factoring, [1] provides yet another
reason -- other than the mostly historical reasons used so far -- not
to rely too much on supposedly more accurate cost-based estimates for the
NFS.
We have shown that the suggestion made in [1] that the number of
digits of factorable numbers has grown by a factor of , is based
on an argument that may not be to everyone's taste. An alternative
interpretation leads to a factor , under the cost function defined
in [1]. The most traditional cost function, however, even leads to
a factor .
Finally, we have presented an improved design for a mesh-based
implementation of the linear algebra stage of the NFS.
For an optimistically estimated 1024-bit
factorization, our analysis suggests that a linear dependency
between the columns of the sparse matrix can be found
within a few hours by a device that costs about $5,000. At the
very least, this is an additional argument not to rely on the alleged
difficulty of the matrix step when evaluating the difficulty of factoring.
As mentioned in [1] there are many other possibilities to
be explored. Further study -- and unbiased interpretation of the
results -- should eventually enable the cryptographic research and users
communities to assess the true impact of [1] and the method
proposed in 5.5.
Acknowledgments.
We thank Daniel J. Bernstein for his constructive criticism [2];
we believe that these concerns are addressed by the present paper.
We thank Martijn Stam for his assistance with the formulas in 2.7,
Scott Contini for his careful reading and his insightful comments,
and Yuliang Zheng for his kind cooperation. The first author thanks
John Markoff for bringing [1] to his attention. The third author worked
at Citibank when the first version of this paper was written.
Next: Bibliography
Up: Analysis of Bernstein's Factorization
Previous: Hardware for the matrix