RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1 I want to make a following proof but I got some difficulties with it.
Would be super if you people have any tips / advises.
Introduction:
Let (N,e) be our public key and (N,s) our private key with $N=pq$ and $ggT(\varphi(n),e)=1$, as well as $es\equiv 1\mod N$.
I want to show that since Lemma of Bézout shows, that there are $a,b\in \mathbb{N}$ so that $ap-bq=1$, the message of $x=ap\mod N$ is equal to the encrypted message $y=x^e \mod N$.
My Plan:
I started by using the Chinese remainder theorem. To show $x\overset{!}{=}y=x^e\mod N$ we need to show, that $x\overset{!}{=}x^e\mod p$ and $x\overset{!}{=}x^e\mod q$. I could also use the Chinese remainder theorem on $x=ap\mod N$.
So I need to show, that $ap \mod p=(ap)^e\mod p$. Since ap is a multiple of p, it should be $ap\equiv 0\mod p$ and so $(ap)^e=0\mod p$. It follows that $ap\mod p=(ap)^e\mod = p= 0 \mod p$.
I now need to show, that $ap\mod q=(ap)^e\mod q$. This is the part I am struggling with. I know that $ap-bq=1$ but I have no glue how this is going to help me. I was thinking about something like $ap=(bq+1)\mod q$ but i am not sure if this works / what to do next.
You can show that $ap\mod q =(ap)^e\mod q$ by using the fact, that $ap-bq=1\Longleftrightarrow ap=bq+1$.
You know that $q|bq$ and therefor $ap\mod q = bq+1\mod q \equiv 1\mod q$.
This implicates that $(ap)^e\mod q = (bq+1)^e\mod q \equiv 1\mod q$. Therefor $ap\mod q \equiv (ap)^e\mod q.$
Now with the chinsese remainder theorem we know that $ap\equiv_N(ap)^e$.