본문 바로가기
KERD
논문KCI 등재

GF(2m)의 정규기저를 이용한 2배속비트직렬 곱셈기 설계

Design of Two-times Faster Bit-Serial MultiplierUsing Normal Basis of GF(2m)

민경일|조용석
한국지식정보기술학회 (Korea Knowledge Information Technology Society)|2017.06|한국지식정보기술학회 논문지 (Journal of Knowledge Information Technology and Systems)|제12권 제3호|pp. 423-429|DOI 10.34163/jkits.2017.12.3.004

1

조회

0

다운로드

0

인용

0

참고문헌

키워드

CryptographyFinite fieldsGalois fieldsNormal BasisBit-serial multipliers
주제분류학제간연구

초록

유한체 연산은 최근 관심이 집중되고 있는 분야로, 신호처리와 오류정정부호, 특히 암호이론 등에서 광범위하게 응용되고 있다. 이와 같은 응용 분야에서는 저복잡도의 유한체 연산기를 설계할 필요가 있다. 유한체 연산의 성능에 큰 영향을 미치는 하나의 중요한 요소는 유한체의 원소를 표현하는 방법인 기저이다. 이 중에서 정규기저를 사용하면, 유한체 의 제곱 연산이 왼쪽으로 한 비트 순회치환만으로 가능하기 때문에 연산기의 하드웨어 구현에 매우 유리하다. 본 논문에서는 정규기저를 이용한 새로운 2배속 비트직렬 곱셈기의 구조를 제안한다. 제안한 곱셈기는 곱셈의 한 원소를 2개의 부분으로 나눈 다음, 각각의 부분을 동시에 비트직렬 곱셈기로 구현한다. 따라서 본 곱셈기는 크기가 인 2진 유한체에서 한 번의 곱셈 연산을 수행하는데 클럭이 소요된다. 그러므로 제안된 곱셈기는 기존의 비트직렬 곱셈기에 비해 2배 빠르며, 비트병렬 곱셈기에 비해서는 더 낮은 복잡도를 가진다. 본 곱셈기는 기존의 곱셈기에 비해서 구조가 매우 규칙적이므로 VLSI 구현에 적합하다. 제안된 곱셈기의 중요한 장점은 회로의 복잡도와 지연시간 사이에 적절한 절충이 가능하다는 것이다. 따라서 본 곱셈기는 값이 크지만 회로의 면적을 고려하여야 하는 자원이 한정된 암호 시스템과 같은 응용에 더 적합하다.

Abstract

Finite field arithmetic has recently gained growing attention due to its wide range of applications in signal processing, error control coding and especially in cryptography. In these applications, there is a need to design low complexity finite field arithmetic units. One important factor that could greatly affect computation performance is the basis in which finite field elements are represented. Among the basis, representation of fields elements using a normal basis is quite attractive for hardware implementation since the squaring operation over can be performed by only one-bit cyclic shift to left. In this paper, we propose a new architecture of two-times faster bit-serial finite field multiplier using a normal basis. In the proposed multiplier, the bits of an operand are grouped into the two parts and each part is implemented simultaneously by bit-serial multiplier. Therefore, the proposed multiplier takesclock cycles, to finish one multiplication operation in a binary field of size m. The proposed architecture is two-times faster than bit-serial architectures but with lower area complexity than bit-parallel ones. It is shown that the new design has higher regular architecture compared to other similar proposals and therefore, well-suited for VLSI implementation. The main advantage of the proposed architecture is that a trade-off between hardware complexity and delay time can be achieved. Therefore, the proposed multipliers are more suitable for resource constrained cryptographic systems where the value of m is large but space is of concern.

