# 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.

• Your last thought is entirely correct. It implies that $ap \equiv 1 \pmod q \implies (ap)^e \equiv 1 \pmod q$.
– user114966
Commented Jan 22, 2021 at 12:19
• Oh my god, how could i oversee that ... Of course $q|bq$ and so we have $ap\equiv1\mod q$ Commented Jan 22, 2021 at 14:25
• Can you be more specific about what your question is? We are a question-and-answer site, so we require you to articulate a specific question -- asking whether we have any reactions to some work-in-progress isn't within the scope of this site.
– D.W.
Commented Jan 23, 2021 at 3:36
• I am sorry about this. I wanted to know how to show, that $ap\equiv_p (ap)^e$. Dmitry already gave me the input needed and now i answered the question, so that other people can look it up. Commented Jan 23, 2021 at 10:20

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