2
$\begingroup$

I'm trying to digitally sign a message m using El Gamal. So far I've been unable to verify the digital signature ive made using El Gamal.

I am using prime number, p = 8369. prime root g = 3031. Private key parameter x = 61. and the message m = 9876

I am calculating y and r to be:

  • y = 3031^61 mod 8369 = 3400
  • r = 3031^11 mod 8369 = 2954

Signed message s, s = k^-1 (m – xr) mod (p-1)

  • s = 11^-1(9876 – 61*2954) mod 8368
  • s = 13788/11 which cannot be right

I then tried removing the inverse power from 11 which I had seen in another example which produced the following

  • s = 11(9876 – 61*2954) mod 8368 = 934

When i used v = g^m mod p and w = y^r r^s mod p I got

  • v = 3031^9876 mod 8369 = 6346
  • w = 3400^2954 * 2954^934 mod 8369 = 855

V and W dont match meaning the signature is invalid and I've made a mistake in my verification. Where did I go wrong and am i on the right track?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

In general case, $k^{-1}$ is equal to $x$ such that $x \cdot k=1$. In your question, to computing $11^{-1}$, you must find $x$ such that $x\cdot11=1 \pmod {8368}$. You can compute $x$ by using the extended Euclidean algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, my understanding of k^-1 was incorrect. You're a champion $\endgroup$
    – archhmod
    Jun 2, 2019 at 14:14
0
$\begingroup$

In this case it should be 11^(-1)= 3043 mod 8368

You can use this calculator for example.

Improve this answer
$\endgroup$

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.