GF(2m) 상에서 새로운 디지트 시리얼 AB2 시스톨릭 어레이 설계 및 분석
Design and Analysis of a Digit-Serial AB2 Systolic Arrays in GF(2m)
김남연(경북대학교); 유기영(경북대학교)
32권 4호, 160~167쪽
초록
상의 공개키 암호 시스템에서 나눗셈/역원은 기본이 되는 연산으로 내부적으로 AB2 연산을 반복적으로 수행함으로써 계산이 된다. 본 논문에서는 유한 필드 GF(2m) 상에서 AB2 연산을 수행하는 디지트 시리얼(digit-serial) 시스톨릭 구조를 제안하였다. L(디지트 크기)×L 크기의 디지트 시리얼 구조로 유도하기 위하여 새로운 AB2 알고리즘을 제안하고, 그 알고리즘에서 유도된 구조의 각 셀을 분리, 인덱스 변환 시킨 후 병합하는 방법을 사용하였다. 제안된 구조는 공간-시간 복잡도를 비교할 때, 디지트 크기가 m보다 적을 때 비트 패러럴 구조에 비해 효율적이고, (1/5)log2(m+1) 보다 적을 때 비트 시리얼(bit-serial) 구조에 비해 효율적이다. 또한, 제안된 디지트 시리얼 구조에 파이프라인 기법을 적용하면 그렇지 않은 구조에 비해 m=160, L=8 일 때 공간-시간 복잡도가 10.9% 적다. 제안된 구조는 암호 프로세서 칩 디자인의 기본 구조로 이용될 수 있고, 또한 단순성, 규칙성과 병렬성으로 인해 VLSI 구현에 적합하다.
Abstract
finite filed arithmetic operations, division/inverse is known as a basic operation for public-key cryptosystems over GF(2m) and it is computed by performing the repetitive AB2 multiplication. This paper presents a digit-serial-in-serial-out systolic architecture for performing the AB2 operation in GF(2m). To obtain L×L digit-serial-in-serial-out architecture, new AB2 algorithm is proposed and partitioning, index transformation and merging the cell of the architecture, which is derived from the algorithm, are proposed. Based on the area-time product, when the digit-size of digit-serial architecture, L, is selected to be less than about m, the proposed digit-serial architecture is efficient than bit-parallel architecture, and L is selected to be less than about (1/5)log2(m+1), the proposed is efficient than bit-serial. In addition, the area-time product complexity of pipelined digit-serial AB2 systolic architecture is approximately 10.9% lower than that of nonpipelined one, when it is assumed that m = 160 and L = 8. Additionally, since the proposed architecture can be utilized for the basic architecture of crypto-processor and it is well suited to VLSI implementation because of its simplicity, regularity and pipelinability.
- 발행기관:
- 한국정보과학회
- 분류:
- 컴퓨터학