Paper 2015/1137 Original: eprint.iacr.org/2015/1137 ↗
Improved Factoring Attacks on Multi-Prime RSA with Small Prime Difference
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2018-03-18: last updated
- 2015-11-26: published
- Short URL
- https://ia.cr/2015/1137
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2015/1137}
}