New Attacks on RSA with Modulus N = p2q Using Continued Fractions

3rd International Conference on Science & Engineering in Mathematics, Chemistry and Physics 2015

数学;化学;物理学

Asbullah, M.A.^1 ; Ariffin, M.R.K.^2

Al-Kindi Cryptography Research Laboratory, Institute for Mathematical Research, Universiti Putra Malaysia, Serdang

43400, Malaysia^1

Department of Mathematics, Faculty of Sciences, Universiti Putra Malaysia, Serdang

43400, Malaysia^2

关键词: Continued fraction;    Continued fraction expansion;    Key equation;    Polynomial-time;    Positive integers;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/622/1/012019/pdf
DOI  :  10.1088/1742-6596/622/1/012019

来源: IOP

【 摘 要 】

In this paper, we propose two new attacks on RSA with modulus N = p2q using continued fractions. Our first attack is based on the RSA key equation ed - φ(N)k = 1 where φ(N) = p(p - 1)(q - 1). Assuming that and , we show that can be recovered among the convergents of the continued fraction expansion of . Our second attack is based on the equation eX - (N - (ap2+ bq2)) Y = Z where a,b are positive integers satisfying gcd(a,b) = 1, |ap2- bq2| 1/2and ap2+ bq2= N2/3+αwith 0 2q in polynomial time.