Improved Attacks on Multi-Prime RSA with Small Prime Difference

Hui ZHANG; Tsuyoshi TAKAGI

doi:10.1587/transfun.E97.A.1533

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 = 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+2gamma-3/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 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.

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

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

Cite this

Copy

Hui ZHANG, Tsuyoshi TAKAGI, "Improved Attacks on Multi-Prime RSA with Small Prime Difference" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 7, pp. 1533-1541, July 2014, doi: 10.1587/transfun.E97.A.1533.
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+2gamma-3/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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1533/_p

Copy

@ARTICLE{e97-a_7_1533,
author={Hui ZHANG, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved Attacks on Multi-Prime RSA with Small Prime Difference},
year={2014},
volume={E97-A},
number={7},
pages={1533-1541},
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+2gamma-3/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 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.},
keywords={},
doi={10.1587/transfun.E97.A.1533},
ISSN={1745-1337},
month={July},}

Copy

TY - JOUR
TI - Improved Attacks on Multi-Prime RSA with Small Prime Difference
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1533
EP - 1541
AU - Hui ZHANG
AU - Tsuyoshi TAKAGI
PY - 2014
DO - 10.1587/transfun.E97.A.1533
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2014
AB - 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+2gamma-3/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 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.
ER -