2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$... $\endgroup$ – figlesquidge Jan 8 '14 at 0:30
  • $\begingroup$ @figlesquidge Are you sure? What about this answer? crypto.stackexchange.com/a/2480/8151, this uses the same idea. $\endgroup$ – evening Jan 8 '14 at 0:31
  • $\begingroup$ I've Tried writing a short answer rather than just comments. $\endgroup$ – figlesquidge Jan 8 '14 at 0:36
  • $\begingroup$ @figlesquidge Can you please also add a comment on crypto.stackexchange.com/questions/2474/… then? $\endgroup$ – evening Jan 8 '14 at 0:38
  • $\begingroup$ What don't you understand? :/ In the case of signing, to create a signature for message $m$, we calculate $m^d$. $\endgroup$ – figlesquidge Jan 8 '14 at 0:44
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.