Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

High Performance Elliptic Curve Cryptographic Processor for $GF(2^m)$

$GF(2^m)$의 고속 타원곡선 암호 프로세서

  • 김창훈 (대구대학교 정보통신공학과) ;
  • 김태호 (대구대학교 정보통신공학과) ;
  • 홍춘표 (대구대학교 정보통신공학과)
  • Published : 2007.04.15
Download PDF
⟨ Previous Next ⟩

Abstract

This paper presents a high-performance elliptic curve cryptographic processor over $GF(2^m)$. The proposed design adopts Lopez-Dahab Montgomery algorithm for elliptic curve point multiplication and uses Gaussian normal basis for $GF(2^m)$ field arithmetic operations. We select m=163 which is the smallest value among five recommended $GF(2^m)$ field sizes by NIST and it is Gaussian normal basis of type 4. The proposed elliptic curve cryptographic processor consists of host interface, data memory, instruction memory, and control. We implement the proposed design using Xilinx XCV2000E FPGA device. Based on the FPGA implementation results, we can see that our design is 2.6 times faster and requires significantly less hardware resources compared with the previously proposed best hardware implementation.

본 논문에서는 $GF(2^m)$상의 고속 타원곡선 암호 프로세서를 제안한다. 제안한 암호 프로세서는 타원곡선 정수 곱셈을 위해 Lopez-Dahab Montgomery 알고리즘을 채택하고， $GF(2^m)$상의 산술 연산을 위해 가우시안 정규 기저(Gaussian Normal Basis: GNB)를 이용한다. 본 논문에서 구현한 타원곡선 암호 프로세서는 m=163을 선택하였으며 NIST(National Institute of Standard and Technology)에서 권고하는 5개의 $GF(2^m)$ 필드 크기 중에서 가장 작은 값으로 GNB 타입 4가 존재한다. 제안한 타원곡선 암호 프로세서는 Host Interface, Data Memory, Instruction Memory, Control로 구성되어 있으며 Xilinx XCV2000E FPGA칩을 이용하여 구현한다. FPGA 구현결과 제안된 타원곡선 암호 프로세서는 기존의 연구결과에 비해 속도에서 약 2.6배의 성능 향상을 보이며 훨씬 낮은 하드웨어 복잡도를 가진다.

Keywords

