TY - GEN
T1 - Analysis of Bernstein's factorization circuit
AU - Lenstra, A.K.
AU - Shamir, A.
AU - Tomlinson, J.
AU - Tromer, E.
PY - 2002
Y1 - 2002
N2 - In [1], Bernstein proposed a circuit-based implementation of the matrix step of the number field sieve factorization algorithm. These circuits offer an asymptotic cost reduction under the measure "construction cost x run time". We evaluate the cost of these circuits, in agreement with [1], but argue that compared to previously known methods these circuits can factor integers that are 1.17 times larger, rather than 3.01 as claimed (and even this, only under the non-standard cost measure). We also propose an improved circuit design based on a new mesh routing logarith, and show that for factorization of 1024-bit integers the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars. We conclude that from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve.
AB - In [1], Bernstein proposed a circuit-based implementation of the matrix step of the number field sieve factorization algorithm. These circuits offer an asymptotic cost reduction under the measure "construction cost x run time". We evaluate the cost of these circuits, in agreement with [1], but argue that compared to previously known methods these circuits can factor integers that are 1.17 times larger, rather than 3.01 as claimed (and even this, only under the non-standard cost measure). We also propose an improved circuit design based on a new mesh routing logarith, and show that for factorization of 1024-bit integers the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars. We conclude that from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve.
U2 - 10.1007/3-540-36178-2_1
DO - 10.1007/3-540-36178-2_1
M3 - Conference contribution
SN - 3-540-00171-9
T3 - Lecture Notes in Computer Science
SP - 1
EP - 26
BT - Advances in Cryptology - ASIACRYPT 2002 (Proceedings 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002)
A2 - Zheng, Y.
PB - Springer
CY - Berlin
ER -