Chinese remainder theorem to solve $3 \bmod 11$ and $11 \bmod 13$

195 Views Asked by At

I'm trying to Decrypt a cipher text which has been encrypted using RSA and whose resulting value is $20$.

Public parameters are $N = 143$ and $e = 17$.

I've gotten down to equations $$x\equiv3 \bmod 11\quad\text{ and }\quad x\equiv 11 \bmod 13 \tag{1}$$

and I've read that to get the plaintext ($x$) you must apply Chinese remainder theorem which I don't really understand. How to solve $(1)$?

1

There are 1 best solutions below

0
On

The Chinese Remainder Theorem Tells you that if the moduli are relatively prime a solution exists and that any two solutions are congruent under the product of the moduli. You can solve this using the Euclidean Algorithm also and addition and multiplication properties of modular arithmetic. (This one is not complicated enough to need the Euclidean algorithm but that might come in handy in the future.)

Here is how to find the number equal to $3 \pmod{11}$ and $11 \pmod{13}$. I am not sure where you wanted to go from there. So you are looking for an integer $x$ where $$x \equiv 3 \pmod{11}$$ $$x \equiv 11 \pmod{13}$$ Then $x = 3+11k$ for some integer $k$. You can substitute this into the second equation : $$3+11k \equiv 11 \pmod{13}$$ Subtract $3$ from both sides and
$$11k\equiv 8 \pmod{13}$$ $k \equiv 9 \pmod{13}$ since $9\times11-8=91$ a multiple of $13$
but $x$ was already defined in terms of $k$ so $x=3+11k=3+11(9)=102$
$x=102$
$102 \pmod{11} \equiv 3$ and $102\pmod{13} \equiv 11$