Extending jochemsz-may analytical strategies upon integer factorization problem

The first public key cryptosystem namely RSA has been used extensively throughout the world since its invention in 1978. Since then, cryptanalytic research on this cryptosystem began with the purpose to enhance its security. In this thesis, we present three analytical attacks on the modulus N = p 2q by utilizing Jochemsz-May strategy. We show that the modulus can be factored if the elements in the cryptosystem satisfy our conditions. For the first attack, we utilize the modulus N = p 2q where p and q are large balanced primes. Suppose there exists e ∈ Z + satisfying gcd(e,φ(N)) = 1 where φ(N) = p(p−1)(q−1) and d < N δ be its corresponding private exponent such that d ≡ e −1 mod φ(N). From ed − kφ(N) = 1, by utilizing the extended strategy of Jochemsz and May, our attack works when the primes share a known amount of Least Significant Bits (LSBs). This is achievable since we obtain the small roots of our constructed integer polynomial that consequently leads to the factorization of N. More specifically we show that N can be factored when the bound δ < 2 3 + 3 2 α − 1 2 γ. Our attack enhances the bound of some former attacks upon N = p 2q. Next, we describe a cryptanalytic study on RSA with the modulus N = p 2q with the existence of two key equations. Let e1, e2 < N γ be the integers such that d1,d2 < N δ be their multiplicative inverses. Based on two key equations e1d1 − k1φ(N) = 1 and e2d2 − k2φ(N) = 1 where φ(N) = p(p − 1)(q − 1), our attack works when the primes share a known amount of LSBs and the private exponents share an amount of Most Significant Bits (MSBs). We apply the extended strategy of Jochemsz and May to find the small roots of a polynomial and show that if δ < 11 10 + 9 4 α − 1 2 β − 1 2 γ − 1 30 p 180γ +990α −180β +64, then N can be factored. Our attack improves the bounds of some previously proposed attacks that makes the RSA vulnerable. Lastly, we present an attack on RSA with the modulus N = p 2q. Let e < N γ be the public exponent satisfying the equation ed − k(N − (ap) 2 − apbq + ap) = 1 where a b is an unknown approximation of q p . Our attack is applicable when some amount of LSBs of ap and bq are known. We use the extended strategy of Jochemsz and May as our main method to find the small roots of our polynomial and show that the modulus N can be factored if δ < 91 135 + 29 45β − 44 45α − 2 3 γ − 2 135 p 2(3α −3β +1)(−84α +45γ +39β −28). In this final segment of our research, we conclude that our approach via extending Jochemsz and May analytical strategies does not improve previous bounds. Hence, answers existing unknown outcome on this matter.

Text IPM 2021 3 UPMIR.pdf Download (1MB)

Actions (login required)

View Item