Hardware speedups in long integer multiplication

ABSTRACT

We present various experiments in Hardware/Software design tradeoffs met in speeding up long integer multiplications. This work spans over a year, with more than 12 different hardware designs tested and measured.To implement these designs, we rely on our PAM (for Programmable Active Memory, see [BRV]) technology which provides us with a 50 millisecond turn-around time silicon foundry for implementing up to 50K gate logic designs fully equipped with fast local RAM and host bus interface.First, we demonstrate how a simple hardware 512 bits integer multiplier coupled with a low end workstation host yields performance on long arithmetic superior to that of the fastest computers for which we could obtain actual benchmark figures.Second, we specialize this hardware in order to speed-up one specific application of long integer arithmetic, namely Rivest-Shamir-Adleman public-key cryptography [RSA]. We demonstrate how a single host driving 3 differently configured PAM boards delivers RSA encryption and decryption faster than 200Kbits/sec for 512 bits keys. This beats the best currently working VLSI specially built for RSA by one order of magnitude.

REFERENCES

• 1: H. J. Boehm, Constructive real interpretation of numerical programs, Papers of the Symposium on Interpreters and interpretive techniques, p.214-221, June 24-26, 1987, St. Paul, Minnesota, United States
• 2: Ernest F. Brickell, A Survey of Hardware Implementation of RSA (Abstract), Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.368-370, August 20-24, 1989
• 3: P. Bertin , D. Roncin , J. Vuillemin, Introduction to programmable active memories, Systolic array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 4: [BW] D. A. Buell, R. L. Ward, A Multiprecise Integer Arithmetic Package, The journal of Supercomputing 3, pp. 89-107, Kluwer Academic Publishers, Boston 1989.
• 5: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: [L] R. F Lyon Two's complement pipeline multipliers, IEEE Trans. Comm., COM-24: 418-425, 1976.
• 7: [LV] J. C. Las Vergnas, C. Vatinel Implémentation d'un multiplicateur 256 bits rapide sur une carte reconfigurable. Application à la cryptographie RSA, Digital Equipment Corp., Paris Research Laboratory, Internal Document. July 1989.
• 8: [LM] A. K. Lenstra, M. S. Manasse Factoring by electronic mail, in Proceedings of Eurocrypt 1989, Springer Verlag Lecture Notes in Computer Science, 1990.
• 9: [Mon] P. L. Montgomery Modular multiplication without trial division, Math. Comp. 44, 170, pp. 519-521, 1985.
• 10: [Mor] F. Morain Implementation of the Atkin-Goldwasser-Killiau primality testing algorithm, Rapport de recherche INRIA #911, October 1988.
• 11: [RSA] R. L. Rivest, A. Shamir, L. Adleman Public key cryptography , CACM 21, 120-126, 1979.
• 12: [SVH] B. Serpette, J. Vuillemin, J. C. Hervé A Portable Efficient Package for Arbitrary-Precision Arithmetic, PRL report 2, Digital Equipment Corp., Paris Research Laboratory, 85, Av. Victor Hugo. 92563 Rueil-Malmaison Cedex, France.
• 13: [X] Xilinx The Programmable Gate Array Data Book, Product Briefs, Xilinx, Inc., 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory