Citation
Abubakar, Saidu Isah
(2018)
Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound.
Doctoral thesis, Universiti Putra Malaysia.
Abstract
The major RSA underlying security problems rely on the difficulty of factoring a very large composite integer N into its two nontrivial prime factors of p and q in polynomial time, the ability to solve a given Diophantine equation ed = 1 + kφ (N) where only
the public key e is known and the parameters d, k and φ (N) are un known and finally the failure of an adversary to compute the decryption key d from the public key pair (e, N). This thesis develops three new strategies for the factorization of
RSA modulus N = pq through analyzing small prime difference satisfying inequalities b2 p
− a2q < Nγ , bi p − a jq < Nγ and b j p − a jq < for...
This research work also focuses on successful factorization of t RSA moduli Ns = psqs. By using
good approximation of φ (N) and generalized key equations of the form esd ksφ (Ns) =
1, esds kφ (Ns) = 1, esd kφ (Ns) = zs and esds kφ (Ns) = zs for s = 1, 2, . . . ,
t. This method leads to simultaneous factoring of t RSA moduli Ns = psqs in polynomial time
using simultaneous Diophantine approximation and lattice basis reduction techniques for
unknown integers d, ds, k, ks, and zs.
Furthermore, this research work develops four successful cryptanalysis attacks of fac toring t
prime power moduli Ns = prqs by transforming equations esd ksφ (Ns) = 1, esds kφ (Ns) = 1,
esd kφ (Ns) = zs and esds kφ (Ns) = zs for s = 1, 2, . . . , t into simultaneous
Diophantine problem by using LLL algorithm to get the reduced basis (d, ks) and (ds, k) which can
be used to calculate unknown parameters φ (N) and later simultaneously factor (ps, qs) in
polynomial time. This research work also makes com parisons of its findings with existing
literature. The bound of this research work was found to be better than the short decryption
exponent bound within some of the existing literature.
Download File
Additional Metadata
Item Type: 
Thesis
(Doctoral)

Subject: 
Mathematics 
Subject: 
Algebra 
Subject: 
Cryptography 
Call Number: 
FS 2019 36 
Chairman Supervisor: 
Associate Professor Muhammad Rezal Kamel Ariffin, PhD 
Divisions: 
Faculty of Science 
Depositing User: 
Ms. Nur Faseha Mohd Kadim

Date Deposited: 
02 Nov 2020 13:26 
Last Modified: 
05 Jan 2022 02:44 
URI: 
http://psasir.upm.edu.my/id/eprint/83705 
Statistic Details: 
View Download Statistic 
Actions (login required)

View Item 