유한체(finite fields or Galois fields) 상의 연산은 오류정정 부호, 디지털 신호처리, 타원곡선 암호화 등에서 매우 중요하게 사용되고 있다[1]-[3]. 유한체 연산중에서 덧셈은 비트별 2원합(modulo-2 sum)으로 쉽게 구현할 수 있는 반면에 곱셈과 나눗셈은 상당히 복잡한 연산이다. 이 중에서 곱셈을 반복적으로 사용하면 나눗셈이나 지수승과 같은 복잡한 연산을 구현할 수 있기 때문에, 곱셈이 유한체 연산중에서 가장 핵심이 되는 연산이 된다[4][5].

유한체 상의 연산에서 주로 사용하는 다항식기저(polynomial basis), 쌍대기저(dual basis)[6], 정규기저(normal basis)[7]-[9] 등이 있다. 이 중에서 정규기저를 사용하면 제곱 연산이 한 비트 순회치환(cyclic shift)만으로 수행될 수 있는 장점이 있다. 즉, 하드웨어로 구현 시 결선만 바꾸면 되므로 비용이 소요되지 않는다. 따라서 정규기저는 여러 가지 타원곡선 암호시스템의 표준에서 널리 사용되고 있으며, 정규기저를 이용한 많은 곱셈기들이 제안되고 있다[10]-[13]. 본 논문에서는 이러한 정규기저의 특성을 이용하여 새로운 비트직렬/디지트병렬 곱셈기를 설계한다.

GF(2^m)의 곱셈기는 비트병렬(bit-parallel) 곱셈기와 비트직렬(bit-serial) 곱셈기로 구현할 수 있다. 비트병렬 곱셈기는 곱셈의 결과를 한 클럭(clock) 안에 출력하는 회로로 연산속도는 빠른 반면에 회로가 복잡하며[14]-[16], 비트직렬 곱셈기는 회로는 간단하지만 m 클럭만큼의 시간 지연이 생긴다[17][18].

본 논문에서는 기존의 비트직렬 곱셈기의 긴 지연시간과 비트병렬 곱셈기의 높은 회로 복잡도 사이에 적절한 절충이 가능한 새로운 비트직렬/디지트병렬 곱셈기를 설계한다. 제안한 곱셈기는 유한체의 정규기저 상에서 곱셈의 한 원소를 w 비트씩 묶어서 각각은 비트직렬 방식으로 구현하고, 전체를 동시에 병렬로 처리하는 방식으로 속도를 향상시키는 것이다.

제안된 곱셈기는 기존의 비트병렬 곱셈기에 비해서는 적은 면적으로 구현할 수 있고 비트직렬 곱셈기보다는 짧은 지연시간에 결과를 얻을 수 있다. 제안한 곱셈기는 회로의 복잡도와 지연시간 사이에 적절한 절충을 꾀할 수 있는 장점을 가지고 있다.

본 논문의 구성은 먼저 2.에서 유한체 GF(2^m)의 정규기저에서 동작하는 비트직렬 곱셈 알고리즘을 분석하고, 새로운 비트직렬/디지트병렬 정규기저 곱셈기를 설계한다. 3.에서 실제 예로써 GF(2⁷)에서 3클럭만에 곱셈의 결과를 출력하는 비트직렬/디지트병렬 정규기저 곱셈기를 설계한다. 그리고 4.에서 결론을 맺는다.

유한체 GF(2^m) 상에서 정규기저를 이용하여 임의의 한 원소 A를 표현하면

가 된다. 여기에서 β^2m=β이므로, 식 (1)과 같은 임의의 한 원소를 제곱하면 다음과 같이 된다.

즉, 정규기저에서는 한 비트 순회치환(cyclic shift)하면 제곱 연산을 구현할 수 있다.

유한체 GF(2^m) 상에서 임의의 두 원소 A와 B의 곱 C는 다음과 같이 표현할 수 있다.

식 (3)을 풀어 쓰면 다음과 같이 된다.

식 (4)는 다음과 같이 다시 정리할 수 있다.

식 (5)는 입력 A를 계속해서 2^-1승을 하면서 입력 B의 계수를 낮은 차수부터 차례로 β와 곱하고 그 결과를 계속해서 2^-1승을 하면서 m 클럭까지 더해 가는 것이다. 식 (5)를 이용하면 <그림 1>과 같은 정규기저 상의 비트직렬 곱셈기를 설계할 수 있다[17].

<그림 1>에서 굵은 선은 m비트 버스를 나타낸 것이고, □는 m비트 레지스터를, ⊕는 m개의 2입력 XOR 게이트를, ⊙은 m개의 2입력 AND 게이트를, 는 GF(2^m) 상의 한 원소 β를 곱하는 상수 곱셈기를 나타내고 있다. 또한 점선으로 된 사각형은 2의 멱승을 수행하는 회로로 정규기저 상에서는 결선만 바꾸는 것이다. 또 2^-1승은 각 계수를 왼쪽으로 한 번 순회치환 하는 것이고 2^m-1승은 각 계수를 오른쪽으로 m-1번 순회치환 하는 것이다.

<그림 1>과 같은 곱셈기는 m 클럭 시간 후에 결과를 얻을 수 있다. 이와 같은 비트직렬 곱셈기의 지연을 줄여서 고속화하기 위하여, 식 (3)에서 곱하는 두 원소 중 하나인 원소 B를 다음과 같이 w 비트씩 묶어서 d(d=m/w) 개로 분할한다.

여기에서 C를 다음과 같이 정의하면

C의 각각의 항은 다음과 같이 정리할 수 있다.

⋮

식 (8)과 같은 C₀는 m 대신에 w를 대입하면 식 (4)와 같은 구조임을 알 수 있다. 식 (9)와 같은 C₁은 다음과 같이 정리할 수 있다.

식 (12)는 A 대신에 A2-w를 대입하면 역시 식 (4)와 동일한 구조가 된다. 식 (10)과 같은 C₂을 같은 형태로 정리하면 다음과 같이 된다.

식 (13)도 A 대신에 A2-2w를 대입하면 역시 식 (4)와 동일한 구조가 된다. 계속해서 식 (11)의 C_d-1도 같은 방법으로 정리할 수 있다.

식 (14)도 A 대신에 A2-d-1w를 대입하면 역시 식 (4)와 같은 구조가 된다. 따라서 식 (12)~(14)를 이용하면 <그림 2>와 같은 비트직렬/디지트병렬 정규기저 곱셈기를 설계할 수 있다. 설계된 곱셈기는 입력되는 한 원소를 w 비트씩 나누어 d개의 디지트로 분리한 다음, 각각의 디지트를 직렬 곱셈기를 이용하여 병렬로 처리한다.

<그림 2>의 회로는 초기 상태에서 레지스터 U에는 입력 A를 로드시키고 레지스터 Z는 클리어시키킨다. 레지스터 V에는 입력 B를 w비트씩 나눈 값을 로드시킨다. 첫 번째 클럭에서 각 디지트의 첫 번째 비트인 b₀, b_w, b_2w ……, b_(d-1)w가 입력되고, 두 번째 클럭에서는 각 디지트의 두 번째 비트가, ……, 그리고 w 번째 클럭에서는 각 디지트의 마지막 비트가 입력된다. m개의 비트가 모두 입력되면 레지스터 V의 끝에는 0으로 채워진다. 그러므로 곱셈의 결과를 w 클럭 후에 얻을 수 있다.

<그림 2>의 곱셈기를 <그림 1>의 곱셈기와 비교해보면, (d-1)m개의 2입력 XOR 게이트, (d-1)m개의 2입력 AND 게이트, 그리고 (d-1)개의 β를 곱하는 상수 곱셈기가 더 사용되었음을 알 수 있다. 여기에서 d는 m/w이다.

실제 예로서 유한체 GF(2⁷) 상에서 3클럭만에 곱셈의 결과를 출력하는 곱셈기를 설계하여 보자. 유한체 GF(2⁷)에서 임의의 두 원소의 곱 C는

가 된다. 여기에서 B를 3 비트씩 묶으면

가 된다. 또한 식 (17)과 식 (18)을 다시 정리하면 다음과 같이 된다.

식 (16), 식 (19), 식 (20)을 이용하면 <그림 3>과 같은 곱셈기를 설계할 수 있다.

<그림 3>에서 β를 곱하는 상수 곱셈기를 설계하기 위하여 유한체 GF(2⁷)의 임의의 한 원소 A에 β를 곱하여 정리하면 다음과 같이 된다.

여기에서는 식 (22)와 같은 유한체 GF(2⁷)의 타입 4 가우시안 정규기저(Gaussian Normal Basis) 상의 곱셈 행렬(multiplication matrix)을 사용하였다[10].

식 (21)을 이용하면 <그림 4>와 같이 GF(2⁷) 상의 비트직렬/디지트병렬 정규기저 곱셈기를 게이트 레벨로 설계할 수 있다. <그림 4>의 곱셈기는 w=3 클럭만에 곱셈의 결과를 얻을 수 있다. <그림 4>와 같이 설계된 곱셈기는 C 언어로 시뮬레이션 하여 그 동작을 검증하였다.

본 논문에서는 유한체 GF(2^m)의 곱셈에서 정규기저를 이용하여 곱하는 임의의 한 원소를 w 비트씩 묶은 다음, 각각의 항들을 비트직렬 곱셈기를 사용하여 동시에 병렬로 처리하는 방식을 사용함으로써, w (1 ≤ w ≤ m) 클럭만에 곱셈의 결과를 얻을 수 있는 새로운 비트직렬/디지트병렬 정규기저 곱셈기를 설계하였다.

설계된 곱셈기는 비트병렬 곱셈기의 복잡한 회로와 비트직렬 곱셈기의 긴 지연시간을 설계자가 적절하게 절충함으로써, 비트병렬 곱셈기보다는 적은 하드웨어로 구현할 수 있으며 비트직렬 곱셈기보다는 짧은 지연시간에 결과를 얻을 수 있는 장점을 가지고 있다.