일반기술

유한체에서의 역원 연산 장치 및 방법

유한체에서의 역원 연산 장치 및 방법이 개시된다. 제1연산부는 유한체 GF(2m)의 원소인 제1다항식 A(x)와 소정의 m차기약다항식인 제2다항식 G(x)를 입력으로 하고, 제1다항식과 제2다항식을 각각 소정의 제1내부변수 및 제2내부변수의 초기값으로 설정한 후 교환연산제어변수, 제1내부변수의 최하위비트값, 및 제1내부변수와 제2내부변수의 최하위비트의 인접비트값의 동일여부에 따라 제1내부변수가 1이 될 때까지 제1내부변수와 제2내부변수에 대한 교환연산, 쉬프트연산, 및 덧셈연산을 선택적으로 반복수행한다. 제2연산부는 교환연산제어변수, 제1내부변수의 최하위비트값, 및 제1내부변수와 제2내부변수의 최하위비트의 인접비트값의 동일여부에 따라 제1내부변수가 1이 될 때까지 소정의 초기값이 설정된 제3내부변수 및 제4내부변수에 대한 교환연산, 쉬프트연산, 및 덧셈연산을 선택적으로 반복수행하며, 상기 덧셈연산을 수행하는 동안 제2다항식에 대해 G(x)/x 및 (G+Gx)/x 연산을 수행하여 얻어진 G(x), G(x)/x, 및 (G+Gx)/x 중에서 선택된 제3다항식과 제4내부변수의 값을 합산하여 모듈러 감산 연산을 수행한다. 제어부는 제1내부변수가 1이 되면 제3내부변수를 제1다항식의 역원으로 출력한다.본 발명에 따른 유한체에서의 역원 연산 장치 및 방법에 의하면, 종래의 역원 연산 알고리즘에 비해 1.5배 빠르게 연산을 수행할 수 있고, 종래의 역원 연산 알고리즘의 수행횟수의 65%정도로 수행횟수를 줄일 수 있다. 또한, 본 발명에 따른 유한체에서의 역원 연산 장치는 종래의 역원 연산 알고리즘을 구현한 하드웨어보다 모듈러 감산 연산을 효율적으로 처리하며, 덧셈기의 수는 증가하였으나 덧셈 연산 수행횟수는 종래의 역원 연산 알고리즘을 구현한 하드웨어와 거의 비슷하다. 또한, 본 발명에 따른 유한체에서의 역원 연산 장치는 종래의 역원 연산 알고리즘을 구현한 하드웨어와 거의 유사한 최대지연경로를 가지고 있으며, 제어 부분이 종래의 역원 연산 알고리즘을 구현한 하드웨어보다 단순하다. 이와 같은 장점으로 인해 본 발명에 따른 유한체에서의 역원 연산 장치 및 방법은 GF(p)에서의 역원 알고리즘으로 확장이 가능하여, 공개키 암호 시스템의 효율성을 높일 수 있으며, 나아가, 처리 능력과 에너지 가용 능력이 제한된 환경인 스마트 카드, 토큰 하드웨어, 휴대용 단말기 등의 장비에 효과적으로 적용될 수 있다.본 발명에 따른 유한체에서의 역원 연산 장치 및 방법에 의하면, 종래의 역원 연산 알고리즘에 비해 1.5배 빠르게 연산을 수행할 수 있고, 종래의 역원 연산 알고리즘의 수행횟수의 65%정도로 수행횟수를 줄일 수 있다. 또한, 본 발명에 따른 유한체에서의 역원 연산 장치는 종래의 역원 연산 알고리즘을 구현한 하드웨어보다 모듈러 감산 연산을 효율적으로 처리하며, 덧셈기의 수는 증가하였으나 덧셈 연산 수행횟수는 종래의 역원 연산 알고리즘을 구현한 하드웨어와 거의 비슷하다. 또한, 본 발명에 따른 유한체에서의 역원 연산 장치는 종래의 역원 연산 알고리즘을 구현한 하드웨어와 거의 유사한 최대지연경로를 가지고 있으며, 제어 부분이 종래의 역원 연산 알고리즘을 구현한 하드웨어보다 단순하다. 이와 같은 장점으로 인해 본 발명에 따른 유한체에서의 역원 연산 장치 및 방법은 GF(p)에서의 역원 알고리즘으로 확장이 가능하여, 공개키 암호 시스템의 효율성을 높일 수 있으며, 나아가, 처리 능력과 에너지 가용 능력이 제한된 환경인 스마트 카드, 토큰 하드웨어, 휴대용 단말기 등의 장비에 효과적으로 적용될 수 있다.