GF(2^m)상의 효율적인 세미-시스톨릭 몽고메리 곱셈기
Efficient Semi-systolic Montgomery multiplier over GF(2^m)
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
유한체 산술 연산은 현대 암호학(cryptography)과 오류 정정 부호(error correction codes) 등 다양한 응용에서 중요한 역할을 한다. 본 논문에서는 유한체상에서 몽고메리 곱셈 알고리즘을 사용한효율적인 유한체 곱셈 알고리즘을 제안한다. 기존의 곱셈기들에서는 AND와 XOR 게이트를 사용하여 구현되었는데, 시간 및 공간 복잡도를 줄이기 위해서 NAND와 NOR 게이트를 사용하는 알고리즘을 제안하였다. 게다가 제안한 알고리즘을 기초로 적은 공간과 낮은 지연시간을 갖는 효율적인 세미-시스톨릭(semi-systolic) 유한체 곱셈기를 제안한다. 제안한 곱셈기는 기존의 곱셈기에 비해 낮은 공간-시간 복잡도(area-time complexity)를 가진다. 기존의 구조들과 비교하면, 제안한 유한체 곱셈기는 공간-시간 복잡도면에서 Chiou 등, Huang 등 및 Kim-Jeon의 곱셈기에 비해 약 71%, 66%, 33%가 감소되었다. 따라서 제안한 곱셈기는 VLSI 구현에 적합하며, 다양한 응용의 기본 구성 요소로 쉽게 적용될 수 있다.
Abstract
Finite field arithmetic operations play an important role in a variety of applications, including modern cryptography and error correction codes. In this paper, we propose an efficient multiplication algorithm over finite fields using the Montgomery multiplication algorithm. Existing multipliers can be implemented using AND and XOR gates, but in order to reduce time and space complexity, we propose an algorithm using NAND and NOR gates. Also, based on the proposed algorithm, an efficient semi-systolic finite field multiplier with low space and low latency is proposed. The proposed multiplier has a lower area-time complexity than the existing multipliers. Compared to existing structures, the proposed multiplier over finite fields reduces space-time complexity by about 71%, 66%, and 33% compared to the multipliers of Chiou et al., Huang et al., and Kim-Jeon. As a result, our multiplier is proper for VLSI and can be successfully implemented as an essential module for various applications.
참고문헌 (16)
- R.E. Blahut, "Theory and Practice of Error Control Codes" (1983), Addison-Wesley
- R. Lidl, "Introduction to Finite Fields and Their Applications" (1994), Cambridge University Press
- A. J. Menezes, "Handbook of Applied Cryptography" (1996), CRC Press
- B. Schneier, "Applied Cryptography second edition" (1996), John Wiley & Sons Inc
- Chin-Liang Wang, "Systolic array implementation of multipliers for finite fields GF(2", sup m, IEEE Transactions on Circuits and Systems, pp.1991, 38(7)[DOI]
- S.K. Jain, "Efficient semisystolic architectures for finite-field arithmetic", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 6(1), pp.101~113 (1998), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
- 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), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Chiou-Yng Lee, "Concurrent Error Detection in a Polynomial Basis Multiplier over GF(2m)", Journal of Electronic Testing, 22(2), pp.143~150 (2006), Springer Science and Business Media LLC[DOI]
- W.-T. Huang, "Concurrent error detection and correction in a polynomial basis multiplier over GF(2m)", IET Information Security, 4(3), pp.111~124 (2010), Institution of Engineering and Technology (IET)[DOI]
- Kee-Won Kim, "Polynomial Basis Multiplier Using Cellular Systolic Architecture", IETE Journal of Research, 60(2), pp.194~199 (2014), Informa UK Limited[DOI]
- 김기원, "유한체상의 효율적인 세미-시스톨릭 AB2 곱셈기", 한국컴퓨터정보학회논문지, 25(1), pp.37~43 (2020), 한국컴퓨터정보학회[DOI]
- 김기원, "유한체상의 여분기저를 사용한 효율적인 멀티플렉서 기반 AB2 곱셈기", 한국컴퓨터정보학회논문지, 25(1), pp.13~19 (2020), 한국컴퓨터정보학회[DOI]
- 김기원, "유한체상의 곱셈과 제곱을 위한 적은 면적의 비트-병렬 시스톨릭 어레이", 한국컴퓨터정보학회논문지, 25(2), pp.41~48 (2020), 한국컴퓨터정보학회[DOI]
- Peter L. Montgomery, "Modular multiplication without trial division", Mathematics of Computation, 44(170), pp.519~521 (1985), American Mathematical Society (AMS)[DOI]
- Cetin K. Koc, "Montgomery multiplication in GF(2k)", Designs, Codes and Cryptography, 14(1), pp.57~69 (1998), Springer Science and Business Media LLC[DOI]
- "65 nm STMicroelectronics CMOS Technology, Standard Cell Library for 65 Nanometer CMOS065LP VLSI Digital Design Platform"[URL]