Equally Spaced 기약다항식 기반의 효율적인 이진체 비트-병렬 곱셈기 (Efficient Bit-Parallel Multiplier for Binary Field Defined by Equally-Spaced Irreducible Polynomials)

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 18권 / 2호 / 3 ~ 10페이지
· 저자명 : 이옥석, 장남수, 김창한, 홍석희

초록

유한체 GF(2m)의 원소를 표현하기 위한 기저선택은 곱셈기의 효율성에 영향을 미친다. 이중에서 여분표현을 이용한 곱셈기는 모듈러 감산을 빠르게 구성할 수 있는 특징을 이용하여 시간-공간의 trade-off를 효율적으로 제공한다. 따라서 여분표현을 이용한 기존의 곱셈기는 다른 기저로 표현한 곱셈기보다 시간 복잡도 상의 효율성을 제공하나 공간 복잡도가 많이 늘어나는 단점을 가진다. 본 논문에서는 다항식 지수승 연산이 많이 사용된다는 것을 감안해 Left-to-Right 형태의 지수승 환경에 적합한 시간-공간 복잡도 상의 효율성을 가지는 새로운 비트-병렬 곱셈기를 제안한다. 제안하는 곱셈기는 시간 복잡도 와 (2m - 1)(m + s) 공간 복잡도를 요구하며 ESP(Equally Spaced Polynomial) 기약다항식 기반의 기존 여분표현 곱셈기와 비교해 2(ms + s²) 공간 복잡도는 감소하며, 시간복잡도는 에서 로 감소된다.(:2개의 입력에 1개의 출력인 AND 게이트 시간, :2개의 입력에 1개의 출력인 XOR 게이트 시간이며 :ESP기약 다항식 차수, : ESP기약 다항식의 각항의 차수 간격)

영어초록

The choice of basis for representation of element in GF(2m) affects the efficiency of a multiplier. Among them, a multiplier using redundant representation efficiently supports trade-off between the area complexity and the time complexity since it can quickly carry out modular reduction. So time of a previous multiplier using redundant representation is faster than time of multiplier using others basis. But, the weakness of one has a upper space complexity compared to multiplier using others basis. In this paper, we propose a new efficient multiplier with consideration that polynomial exponentiation operations are frequently used in cryptographic hardwares. The proposed multiplier is suitable for left-to-right exponentiation environment and provides efficiency between time and area complexity. And so, it has both time delay of and area complexity of (2m - 1)(m + s). As a result, the proposed multiplier reduces compared to the previous multiplier using equally-spaced polynomials in area complexity. In addition, it reduces 2(ms + s²) to in the time complexity.(:Time delay of one AND gate, :Time delay of one XOR gate, :Degree of equally spaced irreducible polynomial, :spacing factor)

참고자료

· 없음