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
I'm following this (Chinese Remainder Theorem and RSA) post, but I don't understand how
$(c^d \bmod n) \bmod p = c^d \bmod p$.
Being told that it's because $n=pq$ is not enough for me to understand.
Could someone please elaborate on that to help me fully understand what's going on here?
Any input would be GREATLY appreciated!
Well, lets see if we can go through it from the basics.
$x \bmod y$ is the unique integer $x + \ell y$ that satisfies $0 \le x + \ell y < y$, for some integer $\ell$ (which might be positive, negative or zero) I will skip the parts that prove that, if $x, y$ are both integers and $y > 0$, then there exists such an $\ell$ and it is, in fact, unique.
Now, when we have $(x \bmod pq) \bmod p$, we can replace the inner $(x \bmod pq)$ with $x + \ell_1 pq$, we get $x + \ell_1 pq \bmod p$. This in turn becomes $x + \ell_1 pq + \ell_2 p$. We further note that $\ell_4 = \ell_1 q + \ell_2$ is an integer (which we will denote at $\ell_4$) [1], and so we have:
$$(x \bmod pq) \bmod p = x + \ell_4 p$$
On the other side, $x \bmod p$ is the same as $x + \ell_3 p$, that is,
$$x \bmod p = x + \ell_3 p$$
So, on one side, we have $x + \ell_4 p$, which is a value between 0 and $p-1$.
On the other side, we have $x + \ell_3 p$, which is also a value between 0 and $p-1$.
Since both $\ell_3$ and $\ell_4$ are integers, these must be the same, and hence the original values $(x \bmod pq) \bmod p$ and $x \bmod p$ must also be the same.
Then, replace $x$ with $c^d$ and $pq$ with $n$, and there you go...
[1]: BTW: this is the step where we assume that $p$ is a factor of $n$ if that is not true, then relation will not hold in general.
