Malaysian Journal of Mathematical Sciences, August 2017, Vol. 11(S)
Special Issue: The 5th International Cryptology and Information Security Conference (New Ideas in Cryptology)
New Vulnerability of RSA Modulus Type \(N=p^2q\)
Rahman, N. N. A. R. and Ariffin, M. R. K.
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
This paper proposes new attacks on modulus of type \(N=p^2q\). Given \(k\) moduli of the form \(N_{i}=p_{i}^{2}q_{i}\) for \(k \geq 2\) and \(i=1,...,k\), the attack works when \(k\) public keys \((N_{i}, e_{i})\) are such that there exist \(k\) relations of the shape \(e_{i}x-N_{i}y_{i}=z_{i}-(ap_{i}^{2}+bq_{i}^{2})y_{i}\) or of the shape \(e_{i}x_{i}-N_{i}y=z_{i}-(ap_{i}^{2}+bq_{i}^{2})y\) where the parameters \(x\), \(x_i\), \(y\), \(y_i\) and \(z_i\) are suitably small in terms of the prime factors of the moduli. The proposed attacks utilizing the LLL algorithm enables one to factor the \(k\) moduli \(N_i\) simultaneously.
Keywords: Factorization, modulus \(N=p^2q\), LLL algorithm, Simultaneous diophantine approximations