References

  1. V.S. Miller, 'Use of Elliptic Curves in Cryptography,' in Advances in Cryptology-Proc. of CRYPTO'85, pp. 417-426, 1986
  2. N. Koblitz, 'Elliptic Curve Cryptosystems,' Mathematics of Computation, vol. 48, pp. 203-209, 1987 https://doi.org/10.2307/2007884
  3. RSA Laboratories, Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1, RFC 3447, 2003
  4. T. ElGamal, 'A Publick Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,' in Advances in Cryptology-Proc. of CRYPTO'84, pp. 10-18, 1985
  5. I.F. Blake, G. Seroussi, and N.P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999
  6. M. Rosing, Implementing Elliptic Curve Cryptography, Manning, 1999
  7. D. Hankerson, A. Menezes, and S. Vanstone, Guide to Eliptic Curve Cryptography, Springer 2004
  8. L. Gao, S. Shrivastava, and G. Sobelman, 'Elliptic Curve Scalar Multiplier Design Using FPGAs,' Proc. Cryptographic Hardware and Embedded Systems (CHES '99), pp. 257-268, Aug. 1999.
  9. G. Orlando and C. Parr, 'A High Performance Reconfigurable Elliptic Curve Processor for GF (2m),' CHES 2000, LNCS 1965, 2000.
  10. G. B. Agnew, R. C. Mullin, and S. A. Vanstone, 'An implementation of elliptic curve cryptosystems over F $_2^{155}$,' IEEE Journal on Selected Areas in Communications, Vol. 11, no. 5, pp. 804-813, June 1993 https://doi.org/10.1109/49.223883
  11. IEEE 1363, Standard Specifications for Publickey Cryptography, 2000
  12. NIST, Recommended elliptic curves for federal government use, May 1999. http://csrc.nist.gov/encryption
  13. J. Lopez and R. Dahab, 'Improved Algorithms for Elliptic Curve Arithmetic in GF(2m),' SAC '98, LNCS Springer Verlag, 1998
  14. N. Gura, S.C. Shantz, H.E. Sumit Gupta, V. Gupta, D. Finchelstein, E. Goupy, and D. Stebila, 'An End-toEnd Systems Approach to Elliptic Curve Cryptography,' CHES '02, LNCS 2523, pp.349-365, 2002
  15. S. Kwon, K. Gaj, C.H. Kim, and C.P. Hong, 'Efficient Linear Array for Multiplication in GF(2m) Using a Normal Basis for Elliptic Curve Cryptography,' CHES 2004, LNCS 3156, pp. 76-91, 2004
  16. J. L. Massey and J.K. Omura, 'Computational method and apparatus for finite field arithmetic,' US Patent No. 4587627, 1986
  17. A. Reyhani-Masoleh and M.A. Hasan, 'Efficient Digit-Serial Normal Basis Multipliers over GF(2m),' ACM Trans. Embedded Computing Systems(TECS), special issue on embedded systems and security, vol. 3, no. 3, pp. 575-592, Aug. 2004 https://doi.org/10.1145/1015047.1015053
  18. T. Itoh and S. Tsuji, 'A fast algorithm for computing multiplicative inverses $GF(2^m)$in using normal bases,' Information and Computing, vol.78, no. 3, pp. 171-177, 1988 https://doi.org/10.1016/0890-5401(88)90024-7
  19. A. Satoh and K. Takano, 'A Scalable Dual-Field Elliptic Curve Cryptographic Processor,' IEEE Trans. on Computers, Vol. 52, No. 4, pp. 449-460, Apr. 2003 https://doi.org/10.1109/TC.2003.1190586
  20. S. Sutikno, A. Surya, and R. Effendi, 'An Implementation of ElGamal Elliptic Curves Cryptosystems,' Proc. 1998 IEEE Asia-Pacific Conf. Circuits and Systems (APCCAS '98), pp. 483-486, Nov. 1998 https://doi.org/10.1109/APCCAS.1998.743829
  21. S. Sutikno, R. Effendi, and A. Surya, 'Design and Implementation of Arithmetic Processor $F_2^{155}$ for Elliptic Curve Cryptosystems,' Proc. 1998 IEEE Asia-Pacific Conf. Circuits and Systems (APCCAS '98), pp. 647-650, Nov. 1998 https://doi.org/10.1109/APCCAS.1998.743903
  22. K.H. Leung, K.W. Ma, W.K. Wong, and P.H.W. Leong, 'FPGA Implementation of a Microcoded Elliptic Curve Cryptographic Processor,' Proc. 2000 IEEE Symp. Field Programmable Custom Computing Machines (FCCM '99), pp. 68-76, Apr. 2000 https://doi.org/10.1109/FPGA.2000.903394
  23. M. Ernst, S. Klupsch, O. Hauck, and S.A. Huss, 'Rapid Prototyping for Hardware Accelerated Elliptic Curve Public-Key Cryptosystems,' Proc. 12th Int''l Workshop Rapid System Prototyping (RSP 2001), pp. 24-29, Jun. 2001 https://doi.org/10.1109/IWRSP.2001.933834
  24. M.C. Rosner, 'Elliptic Curve Cryptosystems on Reconfigurable Hardware,' master's thesis, Worcester Polytechnic Inst., May 1998, http://www.ece.wpi.edu/research/cry-pt/publications/documents/ms_mrosner.pdf
  25. N.P. Smart, 'The Hessian Form of an Elliptic Curve,' Proc. Cryptographic Hardware and Embedded Systems(CHES 2001), pp. 118-125, May 2001
  26. S. Okada, N. Torii, K. Itoh, and M. Takenaka, 'Implementation of Elliptic Curve Cryptographic Coprocessor over $GF(2^m)$ on an FPGA,' Proc. Cryptographic Hardware and Embedded Systems(CHES 2000), pp. 25-40, Aug. 2000
  27. J. Goodman and A. Chandrakasan, 'An Energy Efficient Reconfigurable Public-Key Cryptography Processor Architecture,' Proc. Cryptographic Hardware and Embedded Systems (CHES 2000), pp. 175-190, Aug. 2000