1 Introduction

In 1978, Rivest, Shamir and Adleman [29] proposed one of the most popular and widely used cryptosystems, namely RSA. In the standard RSA encryption scheme, we work modulo an integer N, where N is the product of two large prime numbers p and q. Let \(\varphi (N) = (p-1)(q-1)\) denote the Euler’s totient function. In order to encrypt a message \(m < N\), we simply compute \(c \equiv m^e \bmod N\), where e is generated a priori such that \(\gcd (e, \varphi (N)) = 1\). To decrypt, one needs to compute \(m \equiv c^d \bmod N\), where \(d \equiv e^{-1} \bmod \varphi (N)\). Note that (N, e) are public, while (p, q, d) are kept secret. In the standard version of RSA, also called balanced RSA, p and q are of the same bit-size such that \(q < p < 2q\). In this paper, we only consider the balanced RSA scheme and its variants.

In 2002, Elkamchouchi, Elshenawy and Shaban [15] extend the classical RSA scheme to the ring of Gaussian integers modulo N. A Gaussian integer modulo N is a number of the form \(a+bi\), where \(a,b \in \mathbb {Z}_N\) and \(i^2=-1\). Let \(\mathbb {Z}_N[i]\) denote the set of all Gaussian integers modulo N and let \(\phi (N) = |\mathbb {Z}_N^*[i]| = (p^2-1)(q^2-1)\). To set up the public exponent, in this case we must have \(\gcd (e, \phi (N)) =1\). The corresponding private exponent is \(d \equiv e^{-1} \bmod \phi (N)\). In order to encrypt a message \(m \in \mathbb {Z}_N[i]\), we simply compute \(c \equiv m^e \bmod N\) and to decrypt it \(m \equiv c^d \bmod N\). Note that the exponentiations are computed in the ring \(\mathbb {Z}_N[i]\). The authors of [15] claim that this extension provides more security than that of the classical RSA. In the following paragraphs we present a series of common attacks that work for both types of cryptosystems.

Small Private Key Attacks. In order to decrease decryption time, one may prefer to use a smaller d. Wiener showed in [33] that this is not always a good idea. More exactly, in the case of RSA, if \(d < N^{0.25}/3\), then one can retrieve d from the continued fraction expansion of e/N, and thus factor N. Using a result developed by Coppersmith [12], Boneh and Durfee [5] improved Wiener’s bound to \(N^{0.292}\). Later on, Herrmann and May [19] obtain the same bound, but using simpler techniques. A different approach was taken by Blömer and May [3], whom generalized Wiener’s attack. More precisely, they showed that if there exist three integers x, y, z such that \(ex-y\varphi (N)=z\), \(x < N^{0.25}/3\) and \(|z| < |exN^{-0.75}|\), then the factorisation of N can be recovered. When an approximation of p is known such that \(|p - p_0| < N^\delta /8\) and \(\delta < 0.5\), Nassr, Anwar and Bahig [25] present a method based on continued fractions for recovering d when \(d < N^{(1-\delta )/2}\).

In the case of Elkamchouchi et al., a small private key attack based on continued fractions was presented in [7]. Using lattice reduction, the attack was improved in [28, 34]. The authors obtained a bound of \(d < N^{0.585}\). A generalization of the attack presented in [7] to unbalanced prime numbers was presented in [9]. Considering the generic equation \(ex-y\phi (N)=z\), the authors of [8] describe a method for factoring N when \(xy < 2N -4\sqrt{2} N^{0.75}\) and \(|z| < (p-q)N^{0.25}y\). An extension of the previous attack was proposed in [27].

Multiple Private Keys Attack. Let \(\ell > 0\) be an integer and \(i \in [1, \ell ]\). When multiple large public keys \(e_i \simeq N^{\alpha }\) are used with the same modulus N, Howgrave-Graham and Seifert [20] describe an attack against RSA that recovers the corresponding small private exponents \(d_i \simeq N^\beta \). This attack was later improved by Sarkar and Maitra [30], Aono [1] and Takayasu and Kunihiro [31]. The best known bound [31] is \(\beta < 1 - \sqrt{2/(3\ell +1)}\). Remark that when \(\ell = 1\) we obtain the Boneh-Durfee bound.

The multiple private keys attack against the Elkamchouchi et al. cryptosystem was studied by Zheng, Kunihiro and Hu [34]. The bound obtained by the authors is \(\beta < 2 - 2\sqrt{2/(3\ell +1)}\) and it is twice the bound obtained by Takayasu and Kunihiro [31]. Note that when \(\ell = 1\) the bound is equal to 0.585.

