자원이 제약된 장치에서 효율적인 타원곡선 다중 상수배의 구현을 위한 유연한 접근
A Flexible Approach for Efficient Elliptic Curve Multi-Scalar Multiplication on Resource-constrained Devices
0
조회
0
다운로드
0
인용
0
참고문헌
초록
타원곡선 암호시스템은 작은 키 길이로 인하여 스마트카드, 센서 모트와 같은 메모리, 계산 능력이 제약된 장치에서 사용하기에 적합하다. 본 논문에서는 이러한 장치에서 타원곡선 서명 알고리즘 검증 (, 상수, : 타원곡선 위의 점)의 주된 계산인 다중 상수배를 효율적으로 계산하기 위한 알고리즘을 제안한다. 제안 알고리즘은 부분 윈도우와 Interleave 방법에 기반을 둔 것으로서 어떠한 크기의 사전계산 테이블이라도 이용할 수 있을 뿐만 아니라, 해당 테이블에서 최적의 nonzero 밀도를 제공한다. 또한 상수 리코딩이 테이블 조회를 사용하지 않고 상수배 계산과 함께 진행되기 때문에 기존의 다른 알고리즘에 비하여 더욱 메모리를 절약할 수 있다. 실험을 통하여 163 비트의 와, 233 비트의 에 대하여 를 수행하는데 필요한 계산량을 사전계산 테이블의 크기에 따라 비교함으로써 최적의 테이블 크기는 각각 7, 15임을 알아낼 수 있었다.
Abstract
Elliptic Curve Cryptosystem (ECC) is suitable for resource-constrained devices such as smartcards, and sensor motes because of its short key size. This paper presents an efficient multi-scalar multiplication algorithm which is the main component of the verification procedure in Elliptic Curve Digital Signature Algorithm (ECDSA). The proposed algorithm can make use of a precomputed table of variable size and provides an optimal efficiency for that precomputed table. Furthermore, the given scalar is recoded on-the-fly so that it can be merged with the main multiplication procedure. This can achieve more savings on memory than other recoding algorithms. Through experiments, we have found that the optimal sizes of precomputed tables are 7 and 15 when is computed for of 163 bits and 233 bits integers. This is shown by comparing the computation time taken by the proposed algorithm and other existing algorithms.
참고문헌 (17)
- "Use of Elliptic Curves in Cryptography", 85 lncs 218, pp.417~426 (1986)
- "Signed Binary Representation Revisited", lncs 3152, pp.123~139 (2004)
- "Improved Signed-Digit Representation for Efficient Exponentiation", LNCS 3506, pp.137~153 (2004)
- "An Advanced Method for Joint Scalar Multiplications on Memory Constraint Devices", lncs 3813, pp.189~204 (2005)
- "Efficient Arithmetic on Koblitz Curves", 19, pp.195~249 (2000)
- "Analysis of Fractional Window Recoding Methods and Their Application to Elliptic Curve Cryptosystems", 55 (2006)
- "Algorithms for Efficient Simultaneous Elliptic Scalar Multiplication", LNCS 2433, pp.484~499 (2002)
- "Low-Weight Binary Representations for Pairs of Integers", 41 (2001), University of Waterloo
- "An Improved Algorithm for uP + vQ Using JSF3", lncs 3089, pp.467~478 (2004)
- "Algorithms for Multi- exponentiation", lncs 2259, pp.165~180 (2001)
- "Improved Techniques for Fast Exponentiation", ICISC 2002, pp.298~312 (2003)
- "Left-to- Right Optimal Signed-Binary Representation of a Pair of Integers", 54 (2005)
- "Efficient Elliptic Curve Exponentiation Using Mixed Coordinates", lncs 1514, pp.51~65 (1998)
- "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick", lncs 2523, pp.564~578 (2003)
- "Standard Specifications for Public Key Cryptography" (1999)
- "On the Performance of Signature Schemes Based on Elliptic Curves", pp.252~266 (1998)
- "SEC 2-Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography. 1999. 아주대학교 정보 및 컴퓨터공학과 졸업2005월 3월-현재 광주과학기술원 정보통신공학과 석사과정 경북대학교 컴퓨터과학과 졸업2003년 8월 광주과학기술원 정보통신공학과 석사 졸업2003년 9월-현재 광주과학기술원 정보통신공학과 박사과정 Indian Institute of Technology 전자공학과 박사1980년-1986년 Indian Institute of Technology Indian Institute of Technology"