Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
