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.)

  • 1
    $\begingroup$ Duplicate of how to use common modulus attack?. P.S. (from the help center) "please provide an indication of what you are not understanding/need clarification on and your attempts at solving it, so we have a clear indication of where you are stuck. This goes for all questions, not just homework. If you have just written out your assignment, your question will be closed." $\endgroup$
    – mikeazo
    Commented Jun 16, 2014 at 16:42
  • 2
    $\begingroup$ 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? $\endgroup$
    – poncho
    Commented Jun 16, 2014 at 21:01
  • $\begingroup$ 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. $\endgroup$ Commented Jun 17, 2014 at 8:19
  • 2
    $\begingroup$ 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). $\endgroup$
    – mikeazo
    Commented Jun 17, 2014 at 12:02
  • 1
    $\begingroup$ @CGFoX Thanks for updating. I'm still hesitant to reopen the question. First, questions shouldn't have answers in the question. Second, if you remove the answer, you are right, it probably shouldn't be considered a duplicate, but the new question is off topic as it is more about math than crypto (yes, the application is crypto, but it is really the math). $\endgroup$
    – mikeazo
    Commented Jun 19, 2014 at 13:47


Browse other questions tagged or ask your own question.