여분 기저를 이용한 멀티플렉서 기반의 유한체 곱셈기
Multiplexer-Based Finite Field Multiplier Using Redundant Basis
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Finite field operations have played an important role in error correcting codes and cryptosystems. Recently, the necessity of efficient computation processing is increasing for security in cyber physics systems. Therefore, efficient implementation of finite field arithmetics is more urgently needed. These operations include addition, multiplication, division and inversion. Addition is very simple and can be implemented with XOR operation. The others are somewhat more complicated than addition. Among these operations, multiplication is the most important, since time-consuming operations, such as exponentiation, division, and computing multiplicative inverse, can be performed through iterative multiplications. In this paper, we propose a multiplexer based parallel computation algorithm that performs Montgomery multiplication over finite field using redundant basis. Then we propose an efficient multiplexer based semi-systolic multiplier over finite field using redundant basis. The proposed multiplier has less area-time (AT) complexity than related multipliers. In detail, the AT complexity of the proposed multiplier is improved by approximately 19% and 65% compared to the multipliers of Kim-Han and Choi-Lee, respectively. Therefore, our multiplier is suitable for VLSI implementation and can be easily applied as the basic building block for various applications.
Abstract
Finite field operations have played an important role in error correcting codes and cryptosystems. Recently, the necessity of efficient computation processing is increasing for security in cyber physics systems. Therefore, efficient implementation of finite field arithmetics is more urgently needed. These operations include addition, multiplication, division and inversion. Addition is very simple and can be implemented with XOR operation. The others are somewhat more complicated than addition. Among these operations, multiplication is the most important, since time-consuming operations, such as exponentiation, division, and computing multiplicative inverse, can be performed through iterative multiplications. In this paper, we propose a multiplexer based parallel computation algorithm that performs Montgomery multiplication over finite field using redundant basis. Then we propose an efficient multiplexer based semi-systolic multiplier over finite field using redundant basis. The proposed multiplier has less area-time (AT) complexity than related multipliers. In detail, the AT complexity of the proposed multiplier is improved by approximately 19% and 65% compared to the multipliers of Kim-Han and Choi-Lee, respectively. Therefore, our multiplier is suitable for VLSI implementation and can be easily applied as the basic building block for various applications.
참고문헌 (21)
- R.E. Blahut, "Theory and Practice of Error Control Codes" (1983), Addison-Wesley
- A.J. Menezes, "Handbook of Applied Cryptography" (1996), CRC Press
- N. Kobliz, "Elliptic Curve Cryptography", Journal of Math. Computation, 48(177), pp.203~209 (1987)
- 박수열, "사이버-물리 시스템의 보안 프레임워크 개발을 위한 보안 요구사항 분석 연구", 대한임베디드공학회논문지, 7(5), pp.255~265 (2012), 대한임베디드공학회
- M. Wolf, "Safety and Security in Cyber-Physical Systems and Internet-of-Things Systems", Proceedings of the IEEE, 106(1), pp.9~20 (2018)
- P. Montgomery, "Modular Multiplication Without Trial Division", Journal of Mathematics of Computation, 44(170), pp.519~521 (1985)
- C.K. Koc, "Montgomery multiplication in GF (2k)", Journal of Designs Codes and Cryptography, 14(1), pp.57~69 (1998)
- C.Y. Lee, "Low-complexity Bit-parallel Systolic Montgomery Multipliers for Special Classes of GF (2m)", Journal of IEEE Transactions on Computers, 54(9), pp.1061~1070 (2005)
- C.W. Chiou, "Concurrent Error Detection in Montgomery Multiplication Over GF (2m)", Journal of Institute of Electronics, Information and Communication Engineers Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 89(2), pp.566~574 (2006)
- A. Hariri, "Bit-serial and Bit-parallel Montgomery Multiplication and Squaring over GF (2m)", Journal of IEEE Transactions on Computers, 58(10), pp.1332~1345 (2009)
- K.W. Kim, "A Semi-systolic Montgomery Multiplier over GF(2m)", Journal of Institute of Electronics, Information and Communication Engineers Electronics Express, 12(21), pp.20150769~ (2015)
- W.T. Huang, "Concurrent Error Detection and Correction in a Polynomial Basis Multiplier over GF (2m)", Journal of Institution of Engineering and Technology Information Security, 4(3), pp.111~124 (2010)
- K.W. Kim, "A Low Latency Semi-systolic Multiplier over GF (2m)", Journal of Institute of Electronics, Information and Communication Engineers Electronics Express, 10(13), pp.20130354~ (2013)
- 김기원, "기약 AOP를 이용한 GF(2m)상의 낮은 지연시간의 시스톨릭 곱셈기", 대한임베디드공학회논문지, 11(4), pp.227~233 (2016), 대한임베디드공학회[DOI]
- S.H. Choi, "Low Complexity Semi-systolic Multiplication Architecture over GF (2m)", Journal of Institute of Electronics, Information and Communication Engineers Electronics Express, 11(20), pp.20140713~ (2014)
- 김태완, "GF(2m) 상의 여분 표현을 이용한 낮은 지연시간의 몽고메리 AB2 곱셈기", 대한임베디드공학회논문지, 12(1), pp.11~18 (2017), 대한임베디드공학회[DOI]
- G. Drolet, "A New Representation of Elements of Finite Fields Yielding Small Complexity Arithmetic Circuits", Journal of IEEE Transactions on Computers, 47(9), pp.938~946 (1998)
- H. Wu, "Finite Field Multiplier Using Redundant Representation", Jounral of IEEE Transactions on Computers, 51(11), pp.1306~1316 (2002)
- K. Z. Pekmestzi, "Multiplexer-based Array Multipliers", Journal of IEEE Transactions on Computers, 48(1), pp.15~23 (1999)
- R.J. Baker, "CMOS Circuit, Design, Layout, and Simulation" (1998), Wiley-IEEE Press
- "STMicroelectronics"[URL]