Collision-Based Power Attack for RSA with Small Public Exponent

Kouichi ITOH  Dai YAMAMOTO  Jun YAJIMA  Wakaha OGATA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.5   pp.897-908
Publication Date: 2009/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.897
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)
Category: Implementation Issues
Keyword: 
power attack,  collision attack,  SPA,  DPA,  RSA,  window method,  countermeasure,  

Full Text: PDF(748.3KB)>>
Buy this Article




Summary: 
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+ riφ(N) to calculate cd'i (mod N), and another is a technique using di,1 = d/ri and di,2 =(d (mod ri)) to calculate (cdi,1)ri cdi,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.