I understand all of the previous steps, but I don't understand what is happening to "S2" in that the number "775" showed up.

Where does the 775 come from? I can't seem to get it, and I've tried modding it, but received the wrong answer.

The answer to this is to add the modulo to the a when a is negative. As such, this worked out fine after I added the modulo to the negative number.


El Gamal Problem Signature Problem

  • 2
    $\begingroup$ $(300 - 61\cdot 425) \equiv 775\ \pmod{880}$ $\endgroup$ – Maeher Dec 10 '18 at 8:01
  • $\begingroup$ To see it, just look at both side of $(300−61⋅425)* 553 ≡775 * 533 $. $\endgroup$ – kelalaka Dec 10 '18 at 8:02
  • $\begingroup$ Thanks, but that's not the answer I get on my calculator. Should I solve within the parentheses first and follow order of operations, then mod by 880? $\endgroup$ – J. Doe Hue Dec 10 '18 at 8:04
  • $\begingroup$ I see how you got the answer now. However, I get a negative, and my calculator doesn't process negative numbers for the MOD operation. How else can I solve this problem using the negative in the parenthesis? $\endgroup$ – J. Doe Hue Dec 10 '18 at 8:09
  • 1
    $\begingroup$ When you get negative add the modulus. $\endgroup$ – kelalaka Dec 10 '18 at 8:19

The question basically is how $300 - 61 \cdot 425 \bmod 880$ can turn into the value $775$, while a calculator returns a different value, likely $-105$. The difference is that sometimes a remainder is taken to have a value in the range $(-N, N)$ rather than $[0, N)$.

$300 - 61 \cdot 425 = -25625$. So you can say that we're trying to find a value $x \cdot 880 + y = -25625$. Now is can be $-29 \cdot 880 - 105 = -25625$ to find a value within $(-N, N)$, similar to finding $29 \cdot 880 + 105 = 25625$. $-105$ is then commonly called "the remainder"; it's what you would get if you would perform simple tail division yourself.

However, for cryptographic operations we generally try and perform operations in a group of order $N$ instead, with $N$ possible values in the range $[0, N)$. so in that case we can take $-30 \cdot 880 + 775 = -25625$, and the result will be $775$, exactly $880$ more than $-105$ in other words. This is commonly called taking the modulus, although this value can also be called a remainder.

So to find the right value within your calculator you can simply add $N = 880$ if the result is negative. A little trick in programming languages is to perform ((X % N) + N) % N, so that an if statement can be avoided. Note though that the + N may cause an overflow for large values of $N$.


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.