Partial Key Exposure Attack. In this type of attack, the most or least significant bits of the private exponent d are known. Starting from these, an adversary can recover the entire RSA private key using the techniques presented by Boneh, Durfee and Frankel in [6]. The attack was later improved by Blömer and May [2], Ernst et al. [16] and Takayasu and Kunihiro [32]. The best known bound [32] is \(\beta < (\gamma +2-\sqrt{2-3\gamma ^2})/2\), where the attacker knows \(N^\gamma \) leaked bits.

Zheng, Kunihiro and Hu [34] describe a partial exposure attack that works in the case of the Elkamchouchi et al. scheme. The bound they achieve is \(\beta < (3\gamma +7-2\sqrt{3\gamma +7})/3\). When \(\gamma = 0\), the bound is close to 0.569, and thus it remains an open problem how to optimize it.

Small Prime Difference Attack. When the prime difference \(|p-q|\) is small and certain conditions hold, de Weger [14] described two methods to recover d, one based on continued fractions and one on lattice reduction. These methods were further extended by Maitra and Sakar [22, 23] to \(|\rho q - p|\), where \(1 \le \rho \le 2\). Lastly, Chen, Hsueh and Lin generalize them further to \(|\rho q - \epsilon p|\), where \(\rho \) and \(\epsilon \) have certain properties. The continued fraction method is additionally improved by Ariffin et al. [21].

The small prime difference attack against the Elkamchouchi et al. public key encryption scheme was studied in [11]. Note that when the common condition \(|p-q| < N^{0.5}\) holds, their bound leads to the small private key bound \(d < N^{0.585}\).

Related Work. It is worth noting that our current undertaking shares similarities with a prior work of ours [13], where we explored a cryptographic system closely related to our own. Specifically, we studied the implications of generalizing the Murru-Saettone cryptosystem [24], and the effect of using continued fractions to recover the private key.

1.1 Our Contributions

We first remark that the rings \(Z_p = \mathbb {Z}_p[t]/(t+1) = GF(p)\) and \(Z_p[i] = \mathbb {Z}_p[t]/(t^2+1) = GF(p^2)\), where GF stands for Galois field. Therefore, we can rethink the RSA scheme as working in the \(GF(p)\times GF(q)\) group instead of \(\mathbb {Z}_N\). Also, that the Elkamchouchi et al. scheme is an extension to \(GF(p^2)\times GF(q^2)\) instead of \(Z_N[i]\). This leads to a natural generalization of RSA to \(GF(p^n)\times GF(q^n)\), where \(n > 1\). In this paper we introduce exactly this extension. We wanted to see if only for \(n=1\) and \(n=2\) the common attacks presented in the introduction work or this is something that happens in general. In this study we present a Wiener-type attack that works for any \(n>1\). More, precisely we prove that when \(d < N^{0.25n}\), we can recover the secret exponent regardless the value of n. Therefore, no matter how we instantiate the generalized version, a small private key attack will always succeed.

Structure of the Paper. We introduce in Sect. 2 notations and definitions used throughout the paper. Inspired by Rivest et al. and Elkamchouchi et al.’s work [15, 29], in Sect. 3 we construct a family of RSA-like cryptosystems. After proving several useful lemmas in Sect. 4, we extend Wiener’s small private key attack in Sect. 5. Two concrete instantiations are provided in Sect. 6. We conclude our paper in Sect. 7.

2 Preliminaries

Notations. Throughout the paper, \(\lambda \) denotes a security parameter. Also, the notation |S| denotes the cardinality of a set S. The set of integers \(\{0, \ldots , a\}\) is further denoted by [0, a]. We use \(\simeq \) to indicate that two values are approximately equal.

2.1 Continued Fraction

For any real number \(\zeta \) there exists a unique sequence \((a_n)_n\) of integers such that

$$\begin{aligned} \zeta = a_0 + \frac{1}{\displaystyle a_1 + \frac{1}{\displaystyle a_2+ \frac{ 1}{\displaystyle a_3 + \frac{1}{\displaystyle a_4+\cdots }}}}, \end{aligned}$$

where \(a_k > 0\) for any \(k \ge 1\). This sequence represents the continued fraction expansion of \(\zeta \) and is denoted by \(\zeta = [a_0, a_1, a_2,\ldots ]\). Remark that \(\zeta \) is a rational number if and only if its corresponding representation as a continued fraction is finite.

For any real number \(\zeta = [a_0, a_1, a_2, \ldots ]\), the sequence of rational numbers \((A_n)_n\), obtained by truncating this continued fraction, \(A_k = [a_0, a_1, a_2, \ldots , a_k]\), is called the convergents sequence of \(\zeta \).

According to [18], the following bound allows us to check if a rational number u/v is a convergent of \(\zeta \).

