3
$\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$
8
  • $\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$ Jan 8, 2014 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, 2014 at 0:31
  • $\begingroup$ I've Tried writing a short answer rather than just comments. $\endgroup$ Jan 8, 2014 at 0:36
  • $\begingroup$ @figlesquidge Can you please also add a comment on crypto.stackexchange.com/questions/2474/… then? $\endgroup$
    – evening
    Jan 8, 2014 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$ Jan 8, 2014 at 0:44

1 Answer 1

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$
3
  • $\begingroup$ Omg I thought s is a message... $\endgroup$
    – evening
    Jan 8, 2014 at 6:10
  • 1
    $\begingroup$ "all modulo $N$", modulo $\lambda(N)$ or modulo $\phi(N)$ not, modulo $N$. $\endgroup$ Jan 8, 2014 at 17:18
  • 1
    $\begingroup$ Cheers, good reason not to answer in the middle of the night $\endgroup$ Jan 8, 2014 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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