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.

Suppose we have two people: Smith and Jones. Smith public key is e=9, n=179 and Jones public key is e=13, n=179. Bob sends to them a message $M$.

The encrypted message $C_s$ to Smith is 32.

The encrypted message $C_j$ to Jones is 127

I tried to resolve this problem with no luck.

First I put both of them as an equation and tried to play with the module, multiplying and adding, but I can't retrieve the solution. I know there is a way to resolve it but I haven't found it anywhere.


EDIT: Is not a realistic situation. Is just for practice. This is the primitive RSA. It has no padding.

I'm beginning to think that the problem is wrong maybe because the results I get are not correct.

This is the original problem text:

Imagine that you are a CIA double agent. As good spy, you have discover that the agents Smith and Jones share the same modulo in their respective RSA public keys, namely ($e_s$ = 9, n = 179) and ($e_j$ = 13, n = 179). After some days sniffing the network, you see that the CIA director has sent the same message m to both agents. Concretely he has sent $c_s$ = 32 and $c_j$ = 127. Can you recover the original message m?.

Solution m = 10

Resolution by me:

So I have the following equation:

$c_s$ = $m^9$ $mod$ 179

$c_j$ = $m^{13}$ $mod$ 179

And I began to use the extended Euclidean algorithm:

9*$a$ + 13*$b$ = $gcd$(9,13) which gives me:

$a$ = 3 and $b$ = -2

As $b$ is negative, we calculate:

$i$ $=$ $c_j^{-1}mod179$

the inverse of $c_j$ (127) which is $-31$

And finally:

$M$ = $c_s^a$ * $i^{-b}$ $mod$ n

$M = 32^3*{-31}^2$ $mod$ $179$ $=$ $10$

Great! thanks!!!

share|improve this question
2  
Note that such "cracking" entails using RSA without padding (so it is not "the" RSA, only the core mathematical operation, but known to have a number of weaknesses), and also that Smith and Jones share the same modulus, which means that they have the "same" private key (at least they both know the factorization of the modulus, so they can compute each other's private key). That's not a realistic situation. –  Thomas Pornin Jan 10 '12 at 13:03
    
I know it's just an example, but to extend Thomas' point, also note the modulus itself is prime, allowing you to decrypt a single message by computing the inverse of $e$ - in other words, you don't actually need the same message to be sent to two different people in this scenario - the inverse of $e=13$ is $d=137$ and you can compute $127^{137} \equiv 10 \mod(179)$. –  Ninefingers Jan 10 '12 at 13:58
add comment

1 Answer 1

up vote 5 down vote accepted

I'm getting the following information from here (slide 26).

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv m^{e_2} \mod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \mod n$

Note: In practice, either $a$ or $b$ will be negative. WLOG, let $b$ be negative. This leads to problems in the above equation. To get around this, use the following computation.

Let $i\equiv c_2^{-1} \mod n$ (i.e., the modular inverse of $c_2$)

$m\equiv c_1^a\cdot i^{-b} \mod n$

share|improve this answer
    
Oh my god. That's why it fails! Thanks so much for your help, I'll resolve it right now! –  Tomas Jan 10 '12 at 13:37
add comment

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.