Theorem 1

Let \(\zeta = [a_0, a_1, a_2, \ldots ]\) be a positive real number. If u, v are positive integers such that \(\gcd (u,v)=1\) and

$$\begin{aligned} \left| \zeta - \frac{u}{v} \right| < \frac{1}{2v^2}, \end{aligned}$$

then u/v is a convergent of \([a_0, a_1, a_2, \ldots ]\).

2.2 Quotient Groups

In this section we will provide the mathematical theory needed to generalize the Rivest, Shamir and Adleman, and the Elkamchouchi, Elshenawy and Shaban encryption schemes. Therefore, let \((\mathbb {F}, +, \cdot )\) be a field and \(t^n-r\) an irreducible polynomial in \(\mathbb {F}[t]\). Then

$$\begin{aligned} \mathbb {A}_n = \mathbb {F}[t]/(t^n-r) = \{a_0 + a_1t + \ldots + a_{n-1} t^{n-1} \mid a_0, a_1, \ldots , a_{n-1} \in \mathbb {F}\} \end{aligned}$$

is the corresponding quotient field. Let \(a(t), b(t) \in \mathbb {A}_n\). Remark that the quotient field induces a natural product

$$\begin{aligned} a(t) \circ b(t) &= \left( \sum _{i=0}^{n-1} a_i t^i\right) \circ \left( \sum _{j=0}^{n-1} b_j t^j\right) \\ &= \sum _{i=0}^{2n-2} \left( \sum _{j=0}^{i} a_j b_{i-j} \right) t^i\\ &= \sum _{i=0}^{n-1} \left( \sum _{j=0}^{i} a_j b_{i-j} \right) t^i + r \sum _{i=n}^{2n-2} \left( \sum _{j=0}^{i} a_j b_{i-j} \right) t^{i-n}\\ &= \sum _{i=0}^{n-2} \left( \sum _{j=0}^{i} a_j b_{i-j} + r \sum _{j=0}^{i+n} a_j b_{i-j+n} \right) t^i + \sum _{j=0}^{n-1} a_j b_{n-1-j} t^{n-1}. \end{aligned}$$

3 The Scheme

Let p be a prime number. When we instantiate \(\mathbb {F} = \mathbb {Z}_p\), we have that \(\mathbb {A}_n = GF(p^n)\) is the Galois field of order \(p^n\). Moreover, \(\mathbb {A}_n^*\) is a cyclic group of order \(\varphi _n(\mathbb {Z}_p) = p^n-1\). Remark that an analogous of Fermat’s little theorem holds

$$\begin{aligned} a(x)^{\varphi _n(\mathbb {Z}_p)} \equiv 1 \bmod p, \end{aligned}$$

where \(a(x) \in \mathbb {A}_n^*\) and the power is evaluated by \(\circ \)-multiplying a(x) by itself \(\varphi _n(\mathbb {Z}_p)-1\) times. Therefore, we can build an encryption scheme that is similar to RSA using the \(\circ \) as the product.

  • Setup(\(\lambda \)): Let \(n > 1\) be an integer. Randomly generate two distinct large prime numbers p, q such that \(p, q \ge 2^\lambda \) and compute their product \(N = pq\). Select \(r\in \mathbb {Z}_N\) such that the polynomial \(t^n-r\) is irreducible in \(\mathbb {Z}_p[t]\) and \(\mathbb {Z}_q[t]\). Let

    $$\begin{aligned} \varphi _n(\mathbb {Z}_N) = \varphi _n(N) = (p^n-1) \cdot (q^n-1). \end{aligned}$$

    Choose an integer e such that \(\gcd (e, \varphi _n(N)) = 1\) and compute d such that \(ed \equiv 1 \bmod \varphi _n(N)\). Output the public key \(pk = (n, N, r, e)\). The corresponding secret key is \(sk = (p, q, d)\).

  • Encrypt(pk, m): To encrypt a message \(m = (m_0, \ldots , m_{n-1})\in \mathbb {Z}_N^{n}\) we first construct the polynomial \(m(t) = m_0 + \ldots + m_{n-1} t^{n-1} \in \mathbb {A}_n^*\) and then we compute \(c(t) \equiv [m(t)]^{e} \bmod N\). Output the ciphertext c(t).

  • Decrypt(sk, c(t)): To recover the message, simply compute \(m(t) \equiv [c(t)]^{d} \bmod N\) and reassemble \(m = (m_0, \ldots , m_{n-1})\).

Remark 1

When \(n=1\) we get the RSA scheme [29]. Also, when \(n=2\), we obtain the Elkamchouchi et al. cryptosystem [15].

4 Useful Lemmas

