MHB Why do we get like that the message?

  • Thread starter Thread starter evinda
  • Start date Start date
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)
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Namaste & G'day Postulate: A strongly-knit team wins on average over a less knit one Fundamentals: - Two teams face off with 4 players each - A polo team consists of players that each have assigned to them a measure of their ability (called a "Handicap" - 10 is highest, -2 lowest) I attempted to measure close-knitness of a team in terms of standard deviation (SD) of handicaps of the players. Failure: It turns out that, more often than, a team with a higher SD wins. In my language, that...

Similar threads

Back
Top