1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: your $c$ is modulo $p$ when you are using the Euler theorem. $\endgroup$ – Tosh Sep 17 '19 at 14:11
  • $\begingroup$ 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 $\endgroup$ – ALEJANDRO PEREZ MORENO Sep 17 '19 at 14:32
  • $\begingroup$ $c~(mod~p)$ is in range $[\![0;p-1]\!]$. Which elements are not coprime to $p$ ? $\endgroup$ – Tosh Sep 17 '19 at 14:44
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Your answer also gave some clues for my own proof using transitivity, I'll post it as a different answer. $\endgroup$ – ALEJANDRO PEREZ MORENO Sep 17 '19 at 15:51
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.