Ⅰ. 서론

에러교정 코드(error-correcting codes)(1), 디지털 신호 처리(由gital signal processing)t2] 및 암호학(cryptography)"F의 응용에서 갈로아필 드(Galois field, GF)t6'71 연산은 아주 중요하다. 이러한 유한체중에서 특별한 관심을 가지는 유한체 는 GF(2")이다. 유한체 GF(2”)은 2"개의 원소를 가지고 각각의 원소들은 0과 1의 비트-스트링으로 이루어진다. 본 논문에서 다루고 있는 유한체 GF(2m) 은 0과 1로 이루어진 속성 때문에 컴퓨터 구조를 구현하기 위한 계산에 적당하다.

1984년에 Yeh⑼는 일반적인 GF(Z")상에서 AB+C 의 연산을 수행하는 병렬 시 스톨릭(systolic) 어레이 구조를 구현하였다. 표준기 저 상에서 세미시스톨릭(semi-systolic) 에레이 구조가 논문〔10〕에 제시되었고 논문〔11〕에서는 정규 기저 상에서 곱셈과 곱셈역원을 계산하기 위한 구조를 제안하였다. 논문〔12〕 에서는 + c를 계산하기 위한 시스톨릭 구조가 제안되었다. 그리고 그 후에도 많은 비트 단위의 병렬 세미시스톨릭 곱셈기들이 제안 되었으나 시스템의 복잡도 때문에 이러한 곱셈기들은 암호화 시스템의 구성에 효과적이지 못했다. 이러한 시스템의 복잡도를 줄이기 위해서 Itoh와 Tsujif")가 GF]/1)상에서 m차의 기약 다항식 AOP(A11 One Polynomial)에 기초한 곱셈기와 m차의 기약 다항식 ESP(equally spaced polynomial)에 기초한 곱셈기를 설계하였다. 이렇게 설계된 두 개의 곱셈기는 효율적인 시스템 복잡도를 가졌다. 이후에 Hasan's은 처리기로서 AOP에 기초한 병렬 곱셈기를 제안하고, 이를 이용하여 ESP에 기초한 병렬 곱셈기로 발전시켰다. 최근에 는 GF(Z")상에서 타원 곡선(elliptic curve) 기반의 공개키 암호화시스템들이 많이 제시되고있다. 연구에서 효율적인 구조들이 제안되었지만 시간과 공간 복잡도면에서 보다 효율적인 구조 설계에 관한 연구가 필요하다.

