Journal of IKEEE (전기전자학회논문지)

Institute of Korean Electrical and Electronics Engineers (한국전기전자학회)
권호 표지
DOI QR코드

DOI QR Code

A High Performance Modular Multiplier for ECC

타원곡선 암호를 위한 고성능 모듈러 곱셈기

  • Choe, Jun-Yeong (School of Electronic Engineering, Kumoh National Institute of Technology) ;
  • Shin, Kyung-Wook (School of Electronic Engineering, Kumoh National Institute of Technology)
  • Received : 2020.11.05
  • Accepted : 2020.12.23
  • Published : 2020.12.31
Download PDF
⟨ Previous Next ⟩

Abstract

This paper describes a design of high performance modular multiplier that is essentially used for elliptic curve cryptography. Our modular multiplier supports modular multiplications for five field sizes over GF(p), including 192, 224, 256, 384 and 521 bits as defined in NIST FIPS 186-2, and it calculates modular multiplication in two steps with integer multiplication and reduction. The Karatsuba-Ofman multiplication algorithm was used for fast integer multiplication, and the Lazy reduction algorithm was adopted for reduction operation. In addition, the Nikhilam division algorithm was used for the division operation included in the Lazy reduction. The division operation is performed only once for a given modulo value, and it was designed to skip division operation when continuous modular multiplications with the same modulo value are calculated. It was estimated that our modular multiplier can perform 6.4 million modular multiplications per second when operating at a clock frequency of 32 MHz. It occupied 456,400 gate equivalents (GEs), and the estimated clock frequency was 67 MHz when synthesized with a 180-nm CMOS cell library.

타원곡선 암호에 필수적으로 사용되는 모듈러 곱셈의 고성능 하드웨어 설계에 대해 기술한다. 본 논문의 모듈러 곱셈기는 NIST FIPS 186-2에 정의된 소수체 상의 5가지 체 크기(192, 224, 256, 384, 521 비트)의 모듈러 곱셈을 지원하며, 정수 곱셈과 축약의 두 단계 과정으로 모듈러 곱셈을 연산한다. 고속 정수 곱셈을 위해 카라추바-오프만 곱셈 알고리듬이 사용되었고, 축약 연산을 위해 Lazy 축약 알고리듬이 사용되었다. 또한, Lazy 축약에 포함된 나눗셈 연산을 위해 Nikhilam 나눗셈 알고리듬이 사용되었으며, 나눗셈 연산은 주어진 모듈러 값에 대해 처음 한 번만 연산되고, 모듈로 값이 고정된 상태로 연속적인 모듈러 곱셈이 수행되는 경우에는 나눗셈을 거치지 않도록 하였다. 설계된 모듈러 곱셈기는 32 MHz의 클록 주파수로 동작하는 경우에 초당 640만번의 모듈러 곱셈을 연산할 수 있는 것으로 평가되었으며, 180-nm CMOS 셀 라이브러리로 합성한 결과, 67 MHz의 클록 주파수로 동작이 가능하며, 456,400 등가 게이트로 구현되었다.

Keywords

Acknowledgement

This work was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. 2020R1I1A3A04038083) This research was supported by the KIAT(Korea Institute for Advancement of Technology) grant funded by the Korea Government(MOTIE : Ministry of Trade Industry and Energy). (No. N0001883, HRD Program for Intelligent semiconductor Industry) Authors are thankful to IDEC for supporting EDA software.

References

  1. N. Koblitz, "Elliptic curve cryptosystems," Mathematics of Computation, vol.48, no.177, pp. 203-209, Jan. 1987. https://doi.org/10.1090/S0025-5718-1987-0866109-5
  2. D. Basu Roy and D. Mukhopadhyay, "High-Speed Implementation of ECC Scalar Multiplication in GF(p) for Generic Montgomery Curves," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol.27, no.7, pp.1587-1600, July 2019. DOI: 10.1109/ TVLSI.2019.2905899.
  3. M. R. Hossain and M. S. Hossain, "Efficient FPGA Implementation of Modular Arithmetic for Elliptic Curve Cryptography," 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE), Cox'sBazar, Bangladesh, pp.1-6, 2019. DOI: 10.1109/ECACE.2019.8679419.
  4. P. L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, vol.44, no.170, pp.519-521, May 1985. https://doi.org/10.1090/S0025-5718-1985-0777282-X
  5. A. Karatsuba and Y. Ofman, "Multiplication of many-digital numbers by automatic computers," Proceedings of the USSR Academy of Sciences, vol.145, no.2, pp.293-294, 1962.
  6. J.-C. Bajard, L.-S. Didier and P. Kornerup, "An RNS Montgomery modular multipli-cation algorithm," in IEEE Transactions on Computers, vol.47, no.7, pp.766-776, July 1998. DOI: 10.1109/ 12.709376.
  7. P. Barrett, "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor," In: Odlyzko A.M. (eds) Advances in Cryptology-CRYPTO'86. Lecture Notes in Computer Science, Springer, vol.263, pp.311-323, Aug. 1986. DOI: 10.1007/3-540-47721-7_24
  8. M. M. Islam, M. S. Hossain, M. Shahjalal, M. K. Hasan and Y. M. Jang, "Area-Time Efficient Hardware Implementation of Modular Multiplication for Elliptic Curve Cryptography," IEEE Access, vol.8, pp.73898-73906, 2020. DOI: 10.1109/ACCESS.2020.2988379.
  9. E. Ozturk, "Design and Implementation of a Low-Latency Modular Multiplication Algorithm," IEEE Transactions on Circuits and Systems I: Regular Papers, vol.67, no.6, pp.1902-1911, June 2020. DOI: 10.1109/TCSI.2020.2966755.
  10. S. Li and Z. Gu, "Lazy Reduction and Multi-Precision Division Based on Modular Reductions," 2018 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), Chengdu, 2018, pp.407-410.
  11. National Institute of Standard and Technology (NIST), Digital Signature Standard (DSS), NIST Std. FIPS PUB 186-2, 2000.
  12. X. Feng and S. Li, "A high performance fpga implementation of 256-bit elliptic curve cryptography processor over GF(p)," IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences, vol. E98.A, no.3, pp.863-869, 2015.
  13. J. S. S. B. K. T. Maharaja, Vedic Mathematics, MotilalBanarsidass, New Delhi, India, 1994.
  14. K. Javeed, X. Wang and M. Scott, "Serial and parallel interleaved modular multipliers on FPGA paltform," 2015 25th International Conference on Field Programmable Logic and Applications (FPL), pp.1-4, Sept 2015.
  15. R. Liu and S. Li, "A design and implementation of Montgomery modular multiplier," IEEE International Symposium on Circuits and Systems (ISCAS), pp.1-4, May 2019.