Paper 2023/1356

Small Private Key Attack Against a Family of RSA-like Cryptosystems

Abstract

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. Elkamchouchi, Elshenawy and Shaban presented in 2002 an interesting 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$. The authors claimed that their scheme is more secure than RSA. Unfortunately, the common attacks developed against RSA can be adapted for Elkamchouchi \emph{et al.}'s scheme. In this paper, we introduce a family of RSA-like encryption schemes that uses the key equation $$, where $$ is an integer. Then, we show that regardless of the choice of $$, there exists an attack based on continued fractions that recovers the secret exponent.