9
$\begingroup$

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!!!

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Pornin Jan 10 '12 at 13:03
  • $\begingroup$ 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)$. $\endgroup$ – user46 Jan 10 '12 at 13:58
  • $\begingroup$ Can you please help me out, regarding this problem : crypto.stackexchange.com/questions/71601/… $\endgroup$ – Subham Ghosh Jun 27 at 3:16
13
$\begingroup$

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

$c_2 \equiv m^{e_2} \bmod 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 \bmod 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} \bmod n$ (i.e., the modular inverse of $c_2$)

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

Update to show details of $m\equiv c_1^a\cdot c_2^b\bmod n$. All math below done modulo $n$.

$$ c_1^a\cdot c_2^b\\ (m^{e_1})^a\cdot (m^{e_2})^b\\ m^{e_1a}\cdot m^{e_2b}\\ m^{e_1a+e_2b}\\ m^1\\ m $$

$\endgroup$

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.