합성체를 이용한 유한체의 역원 계산 알고리즘 구현

Abstract

유한체(Finite field or Galois field)는 스위칭 이론, 디지털 신호처리 및 화상처리, 디지털 통신의 암호화 및 해독화를 요하는 보안 통신 등에서 많이 응용되고 있다. 특히 오류정정부호 중 BCH 부호나 Reed-Solomon 부호와 같은 블록부호는 유한체 상에서 정의되며, CD(Compact Disc), DAT(Digital Audio Tape), 타원곡선 알고리즘 등의 부호화 및 복호화에 GF(2ⁿ)의 산술연산이 적용되어진다. 현재 많은 응용분야에서 유한체 연산의 실시간 처리를 요하므로 유한체 연산을 위한 전용 하드웨어 설계가 필요하게 되었고 이에 대한 많은 연구가 행하여지고 있다. 유한체는 사칙연산이 정의되는 유한개의 연소를 갖는 필드이며 모든 소수 P와 양수 N에 대해서 P^(N)개의 원소를 갖는 하나의 필드만이 존재한다. 이 필드를 유한체 필드라고 부르며 GF(P^(N))으로 나타낸다. 유한체 상에서의 연산은 가ㆍ감산과 승산, 그리고 제산이 있으나 디지털 시스템은 유한체의 개수가 2의 승수인 GF(2^(N))에서 이루어진다. 유한체의 역원의 계산은 크게 유한체 제산기를 이용하는 방법과 승산기를 이용하는 방법으로 나누어진다. 제산기를 이용하는 방법은 빠른 동작 속도를 가지나 하드웨어의 면적이 커지며, 승산기를 이용한 방법은 하드웨어의 면적은 작아지나 계산에 많은 시간이 소모된다. 본 논문에서는 합성체(Composite Fields)를 이용하여 GF(256)의 유한체의 역원을 계산할 수 있는 알고리즘을 제시하고 이를 하드웨어로 구현하여 현재 사용되어지는 'Itoh and Tsujii' 하드웨어 구조와 하드웨어 면적 및 계산 속도의 성능을 비교 하였다. 또한 AES의 SubBytes 블록에 이를 삽입하여 Altera FLEX10K FPGA 에뮬레이터 보드에 구현하여 제시된 알고리즘의 회로가 정상적으로 동작함을 확인하였다.