In this section we provide a few useful properties of \(\varphi _n(N)\). Before starting our analysis, we first note that plugging \(q = N/p\) in \(\varphi _n(N)\) leads to the following function

$$\begin{aligned} f_n(p) = N^n - p^n - \left( \frac{N}{p}\right) ^n +1, \end{aligned}$$

with p as a variable. The next lemma tells us that, under certain conditions, \(f_n\) is a strictly decreasing function.

Proposition 1

Let N be a positive integer. Then for any integers \(n>1\) and \(\sqrt{N} \le x < N\), we have that the function

$$\begin{aligned} f_n(x) = N^n - x^n - \left( \frac{N}{x}\right) ^n +1, \end{aligned}$$

is strictly decreasing with x.

Proof

Computing the derivative of f we have that

$$\begin{aligned} f'(x)=-n\left( x^{n-1} - \frac{1}{x^{n+1}} \cdot N^n\right) . \end{aligned}$$

Using \(x \ge \sqrt{N}\) we obtain that

$$\begin{aligned} x^{2n} > N^n \Leftrightarrow x^{n-1} &> \frac{1}{x^{n+1}} \cdot N^n \Leftrightarrow f'(x)<0, \end{aligned}$$

and therefore we have f is strictly decreasing function.    \(\square \)

Using the following result from [26, Lemma 1], we will compute a lower and upper bound for \(\varphi _n(N)\).

Lemma 1

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). Then the following property holds

$$\begin{aligned} \frac{\sqrt{2}}{2}\sqrt{N} < q < \sqrt{N} < p < \sqrt{2}\sqrt{N}. \end{aligned}$$

Corollary 1

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). Then the following property holds

$$\begin{aligned} \left( \sqrt{N}^n - 1\right) ^2 > \varphi _n(N) > N^n \left( 1-\frac{2^n+1}{\sqrt{2N}^n}\right) + 1. \end{aligned}$$

Proof

By Lemma 1 we have that

$$\begin{aligned} \sqrt{N} < p < \sqrt{2}\sqrt{N}, \end{aligned}$$

which, according to Proposition 1, leads to

$$\begin{aligned} f_n(\sqrt{N}) > f_n(p) > f_n(\sqrt{2}\sqrt{N}). \end{aligned}$$

This is equivalent to

$$\begin{aligned} \left( \sqrt{N}^n - 1\right) ^2 > \varphi _n(N) > N^n \left( 1-\frac{2^n+1}{\sqrt{2N}^n}\right) + 1, \end{aligned}$$

as desired.    \(\square \)

When \(n=1\) and \(n=2\), the following results proven in [10] and [7] respectively become a special case of Corollary 1.

Corollary 2

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). Then the following property holds

$$\begin{aligned} (\sqrt{N}-1)^2 > \varphi _1(N) > N+1 -\frac{3}{\sqrt{2}}\sqrt{N} . \end{aligned}$$

Corollary 3

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). Then the following property holds

$$\begin{aligned} (N-1)^2 > \varphi _2(N) > N^2+1 -\frac{5}{2}N . \end{aligned}$$

We can use Corollary 1 to find a useful approximation of \(\varphi _n\). This result will be useful when devising the attack against the generalized RSA scheme.

Proposition 2

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). We define

$$\begin{aligned} \varphi _{n,0}(N) = \frac{1}{2} \cdot \left( \sqrt{N}^n - 1\right) ^2 + \frac{1}{2} \cdot \left[ N^n \left( 1-\frac{2^n+1}{\sqrt{2N}^n}\right) + 1\right] . \end{aligned}$$

Then the following holds

$$\begin{aligned} |\varphi _n(N) - \varphi _{n,0}(N)| < \frac{\varDelta _n}{2} \sqrt{N}^n, \end{aligned}$$

where

$$\begin{aligned} \varDelta _n = \frac{(\sqrt{2}^n-1)^2}{\sqrt{2}^n}. \end{aligned}$$

Proof

According to Corollary 1, \(\psi _{n,0}(N)\) is the mean value of the lower and upper bound. The following property holds

$$\begin{aligned} |\psi _n(N) - \psi _{n,0}(N)| &\le \frac{1}{2} \left[ \left( \sqrt{N}^n - 1\right) ^2 - N^n \left( 1-\frac{2^n+1}{\sqrt{2N}^n}\right) - 1 \right] \\ &= \frac{1}{2} \left( N^n - 2\sqrt{N}^n +1 - N^n + N^n \cdot \frac{2^n+1}{\sqrt{2N}^n} -1 \right) \\ &=\frac{1}{2} \sqrt{N}^n \left( \frac{2^n+1}{\sqrt{2}^n}-2 \right) \\ &=\frac{\varDelta _n}{2} \sqrt{N}^n, \end{aligned}$$

