The search functionality is under construction.

IEICE TRANSACTIONS on Fundamentals

Improved Attacks on Multi-Prime RSA with Small Prime Difference

Hui ZHANG, Tsuyoshi TAKAGI

  • Full Text Views

    0

  • Cite this

Summary :

We consider some attacks on multi-prime RSA (MPRSA) with a modulus N = p1p2 . . . pr (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 smaller private exponents can be used in the MPRSA to speed up the decryption process. Our work shows that even if a private exponent is significantly beyond Hinek et al.'s bound, it still may be insecure if the prime difference Δ (Δ = pr - p1 = Nγ, supposing p1 < p2 < … < pr) is small, i.e. 0 < γ < 1/r. Specifically, by taking full advantage of prime properties, our small private exponent attack reveals that the MPRSA is insecure when $delta<1-sqrt{1+2gamma-3/r}$ (if $gammage rac{3}{2r}- rac{1+delta}{4}$) or $deltale rac{3}{r}- rac{1}{4}-2gamma$ (if $gamma < rac{3}{2r}- rac{1+delta}{4}$), where δ is the exponential of the private exponent d with base N, i.e., d = Nδ. In addition, we present a Fermat-like factoring attack which factors N efficiently when Δ < N1/r2. These proposed attacks surpass previous works (e.g. Bahig et al.'s at ICICS 2012), and are proved effective in practice.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.7 pp.1533-1541
Publication Date
2014/07/01
Publicized
Online ISSN
1745-1337
DOI
10.1587/transfun.E97.A.1533
Type of Manuscript
PAPER
Category
Cryptography and Information Security

Authors

Hui ZHANG
  Kyushu University
Tsuyoshi TAKAGI
  Kyushu University

Keyword