Security of RSA cryptosystem variant

Question

A variant of RSA cryptosystem is given as following:

$$N=p*q$$

$$ed=1 \space \space mod \space \space (p^r-1)(q^r-1)$$

$$c= m^e \space \space mod \space \space N $$

$$m= c^d \space \space mod \space \space N $$

where $r$ is an a small integer and $p , q$ are primes , $e$ is public exponent , $d$ is private exponent

Trivial Q. Does replacing $\phi(N)$ with $(p^r-1)(q^r-1)$ produces a vulnerability?

Answer 1

In the case you choose $e$ first, you get a private exponent $d$ equivalent to the usual one. Since it is private, no vulnerability can arise. In other words, it is not possible even to distinguish whether you use standard RSA or this variant.

In the case you choose $d$ first, then $e$ may leak a lot of information. For example, in the Boneh-Durfee attack on small $d$, the bound $N^{0.292}$ is actually derived from $e$. If $e$ is larger, it is probably possible attack to attack larger $d$ than in standard RSA.

A simple attack for $d < n^{r/4}$. Consider as usual the exponents equation:

$$ ed = 1 + k(N^r-p^r-q^r+1). $$

Consider it modulo $N^r+1$:

$$ ed + k(p^r+q^r) \equiv 1 \pmod{N^r+1}. $$

we can see linear unknowns $d < N^{r/4}$ and $k(p^r+q^r) < N^{3r/4}$ (because $k < d$). By reducing the equation using LLL, we can get an equation with smaller coefficients, which will hold in integers:

$$ b d + ak(p^r + q^r) = a, $$

where $a,b$ are known. Reducing the equation modulo $a$ we'll recover $d$.

Note that we get the same bound as in the Wiener's attack on standard RSA ($d < N^{1/4})$. Applying the Coppersmith-based Boneh and Durfee method will likely improve the result similarly.