Partial Exposure Attacks Against a Family of RSA-like Cryptosystems

An RSA generalization using complex integers was introduced by Elkamchouchi, Elshenawy and Shaban in 2002. This scheme was further extended by Cotan and Teșeleanu to Galois fields of order n≥1. In this generalized framework, the key equation is ed−k(pn−1)(qn−1)=1, where p and q are prime numbers. Note that the classical RSA and Elkamchouchi et al.’s key equations are special cases, namely, when n=1 and n=2. In addition to introducing this generic family, Cotan and Teșeleanu described a continued fractions attack capable of recovering the secret key d if d<N0.25n. This bound was later improved by Teșeleanu using a lattice-based method. In this paper, we explore other lattice attacks that could lead to factoring the modulus N=pq, namely, we propose a series of partial exposure attacks that can aid an adversary in breaking this family of cryptosystems if certain conditions hold.