Prove that $D(E(x))=(E(x))^d \mod N=(x^e \mod N)^d \mod N=x$

Question

I am currently studying for my next semester's course in mathematics and I have this problem. I know that I have to use Fermat's Little Theorem, but I am lost as to how to start. Also, what property of modulo can I use for exponentiating $a$ in $a \equiv b (\mod p)$

Answer 1

By the looks of things, this is the definition of RSA Encryption. I suggest you watch this 4 part series on Khan Academy which might clear things up for you

---

Put simply though, when encrypting $m$, we compute $$c \equiv m^e \mod N$$ for $N=pq$ where $p$ and $q$ are prime

We then want to find a value of $d$ such that $$c^d\mod N \equiv m$$

That is to say, we want $$\begin{align}\left(m^e\mod N\right)^d \mod N &\equiv m\\ m^{e^d}\mod N &\equiv m \\ m^{e\times d} \mod N &\equiv m \end{align}$$

For any choice of $e$, we want a way of finding $d$ such that this equivalence is true

We use Euler's Phi Function to find $\varphi(N)=(p-1)(q-1)$.

This is true as $p$ and $q$ are coprime, so $$\varphi(N)\equiv\varphi(p)\varphi(q)$$

As $p$ and $q$ are prime, then $$\varphi(p)\varphi(q)=(p-1)(q-1)$$

We then use Euler's Theorem to say that $$\begin{align}m^{\varphi(N)} & \equiv 1\mod N \\ m^{k\times \varphi(N)} &\equiv 1\mod N \tag{as $1^k=1$} \\ m\times m^{k\times\varphi(N)} & \equiv m\mod N\tag{as $1\times m = m$} \\ m^{k\times \varphi(N) + 1} &\equiv m\mod N\end{align}$$

We now have a function for finding $e\times d$ which depends on $\varphi(N)$:

$$\begin{align}m^{e\times d}\mod N & \equiv m^{k\times \varphi(N) + 1}\mod N \\ e\times d&\equiv k\times \varphi(N)+1 \\ e\times d &\equiv 1 \mod \varphi(N) \\ d &\equiv e^{-1}\mod \varphi(N) \end{align}$$

Hopefully this gives you somewhere to start