Paper 2024/1313

A Lattice Attack Against a Family 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 interesting RSA-like cryptosystem that, unlike the classical RSA key equation $ed-k(p-1)(q-1)=1$, uses the key equation $ed-k(p^2-1)(q^2-1)=1$. The scheme was further extended by Cotan and Te\c seleanu to a variant that uses the key equation $ed-k(p^n-1)(q^n-1)=1$, where $n\ge 1$. Furthermore, they provide a continued fractions attack that recovers the secret key $d$ if $d<N^{0.25n}$. In this paper we improve this bound using a lattice based method. Moreover, our method also leads to the factorisation of the modulus $N$, while the continued fractions one does not (except for $n=1,2,3,4$).