SPA에 안전한 Unsigned Left-to-Right 리코딩 방법

국문 초록 (Abstract)

Vuillaume-Okeya는 스칼라 모듈러 지수승 연산에서 SPA 공격에 안전한 리코딩 방법을 제안하였다. 제안한 방법은 역원 연산의 비용이 큰 RSA 또는 DSA 같은 시스템에서 효율적으로 구성 될 수 있게 비밀키의 표현을 0을 포함하지 않는 양의 디짓 셋 {1,2,…,2<SUP>w</SUP>-1} 을 이용해 리코딩 하였다. 제안된 방법은 비밀키의 최하위 비트부터 스캔하면서 리코딩하는 Right-to-Left 기법이다. 따라서 지수승 연산 전에 리코딩이 연산되고 그 결과를 저장하는 추가적인 공간이 필요하게 된다.
본 논문은 Left-to-Right 방향으로 수행하는 새로운 리코딩 방법들을 제안한다. 본 논문에서 제안하는 방법은 (1) 일반적으로 윈도우 크기가 w인 SPA에 안전한 부호가 없는 Left-to-Right 리코딩 방법이고 (2) 윈도우 크기 w=1 (즉, {1,2}로 구성된 부호가 없는 이진 표현)인 경우는 일반적인 윈도우 크기 w에 제안된 기법보다 훨씬 간단하게 변형할 수 있다. 또한 (3) 제안된 리코딩 방법은 부호가 없는 comb 방법에도 적용하여 SPA에 안전하게 수행할 수 있고, (4) 기수가 r인 경우에도 확장하여 SPA에 안전하게 대응할 수 있다. 본 논문에서 제안한 Left-to-Right 리코딩 기법들은 메모리의 제약을 받는 장비인 스마트 카드, 센서 노드에 적합하다.

다국어 초록 (Multilingual Abstract)

Vuillaume-Okeya presented unsigned recoding methods for protecting modular exponentiations against side channel attacks, which are suitable for tamper-resistant implementations of RSA or DSA which does not benefit from cheap inversions. The proposed method was using a signed representation with digits set {1,2,…,2<SUP>w</SUP>-1}, where 0 is absent. This recoding method was designed to be computed only from the right-to-left, i.e., it is necessary to finish the recoding and to store the recoded string before starting the left-to-right evaluation stage.
This paper describes new recoding methods for producing SPA-resistant unsigned representations which are scanned from left to right contrary to the previous ones. Our contributions are as follows; (1) SPA-resistant unsigned left-to-right recoding with general width-w , (2) special case when w=1, i.e., unsigned binary representation using the digit set {1,2}, (3) SPA-resistant unsigned left-to-right Comb recoding, (4) extension to unsigned radix-r left-to-right recoding secure against SPA. Hence, these left-to-right methods are suitable for implementing on memory limited devices such as smartcards and sensor nodes

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. 서론
• Ⅱ. 부채널 공격 및 대응 방법
• Ⅲ. 제안하는 Unsigned Left-to-Right 리코딩 알고리즘
• Ⅲ. 제안하는 Unsigned Left-to-Right 리코딩 알고리즘 확장
• Ⅴ. 결론
• 참고문헌
• 〈著者紹介〉

참고문헌 (Reference)

1 "igned Binary Representations Revisited" 123-139, 2004.

2 "Use of elliptic curves in cryptography In Advances in Cryptology- CRYPTO'85" 417-426, 1986.

3 "Timing Attacks on Implementa- tions of Diffie-Hellman, RSA, DSS, and Other Systems" 104-113, 1996.

4 "The width-wNAF method provids small memory and fast elliptic scalar multiplications secure against side channel attacks" 328-343, 2003.

5 "The advantages of elliptic curve cryptography for wireless security" 11 (11): 62-67, 2004.02

6 "Tate Pairing Implementation for Hyperelliptic Curves y2 = xp-x + d" 111-123, 2003

7 "Software Implementation of Finite Fields of Charact- eristic Three" 5 : 181-193, 2002

8 "Short Signatures from the Weil Pairing" 514-532, 2001

9 "Securing Elliptic Curve Point Multiplication against Side-Channel Attacks" 24-334, 2001.

10 "SPA Resistant Left-to-Right Integer Recodings" 345-358, 2006.

11 "Point Multiplica- tion on Ordinary Elliptic Curves over Fields of Characteristic Three," 13 (13): 485-497, 2003.

12 "Optimal Left-to-Right Binary Signed-Digit Recoding" 49 : 740-748, 2000.07

13 "More Flexible Exp- onentiation with Precomputation Advances in Cryptology-CRYPTO'94" Springer-Verlag 95-839 107, 1994.

14 "Left-to-Right Optimal Signed-Binary Representation of a Pair of Integers" 54 : 124-131, 2005.07

15 "In Mathematics of Computation" me 48 : 203-209, 1987.

16 "Improvement on Ha-Moon Randomized Ex- ponentiation Algorithm" 154-167, 2005

17 "Identity Based Encryption from the Weil Pairing" 32 (32): 586-615, 2001.

18 "High -speed implementation of an ECC-based wireless authentication protocol on an ARM microprocessor" 148 (148): 273-279, 2001.

19 "Hardware Implementa- tion of Finite Fields of Characteristic Three" 529-539, 2002

20 "Flexible Exponentiation with Resistance to Side Channel Attacks" 268-283, 2006

21 "Efficient Pairing Computation on Supersingular Abelian Varieties" 2005.

22 "Efficient GF(pm) Arithmetic Architectures for Cryptographic Applications," 158-175, 2003

23 "Differential Power Analysis" 388-397, 1999.

24 "DPA Attack on the Improved Ha-Moon Algorithm" 283-291, 2006.

25 "Countermeasures for Preventing Comb Method Against SCA Attacks" 85-3439 96, 2005.

26 "Ate pairing for y2=x5-ax in Characteristic Five" 2006.

27 "Analysis and Improvement of an Authenticated Key Exchange Protocol for Sensor Networks" 9 : 970-972, 2005.11

28 "A one round protocol for tripartite Diffie-Hellman" 385-394, 2000

29 "A new method for securing elliptic scalar multiplication against side channel attacks" 289-300, 2004.