Improved Attacks on Multi-Prime RSA with Small Prime Difference

• ZHANG Hui

  Graduate School of Mathematics, Kyushu University

• TAKAGI Tsuyoshi

  Institute of Mathematics for Industry, Kyushu University

Abstract

We consider some attacks on multi-prime RSA (MPRSA) with a modulus N = p₁p₂ . . . p_r (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 Δ (Δ = p_r - p₁ = N^γ, supposing p₁ < p₂ < … < p_r) 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+2\gamma-3/r}$ (if $\gamma\ge\frac{3}{2r}-\frac{1+\delta}{4}$) or $\delta\le \frac{3}{r}-\frac{1}{4}-2\gamma$ (if $\gamma < \frac{3}{2r}-\frac{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 Δ < N^1/r². These proposed attacks surpass previous works (e.g. Bahig et al.'s at ICICS 2012), and are proved effective in practice.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97.A (7), 1533-1541, 2014

  The Institute of Electronics, Information and Communication Engineers

Keywords

• cryptanalysis
• multi-prime RSA
• small prime difference
• lattice reduction

Details

• CRID: 1390001206312466944
• NII Article ID: 130004519181
• DOI: 10.1587/transfun.e97.a.1533
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E97.A/7/E97.A_1533/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed