MHB Why do we get like that the message?

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion explains the RSA encryption process, detailing the selection of two prime numbers, the computation of n and φ(n), and the generation of public and private keys. It addresses the relationship between the encryption and decryption exponents, specifically why M raised to the power of ed equals M modulo n, despite ed being congruent to 1 modulo φ(n). This relationship is derived from Euler's theorem, which states that if M is coprime to n, then M raised to φ(n) is congruent to 1 modulo n. The clarification provided helps solidify the understanding of RSA's mathematical foundation.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

When we encrypt with RSA, we choose two large arbitrary prime numbers $p$ and $q$.
We choose $n=pq$. We compute $\phi(n)=(p-1)(q-1)$.
We choose a number $e>1$ such that $e^{\phi(n)}\equiv 1 \pmod{n}$.

We compute the inverse of $e$, $d \equiv e^{-1}\pmod{\phi(n)}$.
The public key is $(n,e)$ and the private key $(n,d)$.

We encrypt a message $M$ as follows:

$$C(M)=M^e \mod{n}$$

We decrypt the message as follows:

$$M(C)=C^{d} \mod{n}$$

My question is the following:

Why do we have that $M^{ed}=M \mod{n}$, given that $ed=1 \mod{\phi{n}}$ and not modulo $n$ ? (Thinking)
 
Physics news on Phys.org
Hey evinda!

It's a consequence of Euler's theorem that says that if $a$ is coprime with $n$ that then $a^{\phi(n)}=1\bmod n$.

Let $k$ be such that $ed = k\phi(n) + 1$.
If $M$ is coprime with $n$ then it follows that:
$$M^{ed} = M^{k\phi(n) + 1} = (M^{\phi(n)})^k\cdot M = M\bmod n$$
🤔
 
Klaas van Aarsen said:
Hey evinda!

It's a consequence of Euler's theorem that says that if $a$ is coprime with $n$ that then $a^{\phi(n)}=1\bmod n$.

Let $k$ be such that $ed = k\phi(n) + 1$.
If $M$ is coprime with $n$ then it follows that:
$$M^{ed} = M^{k\phi(n) + 1} = (M^{\phi(n)})^k\cdot M = M\bmod n$$
🤔

Ah, I see... Thanks a lot! (Sun)
 

Similar threads

Back
Top