2
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by mikeazo Jun 16 '14 at 16:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 Jun 16 '14 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 Jun 16 '14 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$ – CGFoX Jun 17 '14 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 Jun 17 '14 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 Jun 19 '14 at 13:47