# RSA-CRT exponent reduction

In the implementation of RSA-CRT, the exponent d is reduced mod p-1 ($$d_p = d \bmod {(p-1)}$$). The only proof I've found for that, is the following (considering $$d = k\varphi(p) + d \bmod {\varphi(p)}$$: $$c^d = c^{k\varphi(n) + d \bmod {\varphi(p)}}$$ $$(c^{\varphi(p)})^k * c^{d\bmod {\varphi(p)}} \equiv (1)^k * c^{d\bmod {(p-1)}} (\bmod p)$$ Source: https://www.di-mgt.com.au/crt_rsa.html So $$c^d \equiv c^{d(\bmod(p-1))} (\bmod(p))$$ However, I can't see why is the Euler theorem valid here, as c is not granted to be coprime with p (as far as I know). Any hint on this?

• Hint: your $c$ is modulo $p$ when you are using the Euler theorem.
– Tosh
Sep 17 '19 at 14:11
• Yes, I see that. But Euler's theorem only holds when $c$ and $p$ are coprimes, so $(c^{\varphi(p)})^k \equiv 1^k \mod p$ only if c and p are coprimes Sep 17 '19 at 14:32
• $c~(mod~p)$ is in range $[\![0;p-1]\!]$. Which elements are not coprime to $p$ ?
– Tosh
Sep 17 '19 at 14:44
• c is considered as the ciphertext with the modulus pq. It can be a multiple of p, e.g., 0, p, 2p,..., qp in which case c^d=0 (mod p) and exponent reduction still holds Apr 25 '21 at 5:12

You're correct, the proof isn't precisely correct, because we don't necessarily have $$c^{\phi(n)} = 1$$, specifically in the case $$c \equiv 0 \pmod p$$.
Here is a more correct approach; we have $$c^1 \equiv c \pmod p$$ (trivially), and $$c^{p-1} \equiv c \pmod p$$ for any $$c$$, prime $$p$$ (Fermat's little theorem [1]). By induction, we get $$c^{k (p-1) + 1} \equiv c^1 \pmod p$$ (for any $$k$$), and hence $$c^{k (p-1) + \ell} \equiv c^\ell \pmod p$$.
If we designate $$x = k(p-1) + \ell$$ for $$0 \le \ell < p-1$$ (and any $$x$$ can be put in that form), we have $$c^x \equiv c^{x \bmod p-1} \pmod p$$, for any $$x, c$$ and prime $$p$$; in particular, if $$x = d$$
[1]: The most common expression of Fermat's Little Theorom is that $$1 \equiv x^{p-1} \bmod p$$ for prime $$p$$, $$x$$ relatively prime to $$p$$. However, an equivalent formulation (and what Fermat originally stated) is that $$x \equiv x^p \bmod p$$ for prime $$p$$, any $$x$$ - I'm using this alternative formulation.
I'm not sure how I didn't realize there are only two cases: $$gcd(p, c) = 1$$, or $$c\equiv 0 \bmod (p)$$. Given this, here's the proof I came with. For the former, the proof into the question is valid. For the latter, we have: $$c\equiv 0 \bmod (p)$$ $$c^k\equiv 0 \bmod (p)$$ for any $$k$$. So, using transitivity: $$c^k\equiv c\bmod (p)$$ In this case $$k=d\bmod (p-1)$$