Practical application of lattice basis reduction algorithm to side-channel analysis on (EC)DSA

作     者：Takashima, Katsuyuki 

作者机构：Mitsubishi Electr Corp Informat Technol R&D Ctr Kamakura Kanagawa 2478501 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (IEICE Trans Fund Electron Commun Comput Sci)

年 卷 期：2006年第E89A卷第5期

页      面：1255-1262页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：(EC) DSA side-channel analysis (attack) window method lattice basis reduction algorithm 

摘      要：In this paper. we will report practical modifications of the side-channel analysis to (EQDSA [1], [2], [5], [34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn t been effective when the size q of a cyclic group used in (EQDSA is 160 bit long and the window size w 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w = 4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EQDSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.