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

Vol. 15, No. 3, pp. 65-76, 6월. 2005
10.13089/JKIISC.2005.15.3.65, Full Text:
Keywords: Elliptic curve, Scalar Multiplication, Frobenius map, Batch technique, OEF
Abstract

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

Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
C. Byungchun, L. Soojin, H. Seong-Min and Y. Hyunsoo, "Fast Scalar Multiplication Algorithm on Elliptic Curve over Optimal Extension Fields," Journal of The Korea Institute of Information Security and Cryptology, vol. 15, no. 3, pp. 65-76, 2005. DOI: 10.13089/JKIISC.2005.15.3.65.

[ACM Style]
Chung Byungchun, Lee Soojin, Hong Seong-Min, and Yoon Hyunsoo. 2005. Fast Scalar Multiplication Algorithm on Elliptic Curve over Optimal Extension Fields. Journal of The Korea Institute of Information Security and Cryptology, 15, 3, (2005), 65-76. DOI: 10.13089/JKIISC.2005.15.3.65.