Citation
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.
Abstract
The RSA cryptosystem developed in 1978 is the earliest publickey 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 bitsize (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 specialstructured 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.
Download File
Additional Metadata
Actions (login required)

View Item 