as desired.    \(\square \)

When \(n=1\) and \(n=2\), the following property presented in [10] and [7] respectively become a special case of Proposition 2.

Corollary 4

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). Then the following holds

$$\begin{aligned} |\varphi _1(N) - \varphi _{1,0}(N)| < \frac{3-2\sqrt{2}}{2\sqrt{2}}\sqrt{N}. \end{aligned}$$

Corollary 5

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). Then the following holds

$$\begin{aligned} |\varphi _2(N) - \varphi _{2,0}(N)| < \frac{1}{4}N. \end{aligned}$$

5 Application of Continued Fractions

We further provide an upper bound for selecting d such that we can use the continued fraction algorithm to recover d without knowing the factorisation of the modulus N.

Theorem 2

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If \(e < \varphi _n(N)\) satisfies \(ed - k \varphi _n(N) = 1\) with

$$\begin{aligned} d < \sqrt{\frac{\sqrt{2}^n N^n (\sqrt{N}^n -\delta _n)}{e(\sqrt{2}^n-1)^2}}, \end{aligned}$$
(1)

where

$$\begin{aligned} \delta _n = \frac{2\sqrt{2}^n}{(\sqrt{2}^n -1)^2} + \frac{2(2^n+1)}{\sqrt{2}^n}, \end{aligned}$$

then we can recover d in polynomial time.

Proof

Since \(ed - k \varphi _n(N) = 1\), we have that

$$\begin{aligned} \left| \frac{k}{d} - \frac{e}{\varphi _{n,0}(N)}\right| &\le e\left| \frac{1}{\varphi _{n,0}(N)} - \frac{1}{\varphi _n(N)}\right| + \left| \frac{e}{\varphi _n(N)} - \frac{k}{d} \right| \\ &= e \frac{|\varphi _n(N) - \varphi _{n,0}(N)|}{\varphi _{n,0}(N)\varphi _n(N)} + \frac{1}{\varphi _n(N)d}. \end{aligned}$$

Let \(\varepsilon _n = N^n -\sqrt{N}^n(2^n+1)/\sqrt{2}^n + 1\). Using \(d = (k \varphi _n(N) -1) / e = 1\) and Proposition 2 we obtain

$$\begin{aligned} \left| \frac{k}{d} - \frac{e}{\varphi _{n,0}(N)}\right| &\le \frac{\frac{\varDelta _n}{2}e\sqrt{N}^n}{ \varphi _{n,0}(N)\varphi _n(N)} + \frac{e}{\varphi _n(N)(k \varphi _n(N) -1)}\\ &\le \frac{e\sqrt{N}^n(\sqrt{2}^n-1)^2}{2\sqrt{2}^n\varepsilon _{n}^2} + \frac{e}{\varepsilon _n(k \varepsilon _n -1)}\\ &\le \frac{e\sqrt{N}^n(\sqrt{2}^n-1)^2}{2\sqrt{2}^n \varepsilon _{n}^2} + \frac{e}{\varepsilon _n^2}\\ &= \frac{e[\sqrt{N}^n(\sqrt{2}^n-1)^2 + 2\sqrt{2}^n]}{2\sqrt{2}^n \varepsilon _{n}^2}\\ &\le \frac{e[\sqrt{N}^n(\sqrt{2}^n-1)^2 + 2\sqrt{2}^n]}{2\sqrt{2}^n (N^n -\frac{2^n+1}{\sqrt{2}^n}\sqrt{N}^n)^2}. \end{aligned}$$

Note that

$$\begin{aligned} \frac{[\sqrt{N}^n(\sqrt{2}^n-1)^2 + 2\sqrt{2}^n]}{2\sqrt{2}^n (N^n -\frac{2^n+1}{\sqrt{2}^n}\sqrt{N}^n)^2} &= \frac{(\sqrt{2}^n-1)^2[\sqrt{N}^n + \frac{2\sqrt{2}^n}{(\sqrt{2}^n-1)^2}]}{2\sqrt{2}^n N^n (\sqrt{N}^n -\frac{2^n+1}{\sqrt{2}^n})^2}\\ &\le \frac{(\sqrt{2}^n-1)^2}{2\sqrt{2}^n N^n (\sqrt{N}^n -\delta _n)}, \end{aligned}$$

which leads to

$$\begin{aligned} \left| \frac{k}{d} - \frac{e}{\varphi _{n,0}(N)}\right| &\le \frac{e(\sqrt{2}^n-1)^2}{2\sqrt{2}^n N^n (\sqrt{N}^n -\delta _n)} \le \frac{1}{2d^2}. \end{aligned}$$

