Return to Answer

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$. (A: Why do we need to check this? A: because you want to make sure that when you first encrypt and then decrypt you recover the original plaintext).

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

So, we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)(q-1)$ divides $ed$. Hence we can write $ed = h(p-1)(q-1)$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$. (A: Why do we need to check this? A: because you want to make sure that when you first encrypt and then decrypt you recover the original plaintext).

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

So, we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)(q-1)$ divides $ed - 1$. Hence we can write $ed = h(p-1)(q-1) + 1$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$. (A: Why do we need to check this? A: because you want to make sure that when you first encrypt and then decrypt you recover the original plaintext).

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

Ok, so we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)q-1)$ divides $ed$. Hence we can write $ed = h(p-1)(q-1)$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$. (A: Why do we need to check this? A: because you want to make sure that when you first encrypt and then decrypt you recover the original plaintext).

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

So, we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)(q-1)$ divides $ed$. Hence we can write $ed = h(p-1)(q-1)$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$.

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

Ok, so we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)q-1)$ divides $ed$. Hence we can write $ed = h(p-1)(q-1)$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$. (A: Why do we need to check this? A: because you want to make sure that when you first encrypt and then decrypt you recover the original plaintext).

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

Ok, so we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)q-1)$ divides $ed$. Hence we can write $ed = h(p-1)(q-1)$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.