본 논문에서는 GF(2")상에서 기약 다항식 AOP의 속성에 기반하여 房를 계산하는 MSB우선 알고리즘을 제시하고, 두 가지 병렬 세미시스톨릭 어레이 구조를 제안한다. 2-입력 AND와 XOR게이트의 딜레이 (delay)를 Dand2와 Dxor2라 할 때, 제안된 병렬 세미시스톨릭 어레이 구조(PSM)의 전체 지연시 간은 m+1 이고, 각 셀당 DaND2 + DxOR2의 임계경로를 갖는다. 그리고 전체 게이트 수는 각각 (m+l)2개 의 AND 게이트와 XOR게이트를 갖는다. 재구성된 변형 병렬 세미시스톨릭 어레이 구조(MPSM)의 전체 지연시간은 m+1 이다. 즉, PSM구조와 지연시간은 같지만 MPSM구조는 각 셀당 Dxor2의 보다 효율적인 임계경로를 갖는다. 본 논문에서 제안된 두 구조는 기존에 제안된 구조보다 구조가 더 간단하고 효율적인 시스템 복잡도를 가지므로 두 구조를 기반으로 보다 효율적이고 안전한 암호화 시스템을 구현할 수 있다.

본 논문은 2장에서 AOP에 기반한 MSB 우선 알고리즘을 제시한다. 3장에서는 2장에서 제안한 알고리즘에 기초한 두 가지 곱셈기를 제시하고, 4장에서 기존의 구조와 본 논문에서 제안한 구조를 비교 및 분석을 한다. 그리고 마지막으로 5장에서 결론을 맺는다.

Ⅱ. AOP에 기반한 제안된 MSB우선 알고리즘

유한체 GF(2)의 유한 확대체를 GF(2")이라 하 자.먼저 유한 확대체 gf^™)상의 원소는 표준, 정규, 이원기저의 세 가지 기저에 의해 표현된다. 첫 번째, 표준기저{laaB-dT}에서 유한체 GF(2m) 상의 임의의 원소4를 나타내면 A=am-idrrl+am-2d7r2 H--Faia+ao로 나타낼 수 있다. 두 번째, 정규 기저 0扌, .../"}에서 GF(2")상의 임의의 원소 厶를 나타내면 A= am-ifl2, jr2 + am-2o2nT4H 卜印决 + <如로 나타낼 수 있다. 마지막으로 이원기저에서 임의의 원소A는 A= am-\um-\+am-2Um-<2. +■■- +ais+oouo로 나타난다. 단, 각각의 a((=0, l, ---, m-l) 는 유한체 GF(2)상의 원소이다. 본 논문에서는 기저의 변환이 필요 없는 표준기저에 초점을 맞추었다.

요약에서 언급한 유한체상에서 Diffie-Hellman 키 교환 방식, 디지털 서명 알고리즘과 ElGamal 암호화 방식과 같이 잘 알려진 알고리즘을 응용한 타원곡선 (elliptic curve) 기반의 공개키암호화 시스템(cryptosystem)의 구현에 있어서 GF(p)나 GF(2m) 상에서 효율적인 지수 연산이 필요하다. 이러한 지수연산을 효율적으로 계산하는 알고리즘을 Knuth가 논문 ⑻에서 제시하였다. 제시한 알고리 즘은 LSBdeast significant bit)와 MSB(most significant bit) 우선 방식이 있다. 제시한 알고리즘은 다음과 같다.

C와 M을 GF(2")의 원소라 하자. 그러면 지수 연산은 다음과 같이 표현될 수 있다.

#(1)

여기서, 지수E를 처리하는 방법에 따라서 알고리즘은 크게 두 가지로 나눌 수 있다. 지수의 LSB와 MSB부터 시작해서 각각 M을 계산할 수 있다. 먼저, 지수의 LSB부터 시작해서 財를 계산하면 다음과 같다.

#(2)

다음으로, 지수의 MSB부터 시작해서 財를 계산하면 다음과 같다.

#(3)

이들 연산을 위해서 Knuth가 이진 방식(Binary Method)을 제안했다.⑻ 식(3)에 기초한 MSB우 선 지수 연산 알고리즘은 다음과 같다.

[알고리즘 1] Knuth®의 MSB 우선 지수 알고리즘

입력 : & E. Rx)

출력 : C=AE mod f(x)

단계1 : if(e，"-i= = l) C=A else C=a°

단계 2 : for i=m~2 to 0

단계3 : if(e；= = 1) C=AC^ mod /(x) else C=cP(^ mod f(x)

MSB 우선 알고리즘의 단계3에서 C=ACS mod f(x) 연산이 필요하다. 즉, 효율적인 AC₂ mod fix) 연산을 통하여 효율적인 지수 연산을 수행할 수 있다. 본 논문에서는 MSB 우선 지수 연산 알고리즘을 위한 기본구조로서 AB2 연산을 위한 새로운 알고리즘과 두 가지 세미시스톨릭 구조를 제안한다.

다항식 /(X)의 근을 a라 하자. GF(2m) 상에서 f(X)를 /(X)=£必 + ■■- +flX■顷)라 할 때, 만약 无=13=0, 1, 이면이 f(x)를 m차의 AOP(A1I One Polynomial)이라고 한다. 다항식 AOP에서 m+1 이 소수이고 2가 모듈라 m+1 에 대해 원시근이 되면 기약다항식이 된다. 그리고 위의 AOP f(x)의 근a에 의해 생성된 집합 (l.a.a2 ...., 成气은 유한체 GF(2") 의 표준기저가 되고 유한체 GF(2") 상의 원소4는 표준기저에서 A +am-2(T2 + .. . + aia+ao로 표현된다.

기약다 항식 AOP의 속성을 모듈라(modular)로 사용하기 위해서 기저의 확장이 필요하다. 표준기저에서 확장된 기저를 明이라 하면, 확장된 기저상에서 유한체 GF(2")상의 원소 厶는 A=Amdn+Am-'[dn ---卜/ha+4o(&i= 0, Ai =ai, 로 표현되고 확장된 기저상의 원소가 된다. 그러므로 GF(2C상의 원소4는 두 가지 다른 표현을 가진다. 여기서, F{x)=xn+xnA + -+x+\ 를 m차의 기약 AOP라하고 a를 F(x) 의 근이라 하자. 즉, F(a)=om+a"rl + ... + a+l = 0이다. 그리고 F(a)=0을(菸=<質' + ”・ + 6!+1로 나타낼 수 있고 양변에 a를 곱하고 정리하면 다음 방정식을 만족한다.

#(4)

이제 AOP의 속성이 적용된 尸=/讦1 + 1를 모듈라로 사용해서 GF©"1)의 확대체상에서의 원소 A 와 度의 곱즉, AB2 mod F연산을 수행한다. 이렇게 곱셈한 연산의 결과 역시 확대체상의 원소가 된다. 곱셈 4B2 mod P 연산의 결과를 R=rmam+rm-iaml + …+ ria+ro라 할 때, 기약다항식 AOP의 성질을 이용해서 본 논문에서 제안한 mod P를 계산하는 식은 다음과 같다.

#(5)

위의 방정식(5)에서 AB2 mod P 연산은 크게 두 부분으로 나뉘어진다. 하나는 곱셈연산을 위한 부분이고 다른 하나는 모듈라 감소 연산을 위한 부분이다. 전자는 정수연산에서의 곱셈 연산과 같고, 후자는 2-비트 순환 시프트(2-bit circular shift) 에 의해서 수행될 수 있다. 이두 연산을 한 후에 결과값 R을 쉽게 얻을 수 있다. 방정식(5)로부터, AOP의 속성에 기반하여 AB1 mod P 연산을 더 효율적으로 계산하는 MSB 우선 알고리즘을 다음과 같이 제안한다.

[알고리즘2] AOP에 기반한 제안된 MSB 우선 곱셈 알고리즘

입력 : A=(am,am^,---,ai,ao),

B=(bm.bm-i；*bi,ba)

출력 : H=AB2 mod P

초기값 : 7?m+i = (0,rm-i, ••■,n,ro) = (0,0, -.0,0)

단계1 : for i=m to 0

단계2 : for j=m to 0

단계 3 : rj=r(j-2)+ajb,

단계 3에서 <X>는 X mod m+1을 의미한다. 알고 리즘2는 A와 3를 입력으로 하여 4夢의 결과인 r 을 출력한다. 이 알고리즘의 주된 처리는 단계3에서 이루어진다. 단계3은 크게 계수의 곱셈 연산과 모듈라 감소 연산의 두 가지 연산으로 나뉘어진다. 먼저, 계수의 곱은 t功, 연산에 의해서 수행된다. 모듈라 감소 연산은 己를 왼쪽으로 2비트 순환 시프트시킴으 로 해서 수행할 수 있다. 이러한 특성은 기약다항식으로서 AOP의 특성을 이용하였기 때문에 가능하다. 그러나 일반적인 기약 다 항식을 사용한 모듈라 감소 연산에 있어서는 이전 곱셈의 임시 결과 값의 최상위 두비트에 의해서 모듈라 감소 연산의 필요성이 결정되고, 본 논문에서 제안한 알고리즘보다 상당히 큰 복잡도를 갖는 연산이 필요하게 된다. 즉, 단계 3에서의 己=九-2>을 수행함으로써 모듈라 감소 연산이 수행된다. 단계2의 루프 내의 연산은 병렬로 수행된다.

다음 장에서는 병렬 입출력 형태의 AB2 mod P 연산을 위한 병렬 세미시스톨릭 어레이 구조와 변형된 병렬 세미시스톨릭 어레이 구조를 알고리즘2에 기초하여 제시한다.

Ⅲ. 제안된 곱셈기 구조

본장에서는 두 가지 병렬 세미시스톨릭 어레이 구조를 제안한다. 먼저 알고리즘2에 기초한 병렬 세미시스톨릭 어레이 구조(PSM)를 구현한다. 그리고 PSM구조에서 중간 결과 값의 누적 연산을 한 단계 늦춤으로 해서 임계경로 면에서 보다 효율적인 구조 즉, 변형된 세미시스톨릭 어레이 구조(MPSM)를 새롭게 구현한다.

3.1 병렬 세미시스톨릭 어레이 구조PSM)

유한체 GF(24) 상에서의 원소A, B 및 建은 확장된 기저상에서 각각

#

로 표현된다. 戸 = 扌 + 1라하면, 유한 체GF(24)상의 원소 4와 B2의 확장된 기저상에서의 곱, AB2 mod 戸연산은 알고리즘2에 의해 다음과 같이 계산된다.

#(6)

각각의 중간 결과 값 계수T'는 다음과 같이 계산 된다.

#(7)

위의식 (7)에서 R는 각각의 중간 계산 결과 값 이다. 방정식(6)에 의해서, 〔그림 1〕은 유한체 GF(24) 상의 병렬 세미시스톨릭 어레이 구조(PSM)를 보여준다. PSM은 (m+l)2의 기본셀을 갖는다.〔그림 1〕 의 연산은 알고리즘2를 기반으로 한다.

(그림 1) GF04)상에서 PSM을 위한 병렬 세미시스톨릭 어레이 곱셈기

PSM구조는 为값과 6, (0</, jMm)값이 동시에 입력되는 병렬 구조이다. %값들은 같은 열(column)에 있는 인접 셀에 전송되지만 &값들은 한 번에 같은 행 (row)에 있는 모든 셀에 브로드캐스트(broadcasting) 되는 세미시스톨릭 어레이 속성을 갖는다.”4)다시 말해서 (m+1)비트의 데이터%가 최상위 열에서 입력되고, 셀의 연산 후에 다음 열에 전송된다.즉, 각각의 인접한 열들의 셀에 전송된다. 그러나 각열에 있는 初들은 같은 행에서 브로드캐스트 된다. PSM 에서 각 셀들은 알고리즘2의 단계3에 해당하는 연산을 수행한다. 단계 3의 r; =r<j-2> +ajbi 연산은 수식(7) 의 결과에서 같은 차수의a의 계수의 합을 구함으로서 수행된다.즉, 각 인덱스 问 대해, j 인덱스에 해당하는 연산을 병렬로 수행함으로써 원 하는 AB2 mod P 연산의 결과를 얻을 수 있다. 여기서, 한행에 있는 모든 열들 간에는 의존성(dependency)이없다. 그러므로 같은 행에 있는 각각의 셀들은 병렬로 수행될 수 있다. 제시한 PSM구조의 분석을 위해서 Dand2와 Dxor2를 각각 2-입력 AND와 XOR 게이트의 딜레이(delay)라고 하면, PSM 구조는 각 셀당 DaND2 + DxOR2의 임계경로를 갖는다. 그리고 전체 지연 시간(latency)은 m+1 이다.〔그림 1〕로 부터 GF(2m) 상에서 PSM구조가 m=4에서 뿐만 아니라. 모든 m에 대해서도 확장시킬 수 있다.〔그림 2〕 는 그림 1의 각 셀에 해당하는 구조를 보여준다. 이 기본셀은 하나의 AND와 XOR게이트로 이루어진다.

〔그림 2) PSM의 기본 구조

3.2 변형된 병렬 세미시스톨릭 어레이 구조(MPSM)

제안된 PSM구조는 하나의 AND와 XOR게이트 로 이루어지고 한셀의 임계경로는 DaND2 + DxOR2 이다. 그러나 중간 결과 값의 누적 연산을 한 단계 늦춤으로 해서 PSM보다 한셀의 임계경로가 좀 더 효율적인 구조를 제시할 수 있다.〔그림 3〕은〔그림 1〕에서 보여준 세미시스톨릭 어레이 구조의 변형된 병렬 세미시스톨릭 어레이 구조(MPSM)를 보여준다.

〔그림 3) GF(24)상에서 MPSM을 위한 병렬 세미시스톨릭 어레이 곱셈기

