A variant of RSA cryptosystem is given as following:


$$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?

  • $\begingroup$ Have you already checked that this will preserve functional correctness? $\endgroup$
    – SEJPM
    Oct 19 '20 at 9:47
  • 1
    $\begingroup$ @SEJPM $(p-1)$ divides $(p^r-1)$ so should be ok $\endgroup$
    – Fractalice
    Oct 19 '20 at 10:26
  • $\begingroup$ We now need $e$ and $d$ to be coprime with $p^r-1$ and $q^r-1$, contrary to just $p-1$ and $q-1$ in normal RSA. That narrows the choice. In particular, for $r$ even, that makes it impossible to use the otherwise desirable $e=3$. $\endgroup$
    – fgrieu
    Oct 19 '20 at 12:25

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.

  • $\begingroup$ Thank you for the explanation $\endgroup$
    – hardyrama
    Oct 20 '20 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.