RSA: Common modulus attack problem [duplicate]

I understand in theory how the common modulus attack works (as described here: how to use common modulus attack?)

Though, I did not understand completely how it worked with a negative $s_i$. Since $e_bs_1+e_cs_2=1$ one of the $s_i$ will be negative, so when I calculate $C_j^{s_i}$ it will be a fraction and not out of $\mathbb{Z}$.

From what I learned from the comments the trick is to calculate $(C_j^{-s_i})^{-1}=C_j^{s_i}$ instead. That way $-s_i$ is positive and $C_j^{-s_i}$ can be computed easily as well es the inverse $(C_j^{-s_i})^{-1}$ (using the Extended Euclidean algorithm). This solves my problem.

(I edited this question to specify my problem, answer it and to explain how it is different from how to use common modulus attack? in the hope that it won't be marked as duplicate anymore.)

marked as duplicate by mikeazoJun 16 '14 at 16:42

• As for what $C_j^{s_i}$ might mean if $s_i < 0$, well, remember that we're doing this modulo $N$. We have $a^{b} a^{c} = a^{b+c}$ for any $a, b, c$, so we have $a^{-b} a^{b} = a^0 = 1$. So, by $a^{-b}$, we mean that value which, when multiplied by $a^b$ (modulo $N$), we get one. And, we can find such values using the Extended Euclidean method. Does that help? – poncho Jun 16 '14 at 21:01
• Yes, I wasn't sure if the $s_i$ were modulo N as well. But still, I struggle calculating the result for a specific example. I will update the question adding that example and my problem with it. – CGFoX Jun 17 '14 at 8:19
• For the one that is negative, say $s_2$, you should calculate $c^{-s_2}\bmod{n}$ (that way $s_2$ is positive), then find the modular inverse of that value (mod n). – mikeazo Jun 17 '14 at 12:02