Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 4 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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