참고문헌 (17)

  1. M. Y. Rhee, "Error-correcting coding theory" (1989), Mcgraw-Hill
  2. D. Hankerson, "Guide to elliptic curve cryptography" (2004), Springer-Verlag
  3. R. Lidl, "Introduction to finite fields and their applications" (1994), Cambridge University Press
  4. C. K. Koc, "Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields", IEEE Transactions on Computers, 47(3), pp.353~356 (1998)
  5. A. Reyhani-Masoleh, "A new construction of massey-omura parallel multiplier over GF(2m)", IEEE Transactions on Computers, 51(5), pp.511~520 (2002)
  6. T. Beth, "Algorithm engineering For public key algorithms", IEEE J. Selected Areas in Communications, 7(4), pp.458~466 (1989)
  7. G. B. Agnew, "An implementation for a fast public-key cryptosystem", Journal of Cryptology, 3(2), pp.63~79 (1991)
  8. A. Reyhani-Masoleh, "Efficient Digit-serial Normal Basis Multipliers over Binary Extension Fields", ACM Transactions on Embedded Computing Systems, 3(3), pp.575~592 (2004)
  9. S. Kwon, "Efficient linear array for multiplication in GF(2m) using a normal basis for elliptic curve cryptography", Proceedings of Workshop Cryptographic Hardware and Embedded Systems (CHES), pp.76~91 (2004)
  10. A. H. Namin, "Comb architectures for finite field multiplication in F2m", IEEE Transactions on Computers, 56(7), pp.909~916 (2007)
  11. A. H. Namin, "A word-level finite field multiplier using normal basis", IEEE Transactions on Computers, 60(6), pp.890~895 (2010)
  12. 조용석, "유한체 GF(2m)의 정규기저를 이용한 LSB 우선 워드 레벨 곱셈기", 한국지식정보기술학회 논문지, 9(5), pp.571~578 (2014), 한국지식정보기술학회
  13. S. Lin, "Error control coding: Fundamentals and applications" (2004), Prentice-Hall
  14. E. R. Berlekamp, "Bit-Serial Reed-Solomon encoders", IEEE Transactions on Information Theory, 28(6), pp.869~874 (1982)
  15. J. K. Omura, "Computational method and apparatus for finite field arithmetic", U.S. Patent #4, 587, 627, ~627 (1986)
  16. National institute of standards and technology, "digital signature standard, FIPS Publications 186-2", ~ (2000)
  17. "IEEE Std 1363-2000. IEEE Standard specifications for public-key cryptography", ~ (2000)

관련 논문AI추천

유한체 GF(2^m)의 정규기저를 이용한 새로운 비트직렬/디지트병렬 곱셈기신용달, 조용석한국지식정보기술학회 · 한국지식정보기술학회 논문지2019 · 제14권 제2호유한체 GF(2^m)의 하이브리드 정규기저곱셈기의 효율적인 구현민경일, 조용석한국지식정보기술학회 · 한국지식정보기술학회 논문지2016 · 제11권 제4호유한체 GF(2m)의 정규기저를 이용한 LSB 우선 워드 레벨 곱셈기조용석, 최재연한국지식정보기술학회 · 한국지식정보기술학회 논문지2014 · 제9권 제5호유한체 상에서 고속 연산을 위한 직렬 곱셈기의 병렬화 구조조용석한국정보보호학회 · 정보보호학회논문지2007 · 제17권 제1호유한체 GF(2m)상의 낮은 지연시간의 AB2 곱셈 구조 설계김기원, 김현성, 이원진대한임베디드공학회 · 대한임베디드공학회논문지2012 · 제7권 제2호Massey-Omura 승산기를 위한 최적 정규원소김창규한국정보보호학회 · 정보보호학회논문지2004 · 제14권 제3호

이 간행물의 다른 논문 (8건)

SNS 피로증후군의 선행요인에 관한 연구: 베블런의 유한계급론 관점김경규, 류성열pp. 395-403IoT 시스템의 모바일 센서 디바이스를 위한 에너지 효율적인 그룹 관리 MAC 기법유인태, 이재선, 선경희pp. 405-414BMD의 교차전송을 이용한 지연시간 기반의 탄력적인 하이브리드 멀티캐스트심종채, 남영호, 백현철, 구명모pp. 415-422배경 영상을 이용한 시간 일관적 스케치 렌더링장재건, 김영권, 류승택pp. 431-438트래픽 변이정보와 RST 신호분석을 이용한 스니핑 및 세션하이재킹 대응 모델백현철, 최재영, 김상복, 박재흥pp. 439-446
원문 보기