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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| 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!
|
| Summary: | 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. |
|---|