Malaysian Journal of Mathematical Sciences, December 2021, Vol. 15(S)
Special Topics: New Ideas in Cryptology
An Attack on \(N=p^{2}q\) with Partially Known Bits on the Multiple of the Prime Factors
Ruzai,W. N. A., Adenan, N. N. H., Ariffin, M. R. K., Ghaffar, A. H. A., and Johari, M. A. M.
Corresponding Email: [email protected]
Received date: 17 June 2021
Accepted date: 7 October 2021
Abstract:
This paper presents a cryptanalytic study upon the modulus \(N=p^{2}q\) consisting of two large primes that are in the same-bit size. In this work, we show that the modulus \(N\) is factorable if \(e\) satisfies the Diophantine equation of the form \(ed-k(N-(ap)^{2}-apbq+ap)=1\) where \(\frac{a}{b}\) is an unknown approximation of \(\frac{q}{p}\). Our attack is feasible when some amount of Least Significant Bits
(LSBs) of \(ap\) and \(bq\) is known. By utilising the Jochemsz-May strategy as our main method, we manage to prove that the modulus \(N\) can be factored in polynomial time under certain specified conditions.
Keywords: partial-key exposure attack; integer factorization problem; Jochemsz-May strategy; least significant bits
