Efficient pipelining for modular multiplication architectures in prime fields

ABSTRACT

This paper presents a pipelined architecture of a modular Montgomery multiplier, which is suitable to be used in public key coprocessors. Starting from a baseline implementation of the Montgomery algorithm, a more compact pipelined version is derived. The design makes use of 16-bit integer multiplication blocks that are available on recently manufactured FPGAs. The critical path is optimized by omitting the exact computation of intermediate results in the Montgomery algorithm using a 6-2 carry-save notation. This results in a high-speed architecture,which outperforms previously designed Montgomery multipliers. Because a very popular application of Montgomery multiplication is public key cryptography, we compare our implementation to the state-of-the-art in Montgomery multipliers on the basis of performance results for 1024-bit RSA.

REFERENCES

• 1: Lejla Batina , Geeke Muurling, Montgomery in Practice: How to Do It More Efficiently in Hardware, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.40-52, February 18-22, 2002
• 2: V. Bunimov and M. Schimmler. Area and time efficient modular multiplication of large integers. In Proceedings of IEEE 14th International Conference on Application-specific Systems, Architectures and Processors (ASAP), pages 400--409. IEEE, 2003.
• 3: C. K. Koc. High-radix and bit recoding techniques for modular exponentiation. International Journal of Computer Mathematics, 40(3+4):139--156, 1991.
• 4: Çetin Kaya Koç , Tolga Acar , Burton S. Kaliski, Jr., Analyzing and Comparing Montgomery Multiplication Algorithms, IEEE Micro, v.16 n.3, p.26-33, June 1996 [doi>10.1109/40.502403]
• 5: K. Kelley and D. Harris. Parallelized very high radix scalable Montgomery multipliers. In Conference Record of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers, pages 1196--1200, 2005.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: P. Kocher, J. Jaffe, and B. Jun. Introduction to differential power analysis and related attacks. http://www.cryptography.com/dpa/technical, 1998.
• 8: K. Manochehri and S. Pourmozafari. Fast Montgomery modular multiplication by pipelined CSA architecture. In Proceedings of International Conference on Microelectronics (ICM), pages 144--147, 2004.
• 9: C. McIvor, M. McLoone, J. McCanny, A. Daly, and W. Marnane. Fast Montgomery Modular Multiplication and RSA Cryptographic Processor Architectures. In Proceedings of 37th Annual Asilomar Conference on Signals, Systems and Computers, pages 379--384, November 2003.
• 10: P. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44:519--521, 1985.
• 11: J.-J. Quisquater and C. Couvreur. Fast decipherment algorithm for RSA public-key cryptosystem. Electronic Letters, 1 (21):905--907, 1982.
• 12: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 13: Alexandre F. Tenca , Çetin Kaya Koç, A Scalable Architecture for Montgomery Multiplication, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.94-108, August 12-13, 1999
• 14: Colin D. Walter, Montgomery's Multiplication Technique: How to Make It Smaller and Faster, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.80-93, August 12-13, 1999
• 15: C. D. Walter. Montgomery exponentiation needs no final subtraction. Electronic letters, 35(21):1831--1832, October 1999.
• 16: Xilinx. Xilinx: The programmable logic company. http://www.xilinx.com, 2006.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Cost/performance

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Security

Keywords:
FPGA, cryptography, montgomery multiplication, public key coprocessor