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...

Full description

Saved in:

Bibliographic Details
Main Author:	Adenan, Nurul Nur Hanisah
Format:	Thesis
Language:	English
Published:	2021
Subjects:	Integral equations - Asymptotic theory Factorization (Mathematics)
Online Access:	http://psasir.upm.edu.my/id/eprint/98848/1/IPM%202021%203%20UPMIR.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.98848
record_format	uketd_dc
spelling	my-upm-ir.988482022-10-12T01:51:20Z Extending jochemsz-may analytical strategies upon integer factorization problem 2021-02 Adenan, Nurul Nur Hanisah 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. Integral equations - Asymptotic theory Factorization (Mathematics) 2021-02 Thesis http://psasir.upm.edu.my/id/eprint/98848/ http://psasir.upm.edu.my/id/eprint/98848/1/IPM%202021%203%20UPMIR.pdf text en public masters Universiti Putra Malaysia Integral equations - Asymptotic theory Factorization (Mathematics) Kamel Ariffin, Muhammad Rezal
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English
advisor	Kamel Ariffin, Muhammad Rezal
topic	Integral equations - Asymptotic theory Factorization (Mathematics)
spellingShingle	Integral equations - Asymptotic theory Factorization (Mathematics) Adenan, Nurul Nur Hanisah Extending jochemsz-may analytical strategies upon integer factorization problem
description	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.
format	Thesis
qualification_level	Master's degree
author	Adenan, Nurul Nur Hanisah
author_facet	Adenan, Nurul Nur Hanisah
author_sort	Adenan, Nurul Nur Hanisah
title	Extending jochemsz-may analytical strategies upon integer factorization problem
title_short	Extending jochemsz-may analytical strategies upon integer factorization problem
title_full	Extending jochemsz-may analytical strategies upon integer factorization problem
title_fullStr	Extending jochemsz-may analytical strategies upon integer factorization problem
title_full_unstemmed	Extending jochemsz-may analytical strategies upon integer factorization problem
title_sort	extending jochemsz-may analytical strategies upon integer factorization problem
granting_institution	Universiti Putra Malaysia
publishDate	2021
url	http://psasir.upm.edu.my/id/eprint/98848/1/IPM%202021%203%20UPMIR.pdf
_version_	1747813899315445760

Extending jochemsz-may analytical strategies upon integer factorization problem

Similar Items