Collision-Based Power Attack for RSA with Small Public Exponent

• ITOH Kouichi

  FUJITSU LABORATORIES Ltd. Tokyo Institute of Technology

• YAMAMOTO Dai

  FUJITSU LABORATORIES Ltd.

• YAJIMA Jun

  FUJITSU LABORATORIES Ltd.

• OGATA Wakaha

  Tokyo Institute of Technology

Abstract

This paper proposes a new side channel attack to RSA cryptography. Our target is an implementation with a combination of countermeasures. These are an SPA countermeasure by m-ary method and a DPA countermeasure by randomizing exponent techniques. Here, randomizing exponent techniques shows two DPA countermeasures to randomize the secret exponent d. One is an exponent randomizing technique using d'_i = d + r_iφ(N) to calculate c^d'_i (mod N), and another is a technique using d_i,1 = ⌊ d/r_i ⌋ and d_i,2 = (d mod r_i)) to calculate (c^d_i,1)^r_i × c^d_i,2 (mod N). Using the combination of countermeasures, it was supposed that the implementation is secure against power attack. However, we firstly show the result to successfully attack the implementation of the combination of these countermeasures. We performed the experiment of this search on a PC, and complete d has been successfully revealed less than 10 hours for both attacks.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E92-D (5), 897-908, 2009

  The Institute of Electronics, Information and Communication Engineers

Keywords

• power attack
• collision attack
• SPA
• DPA
• RSA
• window method
• countermeasure

Details

• CRID: 1390282679354678016
• NII Article ID: 10026809071
• NII Book ID: AA10826272
• DOI: 10.1587/transinf.e92.d.897
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E92.D/5/E92.D_5_897/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed