Cryptology ePrint Archive: Report 2015/642

A New Partial Key Exposure Attack on Multi-power RSA

Muhammed F. Esgin and 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\"obner 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.

Category / Keywords: public-key cryptography / Multi-power RSA, Integer factorization, Partial key exposure, Coppersmith's method, Small roots of polynomials

Original Publication (with minor differences): Conference on Algebraic Informatics (CAI) 2015

Date: received 29 Jun 2015

Contact author: muhammedgs at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150630:200529 (All versions of this report)

Short URL: ia.cr/2015/642

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]