〔그림 3〕에서 제안된 구조는〔그림 1〕에서 제안된 구조의 임계경로를 줄이기 위해 새롭게 변형된 구조이다. MPSM구조는 마지막 행을 제외한 m개의 행은 〔그림 4〕의 (a) 구조를 갖는다. 마지막 행은 XOR 연산만을 필요로 하는〔그림 4〕의 (b)와 같은 구조를 갖는다. 제안된 MPSM구조의 전체 지연시간은 앞에서 제시된 PSM과 같다. 하지만〔그림 4〕에서 제 시된 바와 같이 각 셀당 DXOR2의 임계경로만을 갖는다. 결과적으로 말하면 MPSM의 지연시간은 PSM 과 같다. 그렇지만 전체 임계경로는 PSM보다 훨씬 더 효율적이다.〔그림 3〕으로부터 GF(2™)상에서 MPSM 구조를 m = 4에서 뿐만아니라, 모든 m에 대해서도 확장시킬 수 있다.

(그림 4) MPSM의 기본 구조들

본 논문에서 제시한 두 구조에서 한 가지 고려되어야 할 사항은 효율적인 모듈라 감소 연산을 위하여 표준기저보다 확장된 기저상에서 연산이 이루어진다는 것이다. 따라서 결과값도 확장된 기저상 에서의 값이다. 이 문제를 해결하기 위해서는 PSM 과 MPSM의 연산 후 그 결과를 다시 모듈라 감소 연산(modular reduction)을 해줌으로써 표준기저 상에서의 결과 값을 얻을 수 있다. 추가적인 모듈라 감소 연산을 위한 구조를〔그림 5〕에서 보여준다.