Using Theorem 1 we obtain that k/d is a convergent of the continued fraction expansion of \(e/\varphi _{n,0}(N)\). Therefore, d can be recovered in polynomial time.    \(\square \)

Corollary 6

Let \(\alpha < 1.5 n\) and \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If we approximate \(e \simeq N^\alpha \) and \(N \simeq 2^{2\lambda }\), then Eq. 1 becomes

$$\begin{aligned} d < \frac{2^{(n-\alpha )\lambda + \frac{n}{4}} \sqrt{2^{n\lambda } - \delta _n}}{\sqrt{2}^n-1} < \frac{2^{(1.5 n-\alpha )\lambda + \frac{n}{4}} }{\sqrt{2}^n-1} \end{aligned}$$

or equivalently

$$\begin{aligned} \log _2(d) < (1.5 n-\alpha )\lambda + \frac{n}{4} - \log _2(\sqrt{2}^n-1) \simeq (1.5 n-\alpha )\lambda \end{aligned}$$

When cases \(n=1\) and \(n=2\) are considered the following properties presented in [10] and [7] respectively become a special case of Corollary 6. Note that when \(n=\alpha = 1\) we obtain roughly the same margin as Wiener [4, 33] obtained for the classical RSA.

Corollary 7

Let \(\alpha < 1.5\) and \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If we approximate \(e \simeq N^\alpha \) and \(N \simeq 2^{2\lambda }\) then Eq. 1 is equivalent to

$$\begin{aligned} \log _2(d) < (1.5-\alpha )\lambda - 0.25 + 1.27\simeq (1.5-\alpha )\lambda . \end{aligned}$$

Corollary 8

Let \(\alpha < 3\) and \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If we approximate \(e \simeq N^\alpha \) and \(N \simeq 2^{2\lambda }\) then Eq. 1 is equivalent to

$$\begin{aligned} \log _2(d) < (3-\alpha )\lambda - 0.5 \simeq (3-\alpha )\lambda . \end{aligned}$$

The last corollary tells us what happens when e is large enough. We can see that n is directly proportional to the secret exponent’s upper bound.

Corollary 9

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If we approximate \(e \simeq N^n\) and \(N \simeq 2^{2\lambda }\) then Eq. 1 is equivalent to

$$\begin{aligned} \log _2(d) < 0.5 n\lambda + \frac{n}{4} - \log _2(\sqrt{2}^n-1) \simeq 0.5 n\lambda . \end{aligned}$$

6 Experimental Results

We further present an example for the \(n=3\) and \(n=4\) cases. Examples for \(n=1\) and \(n=2\) cases are provided in [10] and [7] respectively, and thus we omit them.

6.1 Case \(n=3\)

Before providing our example, we first show how to recover p and q once \(\varphi _3(N) = (ed-1)/k\) is recovered using our attack.

Lemma 2

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If \(\varphi _3(N) = N^3 - p^3 - q^3 +1\) is known, then p and q can be recovered in polynomial time.

Proof

We will rewrite \(\varphi _3(N)\) as

$$\begin{aligned} \varphi _3(N) &= N^3 - p^3 - 3p^2q - 3pq^2 - q^3 + 1 + 3p^2q + 3pq^2\\ &= N^3 - (p+q)^3 + 3N(p+q) + 1, \end{aligned}$$

which is equivalent to

$$\begin{aligned} (p+q)^3 - 3N(p+q) + \varphi _3(N) - N^3 - 1 = 0. \end{aligned}$$

Finding \(S = p+q\) is equivalent to solving (in \(\mathbb {Z}\)) the following cubic equation

$$\begin{aligned} x^3 - 3Nx + (\varphi _3(N) - N^3 - 1) = 0. \end{aligned}$$
(2)

which can be done in polynomial time as it is presented in [17]. In order to find p and q, we compute \(D = p-q\) using the following remark

$$\begin{aligned} (p-q)^2 = (p+q)^2 - 4pq = S^2 - 4N. \end{aligned}$$

Taking into account that \(p>q\), D is the positive square root of the previous quantity, and thus we derive the following

