Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/83705/1/FS%202019%2036%20-%20ir.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
my-upm-ir.83705 |
|---|---|
| record_format |
uketd_dc |
| spelling |
my-upm-ir.837052022-01-05T02:44:29Z Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound 2018-12 Abubakar, Saidu Isah 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. Mathematics Algebra Cryptography 2018-12 Thesis http://psasir.upm.edu.my/id/eprint/83705/ http://psasir.upm.edu.my/id/eprint/83705/1/FS%202019%2036%20-%20ir.pdf text en public doctoral Universiti Putra Malaysia Mathematics Algebra Cryptography Kamel Ariffin, Muhammad Rezal |
| institution |
Universiti Putra Malaysia |
| collection |
PSAS Institutional Repository |
| language |
English |
| advisor |
Kamel Ariffin, Muhammad Rezal |
| topic |
Mathematics Algebra Cryptography |
| spellingShingle |
Mathematics Algebra Cryptography Abubakar, Saidu Isah Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound |
| description |
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. |
| format |
Thesis |
| qualification_level |
Doctorate |
| author |
Abubakar, Saidu Isah |
| author_facet |
Abubakar, Saidu Isah |
| author_sort |
Abubakar, Saidu Isah |
| title |
Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound |
| title_short |
Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound |
| title_full |
Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound |
| title_fullStr |
Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound |
| title_full_unstemmed |
Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound |
| title_sort |
factorization strategies of n = pq and n = pʳq and relation to its decryption exponent bound |
| granting_institution |
Universiti Putra Malaysia |
| publishDate |
2018 |
| url |
http://psasir.upm.edu.my/id/eprint/83705/1/FS%202019%2036%20-%20ir.pdf |
| _version_ |
1747813410746138624 |