TY - GEN

T1 - Attacks on multi-prime RSA with small prime difference

AU - Zhang, Hui

AU - Takagi, Tsuyoshi

PY - 2013

Y1 - 2013

N2 - We consider some attacks on multi-prime RSA (MPRSA) with a modulus N = p1 p2...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 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.

AB - We consider some attacks on multi-prime RSA (MPRSA) with a modulus N = p1 p2...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 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.

UR - http://www.scopus.com/inward/record.url?scp=84884490272&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84884490272&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39059-3_4

DO - 10.1007/978-3-642-39059-3_4

M3 - Conference contribution

AN - SCOPUS:84884490272

SN - 9783642390586

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 41

EP - 56

BT - Information Security and Privacy - 18th Australasian Conference, ACISP 2013, Proceedings

T2 - 18th Australasian Conference on Information Security and Privacy, ACISP 2013

Y2 - 1 July 2013 through 3 July 2013

ER -