$$\begin{aligned} {\left\{ \begin{array}{ll} p= \frac{S+D}{2}\\ q= \frac{S-D}{2} \end{array}\right. }. \end{aligned}$$

   \(\square \)

The following lemma shows that in order to factor N we only need to find one solution to Eq. 2, namely its unique integer solution.

Lemma 3

Eq. 2 always has exactly two non-real roots and an integer one.

Proof

Let \(x_1\), \(x_2\) and \(x_3\) be Eq. 2’s roots. Using Vieta’s formulas we have

$$\begin{aligned} x_1+x_2+x_3 &= 0,\\ x_1x_2+x_2x_3+x_3x_1 &= -3N,\\ x_1x_2x_3 &= - (\varphi _3(N) - N^3 - 1). \end{aligned}$$

From the first two relations we obtain

$$\begin{aligned} x_1^2+x_2^2+x_3^2 &= (x_1+x_2+x_3)^2 - 2(x_1x_2+x_2x_3+x_3x_1)\\ &= 6N. \end{aligned}$$

If we assume that \(x_1=p+q\) and \(x_2, x_3\) are both real, we get the following system

$${\left\{ \begin{array}{ll} x_2 + x_3 = -(p+q)\\ x_2^2 + x_3^2 = 6N - (p+q)^2 \end{array}\right. }\Rightarrow {\left\{ \begin{array}{ll} (x_2+x_3)^2 = (p+q)^2 \\ 2(x_2^2 + x_3^2) = 12N - 2(p+q)^2 \end{array}\right. }\Rightarrow $$
$$\begin{aligned} (x_2-x_3)^2 &= 12N-3(p+q)^2\\ &= 6pq - 3p^2 - 3q^2 \\ &= -3(p-q)^2 < 0. \end{aligned}$$

Therefore, we obtain a contradiction, and hence we conclude that Eq. 2 has one real root, which is \(p+q \in \mathbb {Z}\), and two non-real roots.    \(\square \)

Now, we will exemplify our attack for \(n=3\) using the following small public key

$$\begin{aligned} N = &~3014972633503040336590226508316351022768913323933,\\ e = &~8205656493798992557632452332926222819762435306999\\ &~0124626035612517563005998895654688526643002715434\\ &~25112020628278119623817044320522328087505650969. \end{aligned}$$

Remark that \(e \approx N^{2.989}\). We use the Euclidean algorithm to compute the continued fraction expansion of \(e / \varphi _{3,0}(N)\) and obtain that the first 25 partial quotients are

$$\begin{aligned}{}[0, 3, 2, 1, 16, 5, 3, 5, 1, 5, 1, 11, 2, 6, 1, 3, 1, 4, 1, 1, 1, 267, 1, 1, 4,\ldots ]. \end{aligned}$$

According to Theorem 2, the set of convergents of \(e / \varphi _{3,0}(N)\) contains all the possible candidates for k/d. From these convergents we select only those for which \(\varphi _3 = (ed-1)/k\) is an integer and the following system of equations

$$\begin{aligned} {\left\{ \begin{array}{ll} \varphi _3 = (p^3-1)(q^3-1)\\ N = pq \end{array}\right. } \end{aligned}$$

has a solution as given in Lemma 2. The 2nd, 3rd and 21st convergents satisfy the first condition, however only the last one leads to a valid solution for p and q. More precisely, the 21st convergent leads to

$$\begin{aligned} \varphi _3 = &~2740628207892953207018702174077483807563264408773\\ &~7057963987757509374280517157259708222994487763446\\ &~946621855565600927215471565545807198298953933036,\\ \frac{k}{d} = &~\frac{514812488}{1719435401},\\ p = &~2119778199036859068707819,\\ q = &~1422305708622213956806807. \end{aligned}$$

6.2 Case \(n=4\)

As in the previous case, we first show how to factorize N once \(\varphi _4\) is known.

Lemma 4

Let \(N = pq\) be the product of two unknown primes with \(q < p < 2q\). If \(\varphi _4(N) = N^4-p^4-q^4 +1\) is known, then

$$\begin{aligned} p &= \frac{1}{2}(S+D) \quad \text { and }\quad q = \frac{1}{2}(S-D), \end{aligned}$$

where \(S = \sqrt{2N + \sqrt{(N^2+1)^2 - \varphi _4(N)}}\) and \(D = \sqrt{S^2 - 4N}\).

Proof

We will rewrite \(\varphi _4(N)\) as

$$\begin{aligned} \varphi _4(N) &= N^4 - p^4 - 4p^3q - 6p^2q^2 - 4pq^3 - q^4 + 1 + 4p^3q + 6p^2q^2 + 4pq^3\\ &= N^4 - (p+q)^4 + 4N(p^2+2pq+q^2) - 2p^2q^2 + 1\\ &= N^4 - (p+q)^4 + 4N(p+q)^2 - 2N^2 + 1 \end{aligned}$$

which is equivalent to

$$\begin{aligned} (p+q)^4 - 4N(p+q)^2 + \varphi _4(N) - (N^2 - 1)^2 = 0. \end{aligned}$$

Finding \(S' = p+q\) is equivalent to solving (in \(\mathbb {Z}\)) the following biquadratic equation

$$\begin{aligned} x^4 - 4Nx^2 + \varphi _4(N) - (N^2 - 1)^2 &= 0 \Leftrightarrow \\ (x^2)^2 - 4N(x^2) + \varphi _4(N) - (N^2 - 1)^2 &= 0. \end{aligned}$$

The previous equation can be solved as a normal quadratic equation. Computing the discriminant \(\varDelta \), we have that

$$\begin{aligned} \varDelta &= 4(N^2+1)^2 - 4\varphi _4(N) > 0. \end{aligned}$$

Thus, the roots of the quadratic equation, \(x'_{1,2}\), are

$$\begin{aligned} x'_{1,2} = 2N \pm \sqrt{(N^2+1)^2-\varphi _4(N)}. \end{aligned}$$

The roots of the biquadratic equation are the square roots of the previous quantities.

$$\begin{aligned} x_{1,2} = \pm \sqrt{2N + \sqrt{(N^2+1)^2-\varphi _4(N)}} \\ x_{3,4} = \pm \sqrt{2N - \sqrt{(N^2+1)^2-\varphi _4(N)}} \end{aligned}$$

The roots \(x_{3,4}\) are pure imaginary since

$$\begin{aligned} \sqrt{(N^2+1)^2-\varphi _4(N)} &> 2N \Leftrightarrow \\ (N^2+1)^2-\varphi _4(N)&> 4N^2 \Leftrightarrow \\ N^4 + 2N^2 + 1 - N^4 + p^4 + q^4 - 1 - 4N^2 &> 0 \Leftrightarrow \\ (p^2-q^2)^2 &> 0. \end{aligned}$$

The root \(x_2 = - \sqrt{2N + \sqrt{(N^2+1)^2-\varphi _4(N)}} < 0\), thus we get \(S' = S = x_1 = \sqrt{2N + \sqrt{(N^2+1)^2-\varphi _4(N)}}\). The values of p and q can be recovered by using the algorithm from Lemma 2.    \(\square \)

We will further present our attack for \(n=4\) using the following small public key

$$\begin{aligned} N = &~3014972633503040336590226508316351022768913323933, \\ e = &~3886649078157217512540781268280213360319970133145\\ &~6396788273204320283738850302214441484301356047280\\ &~9980074678226938065582620857819830171139174634897\\ &~69731055010977380039512575106301590600391232847. \end{aligned}$$

Note that \(e \approx N^{3.993}\). Applying the continued fraction expansion of \(e / \varphi _{4,0}(N)\), we get the first 25 partial quotients

$$\begin{aligned}{}[0, 2, 7, 1, 15, 6, 1, 2, 4, 1, 1, 2, 1, 1, 3, 1, 1, 1, 2, 38, 1, 2, 1, 45, 8,\ldots ]. \end{aligned}$$

In this case, we consider the convergents of \(e / \varphi _{4,0}(N)\), and we select only those for which \(\varphi _4 = (ed-1)/k\) is an integer and the following system of equations

$${\left\{ \begin{array}{ll} \varphi _4 = (p^4-1)(q^4-1)\\ N = pq \end{array}\right. }$$

has a solution as given in Lemma 4. The 2nd and 23rd convergents satisfy the first condition, however only the last one leads to a valid solution for p and q. More precisely, the 23rd convergent leads to

$$\begin{aligned} \varphi _4 = &~8262919045403735048878111025050137547018067986718\\ &~6489272861711603139280409749776405912009959512474\\ &~1225965967573968605037596274853618481302754457480\\ &~67878911842670048325065350941516266452271040000,\\ \frac{k}{d} = &~\frac{799532980}{1699787183},\\ p = &~ 2119778199036859068707819,\\ q = &~ 1422305708622213956806807. \end{aligned}$$

7 Conclusions

In this paper we introduced a family of RSA-like cryptosystems, which includes the RSA and Elkamchouchi et al. public key encryption schemes [15, 29] (i.e. \(n=1\) and \(n=2\)). Then, we presented a small private key attack against our family of cryptosystems and provided two instantiations of it. As a conclusion, the whole family of RSA-like schemes allows an attacker to recover the secret exponent via continued fractions when the public exponent is close to \(N^n\) and the secret exponent is smaller that \(N^{0.25n}\).

Future Work. When \(n=1,2,3,4\), in Sect. 6 and [4, 7, 10] a method for factoring N once \(\varphi _n\) is known is provided. Although we found a method for particular cases of n we could not find a generic method for factoring N. Therefore, we leave it as an open problem. Another interesting research direction, is to find out if the attack methods described in Sect. 1 for the RSA and Elkamchouchi et al. schemes also work in the general case.