Collision-Based Power Attack for RSA with Small Public Exponent

Kouichi ITOH; Dai YAMAMOTO; Jun YAJIMA; Wakaha OGATA

doi:10.1587/transinf.E92.D.897

Collision-Based Power Attack for RSA with Small Public Exponent

Kouichi ITOH, Dai YAMAMOTO, Jun YAJIMA, Wakaha OGATA

Full Text Views

0

Cite this

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+ 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.

Publication: IEICE TRANSACTIONS on Information Vol.E92-D No.5 pp.897-908

Publication Date: 2009/05/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E92.D.897

Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)

Category: Implementation Issues

Cite this

Copy

Kouichi ITOH, Dai YAMAMOTO, Jun YAJIMA, Wakaha OGATA, "Collision-Based Power Attack for RSA with Small Public Exponent" in IEICE TRANSACTIONS on Information, vol. E92-D, no. 5, pp. 897-908, May 2009, doi: 10.1587/transinf.E92.D.897.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.897/_p

Copy

@ARTICLE{e92-d_5_897,
author={Kouichi ITOH, Dai YAMAMOTO, Jun YAJIMA, Wakaha OGATA, },
journal={IEICE TRANSACTIONS on Information},
title={Collision-Based Power Attack for RSA with Small Public Exponent},
year={2009},
volume={E92-D},
number={5},
pages={897-908},
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.},
keywords={},
doi={10.1587/transinf.E92.D.897},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - Collision-Based Power Attack for RSA with Small Public Exponent
T2 - IEICE TRANSACTIONS on Information
SP - 897
EP - 908
AU - Kouichi ITOH
AU - Dai YAMAMOTO
AU - Jun YAJIMA
AU - Wakaha OGATA
PY - 2009
DO - 10.1587/transinf.E92.D.897
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2009
AB - 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.
ER -