| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases
January 2006 (vol. 55 no. 1)
pp. 34-47
Recently, implementations of normal basis multiplication over the extended binary field GF(2^{m}) have received considerable attention. A class of low complexity normal bases called Gaussian normal bases has been included in a number of standards, such as IEEE [1] and NIST [2] for an elliptic curve digital signature algorithm. The multiplication algorithms presented there are slow in software since they rely on bit-wise inner product operations. In this paper, we present two vector-level software algorithms which essentially eliminate such bit-wise operations for Gaussian normal bases. Our analysis and timing results show that the software implementation of the proposed algorithm is faster than previously reported normal basis multiplication algorithms. The proposed algorithm is also more memory efficient compared with its look-up table-based counterpart. Moreover, two new digit-level multiplier architectures are proposed and it is shown that they outperform the existing normal basis multiplier structures. As compared with similar digit-level normal basis multipliers, the proposed multiplier with serial output requires the fewest number of XOR gates and the one with parallel output is the fastest multiplier.
[1] 34 IEEE Standard 1363-2000, “IEEE Standard Specifications for Public-Key Cryptography,” Jan. 2000.[2] Nat'l Inst. of Standards and Tech nology, Digital Signature Standard, FIPS Publication 186-2, Jan. 2000.[3] J.L. Massey and J.K. Omura, “Computational Method and Apparatus for Finite Field Arithmetic,” US Patent No. 4,587,627, 1986.[4] M. Feng, “A VLSI Architecture for Fast Inversion in $GF(2^m)$ ,” IEEE Trans. Computers, vol. 38, no. 10, pp. 1383-1386, Oct. 1989.[5] T. Beth and D. Gollman, “Algorithm Engineering for Public Key Algorithms,” IEEE J. Selected Areas in Comm., vol. 7, no. 4, pp. 458-465, May 1989.[6] W. Geiselmann and D. Gollmann, “Symmetry and Duality in Normal Basis Multiplication,” Proc. Sixth Symp. Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC-6), pp. 230-238, July 1988.[7] G.B. Agnew, R.C. Mullin, I.M. Onyszchuk, and S.A. Vanstone, “An Implementation for a Fast Public-Key Cryptosystem,” J. Cryptology, vol. 3, pp. 63-79, 1991.[8] R.C. Mullin, “Multiple Bit Multiplier,” US Patent No. 5,787,028, July 1998.[9] L. Gao and G.E. Sobelman, “Improved VLSI Designs for Multiplication and Inversion in $GF(2^M)$ over Normal Bases,” Proc. 13th Ann. IEEE Int'l ASIC/SOC Conf., pp. 97-101, 2000.[10] A. Reyhani-Masoleh and M.A. Hasan, “Low Complexity Word-Level Sequential Normal Basis Multipliers,” IEEE Trans. Computers, vol. 54, no. 2, pp. 98-110, Feb. 2005.[11] C.C. Wang, T.K. Truong, H.M. Shao, L.J. Deutsch, J.K. Omura, and I.S. Reed, “VLSI Architectures for Computing Multiplications and Inverses in $GF(2^m)$ ,” IEEE Trans. Computers, vol. 34, no. 8, pp. 709-716, Aug. 1985.[12] B. Sunar and C.K. Koç, “An Efficient Optimal Normal Basis Type II Multiplier,” IEEE Trans. Computers, vol. 50, no. 1, pp. 83-88, Jan. 2001.[13] A. Reyhani-Masoleh and M.A. Hasan, “A New Construction of Massey-Omura Parallel Multiplier over $GF(2^m)$ ,” IEEE Trans. Computers, vol. 51, no. 5, pp. 511-520, May 2002.[14] P. Ning and Y.L. Yin, “Efficient Software Implementation for Finite Field Multiplication in Normal Basis,” Proc. Int'l Conf. Information and Comm. Security (ICICS 2001), pp. 177-181, Nov. 2001.[15] Y.L. Yin and P. Ning, “Efficient Finite Field Multiplication in Normal Basis,” US Patent No. 6,389,442, May 2002. Assignee: RSA Security Inc.[16] A. Reyhani-Masoleh and M.A. Hasan, “Fast Normal Basis Multiplication Using General Purpose Processors,” IEEE Trans. Computers, vol. 52, no. 11, pp. 1379-1390, Nov. 2003.[17] H. Fan and Y. Dai, “Two Software Normal Basis Multiplication Algorithms for $GF(2^n)$ ,” Report 2004/126, Cryptology ePrint Archive, 2004, http:/eprint.iacr.org/.[18] R. Dahab, D. Hankerson, F. Hu, M. Long, J. López, and A. Menezes, “Software Multiplication Using Normal Bases,” Technical Report CACR 2004-12, Centre for Applied Cryptographic Research, Univ. of Waterloo, Canada, Dec. 2004, IEEE Trans. Computers, to appear.[19] D.W. Ash, I.F. Blake, and S.A. Vanstone, “Low Complexity Normal Bases,” Discrete Applied Math., vol. 25, pp. 191-210, 1989.[20] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications. Cambridge Univ. Press, 1994.[21] A. Reyhani-Masoleh, “Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases,” Technical Report CACR 2004-04, Centre for Applied Cryptographic Research, Univ. of Waterloo, Canada, July 2004.[22] A. Reyhani-Masoleh and M.A. Hasan, “Efficient Digit-Serial Normal Basis Multipliers over $GF(2^m)$ ,” ACM Trans. Embedded Computing Systems (TECS), special issue on embedded systems and security, vol. 3, no. 3, pp. 575-592, Aug. 2004.[23] R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone, and R.M. Wilson, “Optimal Normal Bases in $GF(p^n)$ ,” Discrete Applied Math., vol. 22, pp. 149-161, 1988/1989.[24] D. Johnson, A. Menezes, and S. Vanstone, “The Elliptic Curve Digital Signature Algorithm (ECDSA),” Int'l J. Information Security, vol. 1, pp. 36-63, 2001.[25] C.C. Wang, “An Algorithm to Design Finite Field Multipliers Using a Self-Dual Normal Basis,” IEEE Trans. Computers, vol. 38, no. 10, pp. 1457-1460, Oct. 1989.[26] S. Gao, J. Gathen, D. Panario, and V. Shoup, “Algorithms for Exponentiation in Finite Fields,” J. Symbolic Computation, vol. 29, pp. 879-889, 2000.[27] M. Rosing, Implementing Elliptic Curve Cryptography. Manning Publications Company, 1999.[28] S. Kwon, K. Gaj, C.H. Kim, and C.P. Hong, “Efficient Linear Array for Multiplication in $GF(2^m)$ Using a Normal Basis for Elliptic Curve Cryptography,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES 2004), pp. 76-91, Aug. 2004.[29] D. Hankerson, J. Hernandez, and A. Menezes, “Software Implementation of Elliptic Curve Cryptography over Binary Fields,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES 2000), pp. 1-24, 2000.[30] C.-C. Lu, “A Search of Minimal Key Functions for Normal Basis Multipliers,” IEEE Trans. Computers, vol. 46, no. 5, pp. 588-592, May 1997.[31] L. Song and K.K. Parhi, “Low-Energy Digit-Serial/Parallel Finite Field Multipliers,” J. VLSI Signal Processing, vol. 19, pp. 149-166, 1998.[32] D.J. Yang, C.H. Kim, Y. Park, Y. Kim, and J. Lim, “Modified Sequential Normal Basis Multipliers for Type II Optimal Normal Bases,” Proc. Int'l Conf. Computation Science and Its Applications (ICCSA 2005), pp. 647-656, May 2005.[33] M. Elia and M. Leone, “On the Inherent Space Complexity of Fast Parallel Multipliers for $GF(2^m)$ ,” IEEE Trans. Computers, vol. 51, no. 3, pp. 346-351, Mar. 2002.
Index Terms:
Index Terms- Finite field multiplication, normal basis, Gaussian normal basis, software algorithms, ECDSA.
Citation:
Arash Reyhani-Masoleh, "Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases," IEEE Transactions on Computers, vol. 55, no. 1, pp. 34-47, Jan. 2006, doi:10.1109/TC.2006.10
