자원이 제약된 장치에서 효율적인 타원곡선 다중 상수배의 구현을 위한 유연한 접근

Vol. 16, No. 6, pp. 95-110, 12월. 2006
10.13089/JKIISC.2006.16.6.95, Full Text:
Keywords: Elliptic curve cryptosystems, Multi-Scalar Multiplication, Fractional width-w MOF
Abstract

타원곡선 암호시스템은 작은 키 길이로 인하여 스마트카드, 센서 모트와 같은 메모리, 계산 능력이 제약된 장치에서 사용하기에 적합하다. 본 논문에서는 이러한 장치에서 타원곡선 서명 알고리즘 검증 (uP+vQ, u, v: 상수, P, Q: 타원곡선 위의 점)의 주된 계산인 다중 상수배를 효율적으로 계산하기 위한 알고리즘을 제안한다. 제안 알고리즘은 부분 윈도우와 Interleave 방법에 기반을 둔 것으로서 어떠한 크기의 사전계산 테이블이라도 이용할 수 있을 뿐만 아니라, 해당 테이블에서 최적의 nonzero 밀도를 제공한다. 또한 상수 리코딩이 테이블 조회를 사용하지 않고 상수배 계산과 함께 진행되기 때문에 기존의 다른 알고리즘에 비하여 더욱 메모리를 절약할 수 있다. 실험을 통하여 163비트의 u, v와, 233 비트의 u, v에 대하여 uP+vQ를 수행하는 데 필요한 계산량을 사전계산 테이블의 크기에 따라 비교함으로써 최적의 테이블 크기는 각각 7, 15임을 알아낼 수 있었다.

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]
S. Seo, H. Kim and R. Ramakrishna, "A Flexible Approach for Efficient Elliptic Curve Multi-Scalar Multiplication on Resource-constrained Devices," Journal of The Korea Institute of Information Security and Cryptology, vol. 16, no. 6, pp. 95-110, 2006. DOI: 10.13089/JKIISC.2006.16.6.95.

[ACM Style]
Seog-Chung Seo, Hyung-Chan Kim, and R.S. Ramakrishna. 2006. A Flexible Approach for Efficient Elliptic Curve Multi-Scalar Multiplication on Resource-constrained Devices. Journal of The Korea Institute of Information Security and Cryptology, 16, 6, (2006), 95-110. DOI: 10.13089/JKIISC.2006.16.6.95.