Ⅳ. 비교 및 분석

본 논문에서는 AB2 연산을 위한 두 가지 병렬 세미시스톨릭 어레이 구조, 즉, PSM과 MPSM을 유한체 GF(2m) 상에서 제안하였다. 역원/나눗셈을 계산하기 위해서 각각 병렬 입출력 세미시스톨릭 구조, 시스톨릭파워 썸(power-sum)구조 및 AOP를 기반으로 한 병렬 입출력 구조가 논문〔10〕, 〔12〕와〔13〕 에 제안되었다.〔표 1〕은 본 논문에서 제시한 구조와 이와 관계된 구조들의 성능 비교를 보여준다.

표에서 2-입력 AND와 XOR게이트의 딜레이(delay) 는 각각 Dand2와 Dxor2이고, latch는 Ibit, 이다.

(표 1) 구조의 성능 비교 및 분석

먼저 논문〔10〕에서 AND와 XOR게이트는 각각 2-입력이고 지연시간이 m+1 이고 임계경로는 Dandz+ Dxor2이다. 그리고 논문〔12〕에서는 AND게이트는 2-입력이고 XOR게이트는 4-입력이다. 그리고 지연시간은 2m+m/2이고 임계경로는 Dand2+Dxor4이다. 또한, 논문〔13〕에서 Itoh가 제안한 구조의 AND 와 XOR의 전체 게이트 수는 각각 W + 2m+l과 그리고 지연시간은 Dand2+「1昭刎+ log2(m + 2) 1 DXOR2이다. 본 논문에서 제안된 구조PSM의 AND와 XOR게이트는 각각 2-입력이다. PSM 은 m+1 의 지연시간을 가졌고 Dand2 + Dxor2의 임계경로를 가졌다. 이에 비해 변형된 구조인 MPSM 은 지연시간은 m+1 을 임계경로로는 Dxor2를 가졌다. 결국 본 논문에서 제안된 두 구조가 논문〔10〕과 비교할 때, 지연시간과 임계경로면에서는 같지만 셀 복잡도 면에서 많이 향상됨을 확인할 수 있다. 그리고 논문〔12〕와 비교하면, 셀 복잡도 및 지연시 간과 임계경로 면에서 아주 효율적이었다. 또한 본 논문에서 제시한 구조와 논문〔13〕의 구조와 구조 복잡도를 비교해보면 AND 및 XOR게이트 수는 비슷하지만 Itoh의 구조는 병렬 입력을 위한 추가적인 연산이 필요하기 때문에 제안한 구조가 Itoh의 구조에 비해서 더 효율적이고 세미시스톨릭 속성을 사용하기 때문에 구조의 정규성을 더 가진다. 제안된 구조는 Altera MAX Plus II 시뮬레이션 툴을 이용하여 시뮬레이션 되었다.

