A security analysis of two classes of RSA-like cryptosystems

Abstract

Let N=pqN=pq be the product of two balanced prime numbers pp and qq. In Elkamchouchi et al. (Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers. In: ICCS 2002. vol. 1. IEEE Computer Society; 2002. p. 91–5.) introduced an Rivest-Shamir-Adleman (RSA)-like cryptosystem that uses the key equation ed−k(p2−1)(q2−1)=1ed-k\left({p}^{2}-1)\left({q}^{2}-1)=1, instead of the classical RSA key equation ed−k(p−1)(q−1)=1ed-k\left(p-1)\left(q-1)=1. Another variant of RSA, presented in Murru and Saettone (A novel RSA-like cryptosystem based on a generalization of the Rédei rational functions. In: NuTMiC 2017. vol. 10737 of Lecture Notes in Computer Science. Springer; 2017. p. 91–103), uses the key equation ed−k(p2+p+1)(q2+q+1)=1ed-k\left({p}^{2}+p+1)\left({q}^{2}+q+1)=1. Despite the authors’ claims of enhanced security, both schemes remain vulnerable to adaptations of common RSA attacks. Let nn be an integer. This article proposes two families of RSA-like encryption schemes: one employs the key equation ed−k(pn−1)(qn−1)=1ed-k\left({p}^{n}-1)\left({q}^{n}-1)=1 for n>0n\gt 0, while the other uses ed−k[(pn−1)(qn−1)]⁄[(p−1)(q−1)]=1ed-k\left[\left({p}^{n}-1)\left({q}^{n}-1)]/\left[\left(p-1)\left(q-1)]=1 for n>1n\gt 1. Note that we remove the conventional assumption of primes having equal bit sizes. In this scenario, we show that regardless of the choice of nn, 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.

Keywords

• continued fractions
• small private key attack
• rsa
• 94a60
• 11a55