**Che-Wun Chiou This email address is being protected from spambots. You need JavaScript enabled to view it. ^{1}, Chiou-Yng Lee^{2} , An-Wen Deng^{3} and Jim-Min Lin^{4 }**

^{1}Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C. ^{2}Department of Computer Information and Network Engineering, Lung Hwa University of Science & Technology, Taoyuan, Taiwan 333, R.O.C. ^{3}Department of Information Management, Ching Yun University, Chung-Li, Taiwan 320, R.O.C. ^{4}Department of Information Engineering and Computer Science, Feng Chia University, Taichung City, Taiwan 407, R.O.C.

Received:
September 12, 2005

Accepted:
January 9, 2006

Publication Date:
December 1, 2006

Download Citation:
||https://doi.org/10.6180/jase.2006.9.4.09

**ABSTRACT**

The Montgomery multiplication algorithm without division operations is popular both in prime field GF(p) and Finite field GF(2^{m}). However, the Montgomery multiplication algorithm has the time-dependent problem. We will present a time-independent Montgomery multiplication algorithm. The results show that our proposed time-independent Montgomery multiplication algorithm not only saves about 50% time complexity but also saves about 11% space complexity as compared to the traditional Montgomery multiplication algorithm. Our proposed systolic array Montgomery multiplier has simplicity, regularity, modularity, and concurrency, and is very suitable for VLSI implementation.

Keywords:
Finite Field, Cryptography, ECC, Montgomery Multiplication, Parallel Processing

**REFERENCES**

