GF(2m) 상의 여분 표현을 이용한 낮은 지연시간의 몽고메리 AB2 곱셈기
Low-latency Montgomery AB2 Multiplier Using Redundant Representation Over GF(2m)
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
Finite field arithmetic has been extensively used in error correcting codes and cryptography. Low‑complexity and high‑speed designs for finite field arithmetic are needed to meet the demands of wider bandwidth, better security and higher portability for personal communication device. In particular, cryptosystems in GF(2m) usually require computing exponentiation, division, and multiplicative inverse, which are very costly operations. These operations can be performed by computing modular AB multiplications or modular AB2 multiplications. To compute these time-consuming operations, using AB2 multiplications is more efficient than AB multiplications. Thus, there are needs for an efficient AB2 multiplier architecture. In this paper, we propose a low latency Montgomery AB2 multiplier using redundant representation over GF(2m). The proposed AB2 multiplier has less space and time complexities compared to related multipliers. As compared to the corresponding existing structures, the proposed AB2 multiplier saves at least 18% area, 50% time, and 59% area-time (AT) complexity. Accordingly, it is well suited for VLSI implementation and can be easily applied as a basic component for computing complex operations over finite field, such as exponentiation, division, and multiplicative inverse.
Abstract
Finite field arithmetic has been extensively used in error correcting codes and cryptography. Low‑complexity and high‑speed designs for finite field arithmetic are needed to meet the demands of wider bandwidth, better security and higher portability for personal communication device. In particular, cryptosystems in GF(2m) usually require computing exponentiation, division, and multiplicative inverse, which are very costly operations. These operations can be performed by computing modular AB multiplications or modular AB2 multiplications. To compute these time-consuming operations, using AB2 multiplications is more efficient than AB multiplications. Thus, there are needs for an efficient AB2 multiplier architecture. In this paper, we propose a low latency Montgomery AB2 multiplier using redundant representation over GF(2m). The proposed AB2 multiplier has less space and time complexities compared to related multipliers. As compared to the corresponding existing structures, the proposed AB2 multiplier saves at least 18% area, 50% time, and 59% area-time (AT) complexity. Accordingly, it is well suited for VLSI implementation and can be easily applied as a basic component for computing complex operations over finite field, such as exponentiation, division, and multiplicative inverse.
참고문헌 (25)
- A. J. Menezes, "Handbook of Applied Cryptography" (1996), CRC Press
- R. E. Blahut, "Theory and Practice of Error Control Codes" (1983), Addison-Wesley
- N. Kobliz, "Elliptic curve cryptography", Math. Computation, 48(177), pp.203~209 (1987)
- P. Montgomery, "Modular multiplication without trial division", Mathematics of Computation, 44(170), pp.519~521 (1985)
- C. K. Koc, "Montgomery multiplication in GF(2k)", Designs Codes and Cryptography, 14, pp.57~69 (1998)
- C. Y. Lee, "Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2m)", IEEE Transactions on Computers, 54(9), pp.1061~1070 (2005)
- C. W. Chiou, "Concurrent error detection in Montgomery multiplication over GF(2m)", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A(2), pp.566~574 (2006)
- A. Hariri, "Bit-serial and bit-parallel Montgomery multiplication and squaring over GF(2m)", IEEE Transactions on Computers, 58(10), pp.1332~1345 (2009)
- A. Hariri, "Concurrent error detection in Montgomery multiplication over binary extension fields", IEEE Transactions on Computers, 60(9), pp.1341~1353 (2011)
- K. W. Kim, "Efficient cellular automata based Montgomery AB2 multipliers over GF(2m)", IETE Technical Review, 31(1), pp.92~102 (2014)
- K. W. Kim, "Polynomial basis multiplier using cellular systolic architecture", IETE Journal of Research, 60(2), pp.194~199 (2014)
- S. H. Choi, "Low complexity semi-systolic multiplication architecture over GF(2m)", IEICE Electron. Express, 11(20), pp.20140713~ (2014)
- K. W. Kim, "A semi-systolic Montgomery multiplier over GF(2m)", IEICE Electonics Express, 12(21), pp.20150769~ (2015)
- H. H. Lee, "Efficient semi-systolic finite field multiplier using redundant basis", International Journal of Computer, Electrical, Automation, Control and Information Engineering, 10(10), pp.1614~1618 (2016)
- S. W. Wei, "A systolic power-sum circuit for GF(2m)", IEEE Transactions on Computers, 43(2), pp.226~229 (1994)
- C. L. Wang, "New systolic arrays for C+AB2, inversion, and division in GF(2m)", IEEE Transactions on Computers, 49(10), pp.1120~1125 (2000)
- C. H. Liu, "Computation of AB2 multiplier in GF(2m)using an efficient low-complexity cellular architecture", IEICE Transactions on Fundamentals of Electronics, E83-A(12), pp.2657~2663 (2000)
- C. Y. Lee, "Low-complexity bit-parallel systolic architecture for computing AB2+C in a class of finite field GF(2m)", IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 48(5), pp.519~523 (2001)
- Y. R. Ting, "Low complexity bit-parallel systolic architecture for computing C+AB2 over a class of GF(2m)", INTEGRATION, the VLSI journal, 37(3), pp.167~176 (2004)
- C. Y. Lee, "Low-complexity bit-parallel systolic architectures for computing A(x)B2(x) over GF(2m)", IEEE Proceedings of Circuits Devices and Systtems, 153(4), pp.399~406 (2006)
- K. W. Kim, "Low-complexity parallel and serial systolic architectures for AB2 multiplication in GF(2m)", IETE Technical Review, 30(2), pp.134~141 (2013)
- K. W. Kim, "An efficient parallel systolic array for AB2 over GF(2m)", IEICE Electronics Express, 10(20), pp.20130585~ (2013)
- K. W. Kim, "Efficient cellular automata based Montgomery AB2 multipliers over GF(2m)", IETE Technical Review, 31(1), pp.92~102 (2014)
- G. Drolet, "A new representation of elements of finite fields yielding small complexity arithmetic circuits", IEEE Transactions on Computers, 47(9), pp.938~946 (1998)
- H. Wu, "Finite field multiplier using redundant representation", IEEE Transactions on Computers, 51(11), pp.1306~1316 (2002)