본 논문에서 제안된 惡를 계산하는 PSM과 MPSM 구조는 셀복잡도, 지연시간과 임계경로 면에서 기존의 구조보다 더 효율적이다. 따라서 PSM과 MPSM 을 기반으로 공개키 암호화시스템의 기본 연산인 지 수연산을 한다면, 기존의 구조로 지수 연산을 하는 것보다 더 낳은 결과를 얻을 수 있다. 뿐만 아니라, PSM과 MPSM을 기반으로 한다면 나눗셈과 역원 연산에 있어서도 사용될 수 있고, 공개키암호화시 스템의 성능 향상에 있어서도 기여할 수 있다.

Ⅴ. 결론

본 논문에서는 GF(2, 상의 厶夢를 계산하는 새로운 MSB알고리즘과 두 가지 병렬 세미시스톨릭 어레이 구조를 제안하였다. 일반 기약다항식을 사용하는 것보다 기약다항식으로 AOP의 속성을 사용함으로써 제안된 PSM구조는 전체 m+1의 지연시간을 가졌고 각 셀당 DaND2 + DxOR2의 임계경로를 가졌다. 또한 변형된 MPSM구조는 전체 지연시간은 로 PSM과 같지만 각 셀당 Dxor2의 임계경로만을 가졌다.본 논문에서 제안된 두 구조는 기존의 구조보다 지연시간과 임계경로 면에서 보다 효율적이다. 이 두 구조는 일반 기약다항식을 사용할 때보다 시간 및 공간 복잡도를 줄일 수 있는 장점을 제공한다. 제안된 PSM및 MPSM구조를 기반으로 하여보다 효율적이고 안전한 공개키 암호화시스템을 구현할 수 있다. 또한 제안된 구조는GF]/) 상에서의 효율적인 나눗셈기, 지수기 및 역원기를 설계하는 데 기본구조로 사용될 수 있다. 더욱이 제안된 구조 자체가 정규성(regu-1 arity), 모듈성(modularity), 병렬성(concurrency)을 가지기 때문에 VLSI구현 에 효율적이다.

* 본 연구는 한국과학재단 목적기초 연구 2000-2-51200-081-2 지원으로 수행되었음.