
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Improved Attacks on MultiPrime RSA with Small Prime Difference
Hui ZHANG Tsuyoshi TAKAGI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97A
No.7
pp.15331541 Publication Date: 2014/07/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E97.A.1533
Type of Manuscript: PAPER Category: Cryptography and Information Security Keyword: cryptanalysis, multiprime RSA, small prime difference, lattice reduction,
Full Text: PDF(820.4KB) >>Buy this Article
Summary:
We consider some attacks on multiprime RSA (MPRSA) with a modulus N = p_{1}p_{2} . . . 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_{1} = N^{γ}, supposing p_{1} < p_{2} < … < 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<1sqrt{1+2gamma3/r}$ (if $gammagerac{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 Fermatlike factoring attack which factors N efficiently when Δ < N^{1/r2}. These proposed attacks surpass previous works (e.g. Bahig et al.'s at ICICS 2012), and are proved effective in practice.

