Advertisement

A Dedicated Sieving Hardware

  • Willi Geiselmann
  • Rainer Steinwandt
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

We describe a hardware device for supporting the sieving step in integer factoring algorithms like the quadratic sieve or the number field sieve. In analogy to Bernstein's proposal for speeding up the linear algebra step, we rely on a mesh of very simple processing units. Manufacturing the device at moderate cost with current hardware technology on standard wafers with 200 mm or 300 mm diameter should not provide any major obstacle.

A preliminary analysis of the parameters for factoring a 512-bit number with the number field sieve shows that the design considered here might outperform a TWINKLE device.

Keywords

factorization number field sieve RSA 

References

  1. [1]
    Daniel J. Bernstein. Circuits for Integer Factorization: a Proposal. At the time of writing available electronically at http://cr.yp.to/papers.html#nfscircuit, 2001. 254, 256, 257
  2. [2]
    Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Hermante Riele, Karen Aardal, Je. Gilchrist, Gérard Guillerm, Paul Leyland, Joël Marchand, François Morain, Alec Muffet, Chris Putnam, Craig Putnam, and Paul Zimmermann. Factorization of a 512-bit RSA Modulus. In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 1–18. Springer, 2000. 255, 262CrossRefGoogle Scholar
  3. [3]
    Marije Elkenbracht-Huizing. An Implementation of the Number Field Sieve. Experimental Mathematics, 5(3):231–253, 1996. 256zbMATHMathSciNetGoogle Scholar
  4. [4]
    Arjen K. Lenstra and Jr. Hendrik W. Lenstra, editors. The development of the number field sieve, volume 1554 of Lecture Notes in Mathematics. Springer, 1993. 255Google Scholar
  5. [5]
    Arjen K. Lenstra and Adi Shamir. Analysis and Optimization of the TWINKLE Factoring Device. In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 35–52. Springer, 2000. 254, 255, 256, 261CrossRefGoogle Scholar
  6. [6]
    Arjen K. Lenstra, Adi Shamir, Jim Tomlinson, and Eran Tromer. Analysis of Bernstein’s Factorization Circuit. At the time of writing available electronically at http://www.cryptosavvy.com/mesh.pdf, 2002. 254, 255, 261
  7. [7]
    Carl Pomerance. A Tale of Two Sieves. Notices of the AMS, 43(12):1473–1485, 1996. 254zbMATHMathSciNetGoogle Scholar
  8. [8]
    Carl Pomerance, J. W. Smith, and Randy Tuler. A pipeline architecture for factoring large integers with the quadratic sieve algorithm. SIAM Journal on Computing, 17:387–403, 1988. 254zbMATHCrossRefMathSciNetGoogle Scholar
  9. [9]
    Manfred Schimmler. Fast sorting on the instruction systolic array. Technical Report 8709, Christian Albrecht Universität Kiel, Germany, 1987. 256Google Scholar
  10. [10]
    Adi Shamir. Factoring Large Numbers with the TWINKLE Device. In Çetin K. Koç and Christof Paar, editors, Cryptographic Hardware and Embedded Systems. First International Workshop, CHES’99, volume 1717 of Lecture Notes in Computer Science, pages 2–12. Springer, 1999. 254CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Willi Geiselmann
    • 1
  • Rainer Steinwandt
    • 1
  1. 1.IAKS, Arbeitsgruppe Systemsicherheit, Prof. Dr. Th. Beth Fakultät für InformatikUniversität KarlsruheKarlsruheGermany

Personalised recommendations