Paper 2015/1137

Improved Factoring Attacks on Multi-Prime RSA with Small Prime Difference

Mengce Zheng, Noboru Kunihiro, and Honggang Hu

Abstract

In this paper, we study the security of multi-prime RSA with small prime difference and propose two improved factoring attacks. The modulus involved in this variant is the product of r distinct prime factors of the same bit-size. Zhang and Takagi (ACISP 2013) showed a Fermat-like factoring attack on multi-prime RSA. In order to improve the previous result, we gather more information about the prime factors to derive r simultaneous modular equations. The first attack is to combine all the equations and solve one multivariate equation by generic lattice approaches. Since the equation form is similar to multi-prime Phi-hiding problem, we propose the second attack by applying the optimal linearization technique. We also show that our attacks can achieve better bounds in the experiments.

Note: We remove the latex from the abstract on the web to make it easy to read.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ACISP 2017
Keywords
CryptanalysisMulti-prime RSASmall prime differenceFactoring attackLattice-based linearization technique
Contact author(s)
mengce zheng @ gmail com
History
2018-03-18: last of 2 revisions
2015-11-26: received
See all versions
Short URL
https://ia.cr/2015/1137
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1137,
      author = {Mengce Zheng and Noboru Kunihiro and Honggang Hu},
      title = {Improved Factoring Attacks on Multi-Prime RSA with Small Prime Difference},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1137},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1137}},
      url = {https://eprint.iacr.org/2015/1137}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.