Weil 정리를 이용한 효율적인 타원곡선의 위수 계산법의 구현

• 영문명: Efficient Implementations of Index Calculation Methods of Elliptic Curves using Weil’s Theorem
• 발행기관: 한국전자통신학회
• 저자명: 김용태(Yong Tae Kim)
• 간행물 정보: 『한국전자통신학회 논문지』제11권 제7호, 693~699쪽, 전체 7쪽
• 주제분류: 공학 > 전자/정보통신공학
• 파일형태: PDF
• 발행일자: 2016.07.30

국문 초록

현재 사용되고 있는 유한체 GF(q) 위의 non-supersingular 타원곡선 이산대수문제에 기반한 공개키 암호법의 안전성을 보장하기 위해서는 타원곡선의 위수의 크기와 소인수의 크기를 계산하는 일이 매우 중요하다. 그런데 타원곡선의 위수를 구하는 전통적인 방법인 Schoof 알고리즘은 매우 복잡하여 지금도 개선작업이 진행중이다. 본 논문에서는 복잡한 Schoof 알고리즘을 피하기 위하여, 표수가 2인 유한체의 합성체 GF(2m)=GF(2rs)=GF((2r)s) 위에서 Weil 정리를 이용하여 타원곡선의 위수를 계산하는 방법을 제안한다. 또한, 그에 따른 알고리즘과 그 알고리즘을 적용한 프로그램을 실행하여 타원곡선 암호법에 사용될 수 있는 효율적인 곡선으로 #E(GF(2⁵))=36일 때의 합성체 GF((2⁵)c³¹)위에서 위수에 10⁴⁰ 이상인 소인수를 포함하는 non-supersingular 타원곡선을 찾을 수 있었다.

영문 초록

It is important that we can calculate the order of non-supersingular elliptic curves with large prime factors over the finite field GF(q) to guarantee the security of public key cryptosystems based on discrete logarithm problem(DLP). Schoof algorithm, however, which is used to calculate the order of the non-supersingular elliptic curves currently is so complicated that many papers are appeared recently to update the algorithm. To avoid Schoof algorithm, in this paper, we propose an algorithm to calculate orders of elliptic curves over finite composite fields of the forms GF(2m)=GF(2rs)=GF((2r)s) using Weil’s theorem. Implementing the program based on the proposed algorithm, we find a efficient non-supersingular elliptic curve over the finite composite field GF((2⁵)c³¹) of the order larger than 10⁴⁰ with prime factor larger than 10⁴⁰ using the elliptic curve E(GF(2⁵)) of the order 36.

목차

요약

ABSTRACT

Ⅰ. 서론

Ⅱ. 표수가 2인 타원곡선

Ⅲ. 타원곡선의 위수

Ⅳ. 제안하는 타원곡선의 위수 계산법

Ⅴ. 수치실험 및 프로그램

Ⅵ. 결론

References

키워드

타원 곡선 위수 non-supersingular 타원 곡선 Schoof 알고리즘 Weil 정리 Order Of The Elliptic Curve Non-Supersingular Elliptic Curve Schoof Algorithm Weil’S Theorem