Attacks on multi-prime RSA with small prime difference

Hui Zhang, Tsuyoshi Takagi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)


We consider some attacks on multi-prime RSA (MPRSA) with a modulus N = p1 (r ≥ 3). It is believed that the small private exponent attack on the MPRSA is less effective than that on RSA (see Hinek et al.'s work at SAC 2003), which means that one can use a smaller private exponent in the MPRSA than that in the original RSA. However, our attacks show that private exponents which are significantly beyond Hinek's bound may be insecure when the prime difference Δ (Δ = pr - p1 = Nγ, 0 < γ < 1/r, suppose p 1 < p2 <⋯< pr) is small. By exploring the relation between φ(N) and its upper bound, our proposed small private exponent attack can make full use of the benefit brought by small prime difference. It is shown that the MPRSA is insecure when δ < 1-√1+γ-2/r, where δ is the exponential of the private exponent d with base N, i.e., d = Nδ. This result is a perfect extension of the best known small private exponent attack. We also present a Fermat-like factoring attack on the MPRSA which can directly factor the modulus N when Δ < N1/r2. These results surpass those of Bahig et al. (ICICS 2012) and the attacks are experimentally proved effective in practice.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 18th Australasian Conference, ACISP 2013, Proceedings
Number of pages16
Publication statusPublished - 2013
Event18th Australasian Conference on Information Security and Privacy, ACISP 2013 - Brisbane, QLD, Australia
Duration: Jul 1 2013Jul 3 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7959 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other18th Australasian Conference on Information Security and Privacy, ACISP 2013
CityBrisbane, QLD

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Attacks on multi-prime RSA with small prime difference'. Together they form a unique fingerprint.

Cite this