Trying to solve problem with verifying a message through the ElGamal signature scheme and I end up getting two different values.

I'm given a prime number p=881 , e1=3, d=60 , and a random value r=11 . I have to

a) Find e2 and the signature of the message M=300 .

b) Verify the signature.

I'm stuck on part b verifying V1 and V2 I get two different answers and I'm unsure whether I'm doing the calculations wrong or if that's the answer.

I solved e2 = 3^60 mod 881 = 490, S1 = 3^11 mod 881 = 66, S2 = (300 - 60*66)11^-1 mod 880 = 740 mod 880 = 740,

V1 = 3^300 mod 881 = 102 V2 = (490^66)(66^740) mod 881 = 494, therefore, the signature is not verified

Is this the correct answer? There's a lot of calculations going on and I'd just like to know.

Here's the diagram showing the formulas for each calculation along the ElGamal signature process.

  • 1
    $\begingroup$ V1 and V2 should be equal. Make sure you compute modular inverse, with the appropriate modulus. Are you sure you are allowed to post homework? If so, and you are still stuck, edit the question to detail all your calculations. Likely, you'll find your error meanwhile. $\endgroup$
    – fgrieu
    Nov 24, 2023 at 18:23
  • $\begingroup$ More precise hint than the one above: In ElGamal signature, calculations of $S_1$ and $V_2$ are modulo $p$, and (thus) calculation of $S_2$ is modulo $p-1$. It follows the choice of $r$ is incorrect w.r.t. $p$, because it leaves $r^{-1}$ undefined, thus $S_2$ undefined and the proposed value for $S_2$ invalid. The requirement on $r$ is stated in red in the figure (with a typo: read "relatively prime to" or "coprime with" where there is "relative prime to"). I recommend that you make an answer to your own question. $\endgroup$
    – fgrieu
    Nov 25, 2023 at 18:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.