타원곡선암호시스템에서 Montgomery ladder 방법에 기반한 새로운 스칼라 곱셈 알고리즘
New Efficient Scalar Multiplication Algorithms Based on Montgomery Ladder Method for Elliptic Curve Cryptosystems
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 논문에서는 Montgomery ladder 방법을 확장한 효율적인 스칼라 곱셈 알고리즘을 제안한다. 제안하는 방법은 효율성을 높이기 위하여 스칼라를 ternary 또는 quaternary로 표현하고 아핀좌표계에서 Montgomery ladder 방법과 같이 좌표만을 이용하여 연산 가능하도록 하는 새로운 연산식을 적용한다. 그리고 단순전력분석에 안전하도록 Side-channel atomicity를 적용하였다. 또한 Montgomery trick을 사용하여 연산속도를 높였다. 제안하는 방법은 기존에 효율적으로 알려진 window method, comb method에 비해서 연산속도가 26% 이상 향상된다. 또한 이 방법들보다 저장공간을 적게 사용하는 장점도 가지고 있다.
Abstract
This paper proposes efficient scalar multiplication algorithms based on Montgomery ladder method. The proposed algorithm represents the scalar as ternary or quaternary and applies new composite formulas utilizing only coordinate on affine coordinate system in order to improve performance. Furthermore, side-channel atomicity mechanism is applied on the proposed composite formulas to prevent simple power analysis. The proposed methods saves at least 26% of running time with the reduced number of storage compared with existing algorithms such as window-based methods and comb-based methods.
참고문헌 (28)
- N. Koblitz, "Elliptic Curve Cryptosystems", Mathematics of Computation, 48(177), pp.203~309 (1987)
- V. Miller, "Uses of Elliptic Curves in Cryptography", Advances in cryptography -CRYPTO 85’, pp.417~426 (1986)
- I. Blake, "Elliptic Curves in Cryptography" (1999), Cambridge University Press
- F. Morain, "Speeding up the computation of an elliptic curve using addition-subtraction chains", Informatique théorique et Applications, pp.531~544 (1990)
- M. Ciet, "Trading inversions for multiplications in elliptic curve cryptography", Designs, Codes and Cryptography, 39(2), pp.189~206 (2006)
- H. Cohen, "Efficient elliptic curve exponentiation using mixed coordinates", Asiacrypt98, pp.51~65 (1998)
- K. Eisenträger, "Fast elliptic curve arithmetic and improved Weil pairing evaluation", Topics in Cryptology-CT-RSA 2003, pp.343~354 (2003)
- H. Cohen, "A course in computational algebraic number theory : Graduate Texts in Mathematics" (1993), Springer-Verlag
- P. Kocher, "Timing Attacks on Implementations of Diffie- Hellman, RSA, DSS, and Others Systems", CRYPTO'96, pp.104~113 (1996)
- 한동국, "단순전력분석에 안전한 Signed Left-to-Right 리코딩 방법", 정보보호학회논문지, 17(1), pp.127~132 (2007), 한국정보보호학회
- 김성경, "SPA에 안전한 Unsigned Left-to-Right 리코딩 방법", 정보보호학회논문지, 17(1), pp.21~32 (2007), 한국정보보호학회
- 김태현, "부채널 공격에 안전한 타원곡선 스칼라 곱셈 알고리즘", 정보보호학회논문지, 14(6), pp.125~134 (2004), 한국정보보호학회
- 임채훈, "부가채널 공격에 안전한 효율적인 타원곡선 상수배 알고리즘", 정보보호학회논문지, 12(4), pp.99~114 (2002), 한국정보보호학회
- 한동국, "랜덤한 덧셈-뺄셈 체인에 대한 부채널 공격", 정보보호학회논문지, 14(5), pp.121~133 (2004), 한국정보보호학회
- V. Dimitrov, "Efficient and Secure Elliptic Curve Point Multiplication using Double Base Chain. In: Roy, B", ASIACRYPT 2005, pp.59~79 (2005)
- T. Izu, "A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks", PKC 2002, pp.280~296 (2002)
- E. Brier, "Weierstrass Elliptic Curves and Side-Channel Attacks", Public Key Cryptography (PKC2002), pp.335~345 (2002)
- B.C. Mames, "Low-cost solutions for preventing simple side-channel analysis: Side-channel atomicity", IEEE Transactions on Computers, 53(6), pp.760~768 (2004)
- D. Hankerson, "Guide to elliptic curve cryptography" (2004), Springer-Verlag
- P. Kocher, "Differential power analysis", CRYPTO 1999, pp.388~397 (1999)
- J. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems", CHES'99, pp.292~302 (1999)
- B. M¨oller, "Securing Elliptic Curve Point Multiplication against Side-Channel Attacks", ICS 2001, pp.324~334 (2001)
- K. Okeya, "The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplication Secure against Side Channel Attacks", CT-RSA 2003, pp.328~342 (2003)
- J. Lopez, "Fast Multiplication on Elliptic Curves over without Precomputation", Cryptographic Hadware and Embedded Systems-CHES'99, pp.316~327 (1999)
- J.A. Solinas, "Efficient Arithmetic on Koblitz Curves", Designs, Codes and Cryptography, 19(2), pp.195~249 (2000)
- P.K. Mishra, "Efficient Quintuple Formulas for Elliptic Curves and Efficient Scalar Multiplication Using Multibase Number Representation", ISC 2007, pp.390~406 (2007)
- "Efficient Comb Elliptic Curve Multiplication Methods Resistant to Power Analysis"[URL]
- "A Comb Method to Render ECC Resistant against Side Chiannel Attacks"[URL]