# Whats wrong with my El Gamal signature example

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?

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.

• Thank you, my understanding of k^-1 was incorrect. You're a champion Jun 2, 2019 at 14:14

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

You can use this calculator for example.