Paper 2015/642

A New Partial Key Exposure Attack on Multi-power RSA

Muhammed F. Esgin, Mehmet S. Kiraz, and Osmanbey Uzunkol

Abstract

An important attack on multi-power RSA ($N=p^rq$) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that $N$ can be factored efficiently for $r=2$ with private exponent $d$ satisfying $d<N^{0.395}$. In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith's algorithm and Gröbner basis computation. Our attack works for all multi-power RSA exponents $e$ (resp. $d$) when the exponent $d$ (resp. $e$) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of $e$. For practical validation of our attack, we demonstrate several computer algebra experiments.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Conference on Algebraic Informatics (CAI) 2015
Keywords
Multi-power RSAInteger factorizationPartial key exposureCoppersmith's methodSmall roots of polynomials
Contact author(s)
muhammedgs @ gmail com
History
2015-06-30: received
Short URL
https://ia.cr/2015/642
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/642,
      author = {Muhammed F.  Esgin and Mehmet S.  Kiraz and Osmanbey Uzunkol},
      title = {A New Partial Key Exposure Attack on Multi-power RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2015/642},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/642}},
      url = {https://eprint.iacr.org/2015/642}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.