유한체 GF(2^m)의 정규기저를 이용한 새로운 비트직렬/디지트병렬 곱셈기 (A New Bit-Serial/Digit-Parallel Multiplier in GF(2^m) UsingNormal Basis)

서지정보

· 발행기관 : 한국지식정보기술학회
· 수록지 정보 : 한국지식정보기술학회 논문지 / 14권 / 2호 / 203 ~ 210페이지
· 저자명 : 조용석, 신용달

초록

유한체 GF(2^m) 상의 연산은 공개키 암호시스템과 오류정정부호 등에서 널리 사용되고 있다. 유한체 GF(2^m) 상의 연산중에서 지수승과 나눗셈과 같은 더 복잡한 연산은 곱셈의 반복으로 수행될 수 있기 때문에, 유한체 상의 곱셈의 효율적인 구현은 매우 중요한 사항이다. 유한체 상의 곱셈의 효율성은 유한체의 원소를 표현하는 기저의 선택에 좌우된다. 유한체 곱셈기를 구현하는데 널리 사용되는 기저로는 다항식기저, 정규기저, 쌍대기저 등이 있다. 정규기저를 이용한 유한체 곱셈기의 하드웨어 구현은, 제곱 연산이 한 비트 순회치환만으로 가능하여, 비용이 들지 않기 때문에 매우 유리하다. 본 논문에서는 GF(2^m)의 정규기저를 이용하여 새로운 비트직렬/디지트병렬 곱셈기를 설계한다. 이러한 정규기저의 특성을 이용하는 것이 제안된 곱셈기의 주요 아이디어이다. 제안된 곱셈기는 곱셈의 한 원소를 비트씩 묶은 다음, 각각의 부분을 동시에 비트직렬 곱셈기로 구현한다. 그러므로 제안된 곱셈기는 GF(2^m)에서 클럭만에 곱셈의 결과를 출력한다. 여기에서 값은 회로 면적과 속도 사이를 절충하여 설계자가 응용에 따라 선택할 수 있다. 제안된 곱셈기는 비트직렬 곱셈기보다는 고속으로 동작하며, 비트병렬 곱셈기보다는 더 낮은 복잡도를 갖는다. 또한 제안된 곱셈기는 기존의 곱셈기에 비해서 회로의 구조가 매우 규칙적이어서 VLSI 구현에 적합하며, 유한체 상의 지수승과 나눗셈과 같은 복잡한 연산을 위한 기본 요소로 쉽게 사용할 수 있다.

영어초록

The Arithmetic operations over GF(2^m) have been extensively used in public-key cryptography schemes and error correcting codes. Among the arithmetic operations over GF(2^m), the efficient implementation of field multiplication is of upmost importance, as field operations of greater complexity (e.g., exponentiation and division) can be performed by the consecutive use of field multiplication. Choosing the basis by which field elements are represented plays an important role in the efficient implementation of finite field multiplications. There are three popular and applicable basis, namely, polynomial basis (PB), normal basis (NB), and dual basis. Hardware implementations of finite field multiplier using normal basis are advantageous due to the fact that the squaring operation can be performed by only one-bit cyclic shift at almost no cost. In this paper, a new bit-serial/digit-parallel multiplier using normal basis of GF(2^m) is presented. The main idea of the proposed multiplier is to use this feature of normal basis. In the proposed multiplier, the bits of an operand are grouped into several digits with bits and each digit is implemented simultaneously by bit-serial multiplier. Therefore, the proposed multiplier takes clock cycles, , to finish one multiplication operation in GF(2^m). The value of can be selected by designer to set the trade off between area and speed according to the application. The proposed multiplier has lower area complexity than bit-parallel multiplier and is faster than bit-serial ones. In addition, the proposed multiplier has higher regular architecture compared to other similar proposals and therefore, well-suited for VLSI implementation and can be easily applied as a basic component for computing complex operations over finite field, such as exponentiation and division operation.

참고자료

· 없음