next up previous
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 $ 3$, is based on an argument that may not be to everyone's taste. An alternative interpretation leads to a factor $ 1.17$, under the cost function defined in [1]. The most traditional cost function, however, even leads to a factor $ 0.92$. 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 up previous
Next: Bibliography Up: Analysis of Bernstein's Factorization Previous: Hardware for the matrix