Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices
The RSA cryptosystem developed in 1978 is the earliest public-key cryptosystem most widely deployed in securing digital information. One of the security features of RSA is based on the assumption that factoring its modulus N = pq is an infeasible task to be done in polynomial time. However, most...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/98640/ http://psasir.upm.edu.my/id/eprint/98640/1/IPM%202021%201%20-%20IR.pdf |
| _version_ | 1848862918606585856 |
|---|---|
| author | Wan Mohd Ruzai, Wan Nur Aqlili |
| author_facet | Wan Mohd Ruzai, Wan Nur Aqlili |
| author_sort | Wan Mohd Ruzai, Wan Nur Aqlili |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | The RSA cryptosystem developed in 1978 is the earliest public-key cryptosystem
most widely deployed in securing digital information. One of the security features
of RSA is based on the assumption that factoring its modulus N = pq is an infeasible
task to be done in polynomial time. However, most successful cryptanalysis (or
often called ‘attack’) against RSA and its variants are not based on this integer
factorization problem. Instead, these attacks manipulate the additional information
from the RSA parameters being used. Practically for decades, the RSA cryptosystem
has been generalized in various ways to improve its efficiency in terms of encryption
and decryption time and its security.
This study concentrates on algebraic cryptanalysis via the application of classical
methods such as the Diophantine approximation and lattice basis reduction.
Accordingly, five new cryptanalysis methods are developed to show that the modulus
N = pq of RSA and some of its variants can be factored in polynomial time under
certain specified conditions. It is expected from this study to outline several new
conditions required to design a secure RSA and its variant cryptosystems.
The main contribution of this thesis is a strategy called the ‘continuous midpoint
subdivision analysis’ (CMSA) is developed to find the vulnerabilities of RSA and
some of its variants. In the first attack, CMSA is applied upon an interval containing
the Euler’s totient function, and together with continued fractions on the RSA key
relation, the upper cryptanalytic bound of private exponent d is raised exponentially.
As in the second attack, a similar strategy is conducted upon an interval containing
the modified Euler quotient along with continued fractions on the modified key relation of some variants of RSA cryptosystems. Note that, in the third attack,
our strategy is considered for the case when the prime factors p and q are of
arbitrary bit-size (i.e. the primes are said to be unbalanced primes). A new weak
RSA key equation structure that solves the factoring problem under certain specified
conditions in polynomial time is proposed in the fourth attack. This attack combines
the continued fractions and Coppersmith’s theory on finding the small solutions of
modular univariate polynomial equations. Whilst in the last attack, the k instances
of RSA moduli with a special-structured of the key equations can be factored
simultaneously in polynomial time using the lattice basis reduction technique. Note
that our cryptanalytic works extend the bound of insecure RSA decryption exponents
of some previous literature. |
| first_indexed | 2025-11-15T13:24:39Z |
| format | Thesis |
| id | upm-98640 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T13:24:39Z |
| publishDate | 2021 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-986402022-09-06T07:49:52Z http://psasir.upm.edu.my/id/eprint/98640/ Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices Wan Mohd Ruzai, Wan Nur Aqlili The RSA cryptosystem developed in 1978 is the earliest public-key cryptosystem most widely deployed in securing digital information. One of the security features of RSA is based on the assumption that factoring its modulus N = pq is an infeasible task to be done in polynomial time. However, most successful cryptanalysis (or often called ‘attack’) against RSA and its variants are not based on this integer factorization problem. Instead, these attacks manipulate the additional information from the RSA parameters being used. Practically for decades, the RSA cryptosystem has been generalized in various ways to improve its efficiency in terms of encryption and decryption time and its security. This study concentrates on algebraic cryptanalysis via the application of classical methods such as the Diophantine approximation and lattice basis reduction. Accordingly, five new cryptanalysis methods are developed to show that the modulus N = pq of RSA and some of its variants can be factored in polynomial time under certain specified conditions. It is expected from this study to outline several new conditions required to design a secure RSA and its variant cryptosystems. The main contribution of this thesis is a strategy called the ‘continuous midpoint subdivision analysis’ (CMSA) is developed to find the vulnerabilities of RSA and some of its variants. In the first attack, CMSA is applied upon an interval containing the Euler’s totient function, and together with continued fractions on the RSA key relation, the upper cryptanalytic bound of private exponent d is raised exponentially. As in the second attack, a similar strategy is conducted upon an interval containing the modified Euler quotient along with continued fractions on the modified key relation of some variants of RSA cryptosystems. Note that, in the third attack, our strategy is considered for the case when the prime factors p and q are of arbitrary bit-size (i.e. the primes are said to be unbalanced primes). A new weak RSA key equation structure that solves the factoring problem under certain specified conditions in polynomial time is proposed in the fourth attack. This attack combines the continued fractions and Coppersmith’s theory on finding the small solutions of modular univariate polynomial equations. Whilst in the last attack, the k instances of RSA moduli with a special-structured of the key equations can be factored simultaneously in polynomial time using the lattice basis reduction technique. Note that our cryptanalytic works extend the bound of insecure RSA decryption exponents of some previous literature. 2021-05 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/98640/1/IPM%202021%201%20-%20IR.pdf Wan Mohd Ruzai, Wan Nur Aqlili (2021) Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices. Doctoral thesis, Universiti Putra Malaysia. Cryptography Public key cryptography Lattice theory |
| spellingShingle | Cryptography Public key cryptography Lattice theory Wan Mohd Ruzai, Wan Nur Aqlili Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices |
| title | Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices |
| title_full | Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices |
| title_fullStr | Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices |
| title_full_unstemmed | Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices |
| title_short | Cryptanalysis of RSA and its variants using continuous midpoint subdivision analysis and lattices |
| title_sort | cryptanalysis of rsa and its variants using continuous midpoint subdivision analysis and lattices |
| topic | Cryptography Public key cryptography Lattice theory |
| url | http://psasir.upm.edu.my/id/eprint/98640/ http://psasir.upm.edu.my/id/eprint/98640/1/IPM%202021%201%20-%20IR.pdf |