- [1] MacWilliams, F. J. and Sloane, N. J. A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland (1977).
- [2] Lidl, R. and Niederreiter, H., Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press, U.S.A. (1994).
- [3] Blahut, R. E., Fast Algorithms for Digital Signal Processing, Reading, Mass.: Addison-Wesley (1985).
- [4] Reed, I. S. and Truong, T. K., “The Use of Finite Fields to Compute Convolutions,” IEEE Trans. Information Theory, Vol. IT-21, pp. 208213, (1975).
- [5] Benjauthrit, B. and Reed, I. S., “Galois Switching Functions and Their Applications,” IEEE Trans. Computers, Vol. C-25, pp. 7886 (1976).
- [6] Wang, C. C. and Pei, D., “A VLSI Design for Computing Exponentiation in GF(2m) and Its Application to Generate Pseudorandom Number Sequences,” IEEE Trans. Computers, Vol. 39, pp. 258262 (1990).
- [7] Bartee, T. C. and Schneider, D. J., “Computation with Finite Fields,” Information and Computing, Vol. 6, pp. 7998 (1963).
- [8] Mastrovito, E. D., “VLSI Architectures for Multiplication over Finite Field GF(2m),” Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int’l Conf., AAECC-6, T. Mora, ed., Rome, pp. 297309 (1988).
- [9] Koç, Ç. K. and Sunar, B., “Low-complexity Bit-parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 353356 (1998).
- [10] Lee, C.-Y., “Low Complexity Bit-parallel Systolic Multiplier over GF(2m) Using Irreducible Trinomials,” IEE Proc.-Comput. Digit. Tech., Vol. 150, pp. 3942 (2003).
- [11] Itoh, T. and Tsujii, S., “Structure of Parallel Multipliers for a Class of Fields GF(2m),” Information and Computation, Vol. 83, pp. 2140 (1989).
- [12] Hasan, M. A., Wang, M. and Bhargava, V. K., “Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields GF(2m),” IEEE Trans. Computers, Vol. 41, pp. 962971(1992).
- [13] Lee, C. Y., Lu, E. H. and Lee, J. Y., “Bit-parallel Systolic Multipliers for GF(2m) Fields Defined by All-one and Equally-spaced Polynomials,” IEEE Trans. Computers, Vol. 50, pp. 385393 (2001).
- [14] Paar, C., “A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields,” IEEE Trans. Computers, Vol. 45, pp. 856861 (1996).
- [15] Chiou, C. W., Lin, L. C., Chou, F. H. and Shu, S. F., “Low Complexity Finite Field Multiplier Using Irreducible Trinomials,” Electronics Letters, Vol. 39, pp. 17091711 (2003).
- [16] Massey, J. L. and Omura, J. K., “Computational Method and Apparatus for Finite Field Arithmetic,” U.S. Patent Number 4,587,627, May (1986).
- [17] Reyhani-Masoleh, A. and Hasan, M. A., “A New Construction of Massey-Omura Parallel Multiplier over GF(2m),” IEEE Trans. Computers, Vol. 51, pp. 511 520 (2002).
- [18] Berlekamp, E. R., “Bit-serial Reed-Solomon Encoders,” IEEE Trans. Information Theory, Vol. IT-28, pp. 869874 (1982).
- [19] Wu, H. M., Hasan, A. and Blake, I. F., “New Lowcomplexity Bit-parallel Finite Field Multipliers Using Weakly Dual Bases,” IEEE Trans. Computers, Vol. 47, pp. 12231234 (1998).
- [20] Rivest, R. L., Shamir, A. and Adleman, L., “A Method for Obtaining Digital Signatures and Public-key Cryptosystems,” Comm. ACM, Vol. 21, pp. 120126 (1978).
- [21] Kobltiz, N., “Elliptic Curve Cryptosystems,” Math. Computation, Vol. 48, pp. 203209 (1987).
- [22] Miller, V. S., “Use of Elliptic Curves in Cryptography,” Advances in Cryptology CRYPTO 85 Proceedings, Springer Verlag, pp. 417429 (1986).
- [23] Hoffstein, J., Pipher, J. and Silverman, J. H., “NTRU: A Ring Based Public Key Cryptosystem,” Proc. Algorithmic Number Theory: Third Int’l Symp. (ANTS 3), J.P. Buhler, ed., pp. 267288 (1998).
- [24] Diffie, W. and Hellman, M. E., “New Directions in Cryptography,” IEEE Trans. Information Theory, Vol. 22, pp. 644654 (1976).
- [25] National Institute for Standards and Technology, Digital Signature Standard (DSS). FIPS PUB 186-2, (2000).
- [26] Montgomery, P. L., “Modular Multiplication Without Trial Division”, Math. Computation, Vol. 44, pp. 519 521 (1985).
- [27] Nibouche, O., Bouridane, A. and Nibouche, M., “Architectures for Montgomery’s Multiplication,” IEE Proc.-Comput. Digit. Tech., Vol. 150, pp. 361368 (2003).
- [28] Walter, C. D., “Systolic Modular Multiplication,” IEEE Trans. Computers, Vol. 42, pp. 376378 (1993).
- [29] O’Rourke, C. and Sunar, B., “Achieving NTRU with Montgomery Multiplication,” IEEE Trans. Computers, Vol. 52, pp. 440448 (2003).
- [30] Kornerup, P., “A Systolic, Linear-array Multiplier for a Class of Right-shift Algorithms,” IEEE Trans. Computers, Vol. 43, pp. 892898 (1994).
- [31] Walter, C. D., “Montgomery Exponentiation Needs No Final Subtractions,” Electronics Letters, Vol. 35, pp. 18311832 (1999).
- [32] Bium, T. and Paar, C., “High-radix Montgomery Modular Exponentiation on Reconfigurable Hardware,” IEEE Trans. Computers, Vol. 50, pp. 759764 (2001).
- [33] Koc, K. C. and Acar, T., “Analyzing and Comparing Montgomery Multiplication Algorithms,” IEEE Micro, Vol. 16, pp. 2633 (1996).
- [34] Koc, C. K. and Acar, T., “Montgomery Multiplication in GF(2k ),” Designs, Codes, and Cryptography, Vol. 14, pp. 5769 (1998).
- [35] Wu, H., “Montgomery Multiplier and Squarer in GF(2m),” CHES 2000, LNCS 1965, pp. 264276 (2000).
- [36] Fournaris, A. P. and Koufopavlou, O., “GF(2k ) Multipliers Based on Montgomery Multiplication Algorithm,” Proc. of the IEEE International Symposium on Circuits and Systems, Vol. II, pp. 849852 (2004).
- [37] Bajard, J. C., Imbert, L., Negre, C. and Plantard, T., “Efficient Multiplication in GF(pk ) for Elliptic Curve Cryptography,” IEEE Symp. Computer Arithmetic, pp. 181187 (2003).
- [38] Sava, E., Tenca, A. F. and Koç, Ç. K., “A Scalable and Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m),” CHES 2000, LNCS 1965, pp. 277292 (2000).
- [39] Goodman, J. and Chandrakasan, A. P., “An Energyefficient Reconfigurable Public-key Cryptography Processor,” IEEE Journal of Solid-State Circuits, Vol. 36, pp. 18081820 (2001).
- [40] Großschädl, J., “A Bit-serial Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m),” CHES 2001, LNCS 2162, pp. 202219 (2001).
- [41] Wolkerstorfer, J., “Dual-field Arithmetic Unit for GF(p) and GF(2m),” CHES 2002, LNCS 2523, pp. 500514 (2003).
- [42] Savas, E., Tenca, A. F., Çiftçibasi, M. E. and Koç, Ç. K., “Multiplier Architectures for GF(p) and GF(2n ),” IEE Proceedings-Computers and Digital Technology, Vol. 151, pp.147160 (2004).
- [43] Satoh, A. and Takano, K., “A Scalable Dual-field Elliptic Curve Cryptographic Processor,” IEEE Trans. Computers, Vol. 52, pp. 449460 (2003).
- [44] Gutub, A. A.-A., Tenca, A. F., Savas, E. and Koc, C. K., “Scalable Unified Hardware to Compute Montgomery Inverse in GF(p) and GF(2n ),” CHES 2002, LNCS 2523, pp.484499 (2003).
- [45] Massey, J. L. and Omura, J. K., “Computational Method and Apparatus for Finite Field Arithmetic,” U.S. Patent Number 4,587,627 (1986).
- [46] Jeon, J.-C., Kim, H.-S. and Lee, H.-M., “Bit-serial AB2 Multiplier Using Modified Inner Product,” Journal of Information Science and Engineering, Vol. 18, pp. 507518 (2002).