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...
| 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 |
| _version_ | 1825951787288363008 |
|---|---|
| author | Abubakar, Saidu Isah |
| author_facet | Abubakar, Saidu Isah |
| author_sort | Abubakar, Saidu Isah |
| collection | UPM |
| 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. |
| first_indexed | 2024-03-06T10:35:14Z |
| format | Thesis |
| id | upm.eprints-83705 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T10:35:14Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | upm.eprints-837052022-01-05T02:44:29Z http://psasir.upm.edu.my/id/eprint/83705/ Factorization strategies of N = pq and N = pʳq and relation to its decryption exponent bound 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. 2018-12 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/83705/1/FS%202019%2036%20-%20ir.pdf 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. 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 |
| title | 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_short | 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 |
| topic | Mathematics Algebra Cryptography |
| url | http://psasir.upm.edu.my/id/eprint/83705/1/FS%202019%2036%20-%20ir.pdf |
| work_keys_str_mv | AT abubakarsaiduisah factorizationstrategiesofnpqandnprqandrelationtoitsdecryptionexponentbound |