최적확장체 위에서 정의되는 타원곡선에서의 고속 상수배 알고리즘
Fast Scalar Multiplication Algorithm on Elliptic Curve over Optimal Extension Fields
1
조회
0
다운로드
0
인용
0
참고문헌
초록
EC-DSA나 EC-ElGamal과 같은 타원곡선 암호시스템의 성능 향상을 위해서는 타원곡선 상수배 연산을 빠르게 하는 것이 필수적이다. 타원곡선 특유의 Frobenius 사상을 이용한 base- 전개 방식은 Koblitz에 의해 처음 제안되었으며, Kobayashi 등은 최적확장체 위에서 정의되는 타원곡선에 적용할 수 있도록 base- 전개 방식을 개선하였다. 그러나 Kobayashi 등의 방법은 여전히 개선의 여지가 남아있다. 본 논문에서는 최적확장체에서 정의되는 타원곡선 상에서 효율적인 상수배 연산 알고리즘을 제안한다. 제안한 상수배 알고리즘은 Frobenius 사상을 이용하여 상수 값을 Horner의 방법으로 base- 전개하고, 이 전개된 수식을 최적화된 일괄처리 기법을 적용하여 연산한다. 제안한 알고리즘을 적용할 경우, Kobayashi 등이 제안한 상수배 알고리즘보다 20%～40% 정도의 속도 개선이 있으며, 기존의 이진 방법에 비해 3배 이상 빠른 성능을 보인다.
Abstract
Speeding up scalar multiplication of an elliptic curve point has been a prime approach to efficient implementation of elliptic curve schemes such as EC-DSA and EC-ElGamal. Koblitz introduced a base- expansion method using the Frobenius map. Kobayashi et al. extended the base- scalar multiplication method to suit Optimal Extension Fields(OEF) by introducing the table reference method. In this paper we propose an efficient scalar multiplication algorithm on elliptic curve over OEF. The proposed base- scalar multiplication method uses an optimized batch technique after rearranging the computation sequence of base- expansion usually called Horner's rule. The simulation results show that the new method accelerates the scalar multiplication about 20%～40% over the Kobayashi et al. method and is about three times as fast as some conventional scalar multiplication methods.
참고문헌 (15)
- "Use of Elliptic Curve in Cryptography in Advances in Cryptology - CRYPTO'85", pp.417~426 (1985)
- "Mathematics of Computa- tion", pp.203~209 (1987)
- "Fast Attacks on Elliptic Curve Crypto- systems" (1998)
- "Elliptic Curve Crypto- systems", 1(2), pp.1~4 (1995)
- "A Survey of Fast Exponentiation Methods", 27, pp.129~146 (1998)
- "CM-curves with Good Cryptogrpahic Properties in Advances in Cryptology - CRYPTO'91", pp.279~576 287 (1991)
- "Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two", 11, pp.219~234 (1998)
- "Two Efficient Algorithms for Arithmetic of Elliptic Curves Using Frobenius Map", pp.195~202 (1998)
- "An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm", 1462, pp.327~337 (1998)
- "Elliptic Curve Crypto- system over Small Fields of Odd Characteristic", 12, pp.141~151 (1999)
- "Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms in", 1462, pp.472~485 (1998), Paar
- "Fast Elliptic Curve Algorithm Combining Frobe- nius Map and Table Reference to Adapt to Higher Characteristic in Advances in", 1592, pp.176~189 (1999)
- "The Art of Computer Programming", me 2 (1981)
- "Batch Exponentiation : A First DLP-based Signature Generation Strategy", pp.58~61 (1996)
- "TTA 표준 : 부가형 전자 서명 방식 표준 - 제3부 : 타원곡선을 이용한 인증서 기반 전자 서명 알고리즘" (2001)