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

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 et al.’s scheme. In this paper, we introduce a family of RSA-like encryption schemes that uses the key equation \(ed - k (p^n-1)(q^n-1) = 1\) , where \(n>0\) is an integer. Then, we show that regardless of the choice of n, there exists an attack based on continued fractions that recovers the secret exponent.