최적확장체 위에서 정의되는 타원곡선에서의 고속 상수배 알고리즘

Abstract

EC-DSA나 EC-ElGamal과 같은 타원곡선 암호시스템의 성능 향상을 위해서는 타원곡선 상수배 연산을 빠르게 하는 것이 필수적이다. 타원곡선 특유의 Frobenius 사상을 이용한 base- 전개 방식은 Koblitz에 의해 처음 제안되었으며, Kobayashi 등은 최적확장체 위에서 정의되는 타원곡선에 적용할 수 있도록 base- 전개 방식을 개선하였다. 그러나 Kobayashi 등의 방법은 여전히 개선의 여지가 남아있다. 본 논문에서는 최적확장체에서 정의되는 타원곡선 상에서 효율적인 상수배 연산 알고리즘을 제안한다. 제안한 상수배 알고리즘은 Frobenius 사상을 이용하여 상수 값을 Horner의 방법으로 base- 전개하고, 이 전개된 수식을 최적화된 일괄처리 기법을 적용하여 연산한다. 제안한 알고리즘을 적용할 경우, Kobayashi 등이 제안한 상수배 알고리즘보다 20%～40% 정도의 속도 개선이 있으며, 기존의 이진 방법에 비해 3배 이상 빠른 성능을 보인다.