본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

타원곡선 암호프로세서의 재구성형 하드웨어 구현을 위한 GF(2$^{m}$)상의 새로운 연산기
A Novel Arithmetic Unit Over GF(2$^{m}$) for Reconfigurable Hardware Implementation of the Elliptic Curve Cryptographic Processor

김창훈   (대구대학교 컴퓨터정보공학과UU0000355  ); 권순학   (성균관대학교 수학UU0000759  ); 홍춘표   (대구대학교 정보통신공학UU0000355  ); 유기영   (경북대학교 컴퓨터공학과UU0000096  );
  • 초록

    In order to solve the well-known drawback of reduced flexibility that is associate with ASIC implementations, this paper proposes a novel arithmetic unit over GF(2 $^{m}$ ) for field programmable gate arrays (FPGAs) implementations of elliptic curve cryptographic processor. The proposed arithmetic unit is based on the binary extended GCD algorithm and the MSB-first multiplication scheme, and designed as systolic architecture to remove global signals broadcasting. The proposed architecture can perform both division and multiplication in GF(2 $^{m}$ ). In other word, when input data come in continuously, it produces division results at a rate of one per m clock cycles after an initial delay of 5m-2 in division mode and multiplication results at a rate of one per m clock cycles after an initial delay of 3m in multiplication mode respectively. Analysis shows that while previously proposed dividers have area complexity of Ο(m $^2$ ) or Ο(mㆍ(log $_2$ $^{m}$ )), the Proposed architecture has area complexity of Ο(m), In addition, the proposed architecture has significantly less computational delay time compared with the divider which has area complexity of Ο(mㆍ(log $_2$ $^{m}$ )). FPGA implementation results of the proposed arithmetic unit, in which Altera's EP2A70F1508C-7 was used as the target device, show that it ran at maximum 121MHz and utilized 52% of the chip area in GF(2 $^{571}$ ). Therefore, when elliptic curve cryptographic processor is implemented on FPGAs, the proposed arithmetic unit is well suited for both division and multiplication circuit.


  • 주제어

    $GF(2^{m})$ 나눗셈 .   $GF(2^{m})$ 곱셈 .   타원곡선 암호시스템 .   시스톨릭 어레이 .   회로설계.  

  • 참고문헌 (26)

    1. S.K. Jain, L. Song, and K.K. Parhi, 'Efficient Semi-Systolic Architectures for Finite Field Arithmetic,' IEEE Trans. VLSI Syst., vol. 6, no. 1, pp. 101-113, Mar. 1998 
    2. C. L. Wang and J. L. Lin, 'Systolic Array Implementation of Multipliers for Finite Field GF($2^m$),' IEEE Trans. Circuits and Syst., vol. 38, no. 7, pp. 796-800, July 1991 
    3. S. Y. Kung, VLSI Array Processors, Englewood Cliffs, NJ: Prentice Hall, 1988 
    4. C.H. Kim and C.P. Hong, 'High-speed division architecture for GF($2^m$),' Electronics Letters, vol. 38, no. 15, pp. 835-836, July 2002 
    5. NIST, Recommended elliptic curves for federal government use, May 1999. http://csrc.nist.gov/encryption 
    6. Altera, APEXTMII Programable Logic Device Family Data Sheet, Aug. http://www.altera.com/literature/lit-ap2.html 
    7. S.D. Han, C.H. Kim, and C. P. Hong, 'Characteristic Analysis of Modular Multiplier for GF($2^m$),' Proc. of IEEK Summer Conference 2002, vol. 25, no. 1, pp. 277-280, 2002 
    8. C.-L. Wang and J.-L. Lin, 'A Systolic Architecture for Computing Inverses and Divisions in Finite Fields GF($2^m$),' IEEE Trans. Computers., vol. 42, no. 9, pp. 1141-1146, sep. 1993 
    9. M.A. Hasan and V.K. Bhargava, 'Bit-Level Systolic Divider and Multiplier for Finite Fields GF($2^m$),' IEEE Trans. Computers, vol. 41, no. 8, pp. 972-980, 1992 
    10. S.-W. Wei, 'VLSI Architectures for Computing exponentiations, Multiplicative Inverses, and Divisions in GF($2^m$),' IEEE Trans. Circuits Syst. II, vol. 44, no. 10, pp. 847-855, Oct. 1997 
    11. A.V. Dinh, R.J. Bolton, R. Mason, 'A Low Latency Architecture for Computing Multiplicative Inverses and Divisions in GF($2^m$),' IEEE Trans. Circuits Syst. II, vol. 48, no. 8, pp. 789-793, Aug. 2001 
    12. H. Brunner, A. Curiger and M. Hofstetter, 'On Computing Multiplicative Inverses in GF($2^m$),' IEEE Trans. Computers., vol. 42, no. 8, pp. 1010-1015, Aug. 1993 
    13. J.-H. Guo and C.-L. Wang, 'Systolic Array Implementation of Euclid's Algorithm for Inversion and Division in GF($2^m$),' IEEE Trans. Computers., vol. 47, no. 10, pp. 1161-1167, Oct. 1998 
    14. T. Blum and C. Paar, 'High Radix Montgomery Modular Exponentiation on Reconfigurable Hardware,' IEEE Trans. Computers., vol. 50, no. 7, pp.759-764, July 2001 
    15. K. Compton and S. Hauck, 'Reconfigurable Computing: A Survey of Systems and Software,' ACM Computing Surveys, vol. 34, no. 2, pp. 171-210, June 2002 
    16. R. Tessier amd W. Burleson, 'Reconfigurable Computing for Digital Signal Processing: A Survey,' J. VLSI Signal Processing, vol. 28, no. 1, pp. 7-27, May 1998 
    17. G. B. Agnew, R. C. Mullin, and S. A. Vanstone, 'An Implementation for Elliptic Curve Cryptosystems Over $F_{2^{155}}$,' IEEE J. Selected Areas in Comm., vol.11, no. 5, pp. 804-813, June 1993 
    18. J.R. Goodman, Energy Scalable Reconfigurable Cryptographic Hardware for Portable Applications,' PhD thesis, MIT, 2000 
    19. M. Bednara, M. Daldrup, J. von zur Gathen, J. Shokrollahi, and J. Teich, 'Reconfigurable Implementation of Elliptic Curve Crypto Algorithms,' Proc. of the International Parallel and Distributed Processing Symposium (IPDPS02), pp. 157-164, 2002 
    20. G. Orlando and C. Parr, 'A High Performance Reconfigurable Elliptic Curve Processor for GF($2^m$),' CHES 2000, LNCS 1965, Springer-Verlag, 2000 
    21. L. Gao, S. Shrivastava and G. E. Solbelman, 'Elliptic Curve Scalar Multiplier Design Using FPGAs,' CHES 2000, LNCS 1717, Springer-Verlag, 1999 
    22. D. Bailey and C. Paar, 'Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography, vol. 14, no.3, pp. 153-176, 2001 
    23. D. Hankerson, J. L. Hernandez, and A. Menezes, 'Implementation of Elliptic Curve Cryptography Over Binary Fields,' CHES 2000, LNCS 1965, Springer-Verlag, 2000 
    24. IEEE P1363, Standard Specifications for Publickey Cryptography, 2000 
    25. I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999 
    26. M. Rosing, Implementing Elliptic Curve Cryptography, Manning, 1999 

 저자의 다른 논문

  • 김창훈 (19)

    1. 2002 "유한 필드 $GF(2^m)$상에서의 MSB 우선 디지트 시리얼 곱셈기 설계" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 통신이론 및 시스템 27 (c6): 625~631    
    2. 2002 "유한 필드 GF(2m)상에서의 LSB 우선 디지트 시리얼 곱셈기 구현" 정보처리학회논문지. The KIPS transactions. Part A. Part A a9 (3): 281~286    
    3. 2002 "유한 필드 GF($2^m$)상의 모듈러 곱셈기 및 제곱기 특성 분석" 한국산업정보학회논문지 = Journal of the Korea Industrial Information Systems Research 7 (5): 167~174    
    4. 2002 "타원곡선 암호시스템을 위한 GF(2$^{m}$ )상의 비트-시리얼 나눗셈기 설계" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 통신이론 및 시스템 27 (c12): 1288~1298    
    5. 2003 "저 면적 타원곡선 암호프로세서를 위한 GF(2$^{m}$ )상의 새로운 산술 연산기" 한국통신학회논문지. The journal of Korea Information and Communications Society. 무선통신 28 (a7): 547~556    
    6. 2004 "유한 필드 GF(2m)상의 비트-패러럴 시스톨릭 나눗셈기" 정보처리학회논문지. The KIPS transactions. Part A. Part A a11 (2): 109~114    
    7. 2004 "기약 All One Polynomial을 이용한 유한체 GF(2$^{m}$ )상의 시스톨릭 곱셈기 설계" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 통신이론 및 시스템 29 (c8): 1047~1054    
    8. 2005 "유한체 GF(2m)의 응용을 위한 새로운 나눗셈 회로" 정보처리학회논문지. The KIPS transactions. Part A. Part A a12 (3): 235~242    
    9. 2008 "타원곡선 암호 시스템의 고속 구현을 위한 VLSI 구조" 정보처리학회논문지. The KIPS transactions. Part C Part C c15 (2): 133~140    
    10. 2008 "무선 센서 네트워크상의 소프트웨어 업데이트를 위한 고속 코드 전파 프로토콜" 한국산업정보학회논문지 = Journal of the Korea Industrial Information Systems Research 13 (5): 168~177    
  • 권순학 (7)

  • 홍춘표 (12)

  • 유기영 (52)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기