효율적인 유한체 역원 알고리즘에 대한 연구
- 발행기관 고려대학교 정보보호대학원
- 발행년도 2004
- 학위명 박사
- 학과 정보보호대학원:정보보호
- 식별자(기타) DL:000014914302
- 서지제어번호 000045212979
초록/요약
유비쿼터스 환경의 정보보호에 대한 관심이 증가되면서 경량화 및 고속화된 차세대 암호 시스템의 설계가 요구되고 있다. 이에 따라 동일한 안전도를 유지하면서 다른 공개키 암호 시스템보다 적은 길이의 키를 가진 타원곡선 암호시스템이 주목받고 있다. 공개키 기반 암호 시스템의 수행시간은 주로 곱셈 및 역원 연산의 수행시간을 기반으로 하며, 이 중 역원 연산이 곱셈에 비해 시간복잡도가 크므로 개선에 대한 연구가 활발히 진행되고 있다. 역원 알고리즘은 유한체의 기저에 따라 제안되며, 특히 유한체 GF(2m)의 다항식 기저에서 Extended Euclid's Algorithm(EEA)나 Extended Binary GCD Algorithm(EBGA)을 바탕으로 한다. 기존에 제안된 역원기는 수행횟수를 2m번으로 고정된 알고리즘을 사용하며 시스톨릭 어레이 구조(Systolic Array Structure)를 제시하였다. 그러나 m이 커지는 경우 하드웨어 면적과 리소스 요구량이 증가하므로 경량화가 요구되는 하드웨어 구조에 적합하지 않다. 본 논문에서는 다항식 기저를 기반으로 기존의 알고리즘에 비해 65%인 수행횟수를 가진 새로운 역원 알고리즘을 제안한다. 기존의 시스톨릭 구조보다 적은 공간 복잡도를 가지는 하드웨어 구조를 제시한다. 기존에 비해 덧셈기의 수와 최대 지연 경로를 다소 증가하나 연구한 결과, 제안한 역원 알고리즘은 기존의 알고리즘의 덧셈 연산 수행횟수와 차이를 보이지 않았다. 또한 제안한 알고리즘은 모듈러 감산 연산의 평균 수행횟수를 비교하면 기존의 알고리즘에 비해 1.5배 빠르게 수행한다. 제시한 하드웨어 구조는 모듈러 감산 연산을 효율적으로 처리하였으며 제어 로직을 단순하게 개선하였다. 이는 처리 능력과 에너지 가용 능력이 제한된 환경인 스마트 카드, 휴대용 단말기 등의 장비에 효과적으로 적용될 수 있을 것이다.
more목차
제1장 서론
제1절 소개
제2절 유한체에서 역원 알고리즘의 구성과 복잡도
제2장 수학적 배경
제1절 수학적 이론
1.1 군, 환 그리고 체
1.2 유한체 위헤서 정의된 환
1.3 확장체
1.4 최적 확장체
제2절 유한체의 기저와 연산
제3절 유한체 위헤서의 타원곡선
3.1 정의
3.2 타원군의 법칙
3.3 판별식과 j-불변량
3.4 체 K위의 곡선들, char(K)!=2
제4절 타원곡선의 응용
4.1 ECDSA
4.2 ECDH
제3장 유한체 GF(2m)에서 기존의 역원 알고리즘 분석
제1절 정규기저에서의 역원 알고리즘
1.1 Itho-Tsujii Inversion for OEF
제2절 다항식기저에서의 역원 알고리즘
2.1 Extended Euclid's Algorithm for GF(2m)
2.2 Extended Binary GCD Algorithm for GF(2m)
2.3 Almost Inversion Algorithm for GF(2m)
제4장 유한체 GF(2m)에서 제안하는 역원 알고리즘
제1절 유한체 GF(2m)에서 제안하는 역원 알고리즘
제2절 제안하는 역원 알고리즘의 하드웨어 구조
제3절 제안하는 역원 알고리즘의 효율성 분석
제5장 결론
