Why encrypting with private and public keys produce the same result?

Let say $e = 5$, $n = 119$ and $d = 77$. If I encrypt, for example, $m=15$ I get: $$m_1 = m^e=15 ^ 5 \mod 119 = 36\qquad\text{and}\qquad m_2 =m^d= 15 ^ {77} \mod 119 = 36$$. Why? Is it always like that in RSA? Is it bad?

My question was prompted by an answer to Why hash or salt when signing? : why does this work?

• No, you wouldn't always get that - in fact it's very unlikely behaviour. If encrypting with the public and private exponents was always the same you'd be able to decrypt someone else's message $c$ by calculating $c^e=c^d=m$... Jan 8 '14 at 0:30
• I've Tried writing a short answer rather than just comments. Jan 8 '14 at 0:36
• @figlesquidge Can you please also add a comment on crypto.stackexchange.com/questions/2474/… then? Jan 8 '14 at 0:38
• What don't you understand? :/ In the case of signing, to create a signature for message $m$, we calculate $m^d$. Jan 8 '14 at 0:44

No, you wouldn't always get that - in fact it's very unlikely behavior (eg the wikipedia worked example).

If encrypting with the public and private exponents was always the same you'd be able to decrypt someone else's message $c$ by calculating $c^e=c^d=m$.

It is important to realize that (after running the RSA setup algorithm) there is algebraically no reason you couldn't swap $e$ and $d$, since $d=e^{-1}$ and thus $e=d^{-1}$ (all modulo $\varphi(N)$). However, it is unlikely that $m^d$ and $m^e$ would be equal.

In the question you link to, using the "wrong" exponent is done to cheat: it demonstrates a potential flaw in the encryption scheme. In the forgability game, we say the adversary 'wins' if they manage to create a pair $(m,s)$ such that $s$ is a valid signature for $m$, without asking the legitimate signer to calculate a signature of $m$.

So, consider what a valid message signature pair actually is (in textbook RSA signing): The pair $(m,s)$ is valid if $m=s^e\pmod N$. Now, since the public key is $(e,N)$, the adversary can cheat a bit. Instead of picking the message that he wants signed, he instead picks the signature. Having picked $s$, he now calculates $m:=s^e \pmod N$. This leaves him with the pair $(m,s)$, which by construction must be valid.

Notice that he doesn't have a clue what the message $m$ actually says, but we do know that $s$ is a valid signature for it. This is why real-world RSA signing uses a secure padding scheme: a message $m$ created in the way I describe above is very unlikely to have valid padding.

• Omg I thought s is a message... Jan 8 '14 at 6:10
• "all modulo $N$", modulo $\lambda(N)$ or modulo $\phi(N)$ not, modulo $N$. Jan 8 '14 at 17:18
• Cheers, good reason not to answer in the middle of the night Jan 8 '14 at 17:19