Reconfigurable solutions for very-long arithmetic with applications in cryptography

ABSTRACT

We present a cryptography-oriented reconfigurable array called CryptoRA that efficiently supports very long-integer addition and subtraction. We first describe the CryptoRA architecture and show that extending the dedicated carry chains of modern FPGAs over the orthogonal direction, followed by merging two FPGA columns to create computing tiles that support both generate and propagate signals of a carry-lookahead network, provides a reduction in operation latency. Then, we show that splitting a tile's Look-Up Table into two halves provides additional benefits in terms of latency and flexibility in using the dedicated generate and propagate chains. According to our estimations, long-integer addition widely used in cryptography is more than 22% faster on CryptoRA than on Virtex-II Pro FPGA. This improvement has a large positive impact on implementing cryptography applications in embedded environments.

REFERENCES

• 1: Altera Corporation, http://www.altera.com/.
• 2: Altera Corporation, Stratix Device Handbook. Altera Corporation, San Jose, California, January 2006.
• 3: Thomas Blum, Montgomery Modular Exponentiation on Reconfigurable Hardware, Proceedings of the 14th IEEE Symposium on Computer Arithmetic, p.70, April 14-16, 1999
• 4: Duncan A. Buell , Kenneth L. Pocek, Custom computing machines: an introduction, The Journal of Supercomputing, v.9 n.3, p.219-229, 1995 [doi>10.1007/BF01212869]
• 5: Canadian Microelectronics Corporation (CMC Microsystems). http://www.cmc.ca/.
• 6: Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002 [doi>10.1145/508352.508353]
• 7: Andre DeHon, Reconfigurable Architectures for General-Purpose Computing, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 8: André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
• 9: André DeHon, The Density Advantage of Configurable Computing, Computer, v.33 n.4, p.41-49, April 2000 [doi>10.1109/2.839320]
• 10: Milos D. Ercegovac and Tomas Lang. Digital Arithmetic. Morgan Kaufmann, 2003.
• 11: James Goodman and Anantha P. Chandrakasan. An Energy--Efficient IEEE 1363--based Reconfigurable Public--Key
• 12: Cryptography Processor. In The IEEE Intl. Solid--State Circuits Conf., pp. 330--331, 461--462, San Francisco, California, February 2001.
• 13: James Goodman and Anantha P. Chandrakasan. An Energy--Efficient Reconfigurable Public--Key Cryptography Processor. IEEE J. Solid--State Circuits, 36(11):1808--1820, November 2001.
• 14: Darrel Hankerson , Alfred J. Menezes , Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 15: Scott Hauck , Thomas W. Fry , Matthew M. Hosler, High-performance carry chains for FPGA's, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.2, p.138-147, April 2000 [doi>10.1109/92.831434]
• 16: Scott A. Hauck. The Roles of FPGA's in Reprogrammable Systems. Proc. IEEE, 86(4):615--638, April 1998.
• 17: Gerry Kane, MIPS RISC architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 18: Neal Koblitz. Elliptic curve cryptosystem. In Mathematics of Computation, number 48, April 1987.
• 19: Ruby B. Lee , Zhijie Shi , Xiao Yang, Cryptography Efficient Permutation Instructions for Fast Software, IEEE Micro, v.21 n.6, p.56-69, November 2001 [doi>10.1109/40.977759]
• 20: Scott MILLER , Mihai SIMA , Michael McGUIRE, Alternatives in Designing Level-Restoring Buffers for Interconnection Networks in Field-Programmable Gate Arrays, Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, p.138-146, August 29-31, 2007 [doi>10.1109/DSD.2007.22]
• 21: Peter L. Montgomery. Modular multiplication without trial division. In Mathematics of Computation, vol. 44, April 1985.
• 22: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 23: 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]
• 24: Michael Rosing, Implementing elliptic curve cryptography, Manning Publications Co., Greenwich, CT, 1999
• 25: Akashi Satoh , Y. Kobayashi , H. Niijima , Nobuyuki Ooba , Seiji Munetoh , S. Sone, A High-Speed Small RSA Encryption LSI with Low Power Dissipation, Proceedings of the First International Workshop on Information Security, p.174-187, September 17-19, 1997
• 26: David Seal, ARM Architecture Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 27: Shamus Software Ltd. Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL), 2005. http://www.shamus.ie.
• 28: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 29: Wade Trappe , Lawrence C. Washington, Introduction to Cryptography with Coding Theory (2nd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2005
• 30: Xilinx Corporation. Virtex--II Platform FPGAs: Complete Data Sheet. Data Sheet DS031, San Jose, California, November 2007.
• 31: Xilinx Incorporated., http://www.xilinx.com/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms; Cost/performance
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Performance

Keywords:
cryptography, embedded systems, field-programmable gate arrays, reconfigurable computing