1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you already checked that this will preserve functional correctness? $\endgroup$ – SEJPM Oct 19 at 9:47
  • 1
    $\begingroup$ @SEJPM $(p-1)$ divides $(p^r-1)$ so should be ok $\endgroup$ – Fractalic Oct 19 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 at 12:25
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the explanation $\endgroup$ – hardyrama Oct 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.