Paper 2024/1263

A Security Analysis of Two Classes of RSA-like Cryptosystems

Abstract

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2002, Elkamchouchi, Elshenawy and Shaban introduced an RSA-like cryptosystem that uses the key equation $ed-k(p^2-1)(q^2-1)=1$, instead of the classical RSA key equation $ed-k(p-1)(q-1)=1$. Another variant of RSA, presented in 2017 by Murru and Saettone, uses the key equation $ed-k(p^2+p+1)(q^2+q+1)=1$. Despite the authors' claims of enhanced security, both schemes remain vulnerable to adaptations of common RSA attacks. Let $n$ be an integer. This paper proposes two families of RSA-like encryption schemes: one employs the key equation $$ for $$, while the other uses $$ for $$. Note that we remove the conventional assumption of primes having equal bit sizes. In this scenario, we show that regardless of the choice of $$, continued fraction-based attacks can still recover the secret exponent. Additionally, this work fills a gap in the literature by establishing an equivalent of Wiener's attack when the primes do not have the same bit size.