Whats wrong with my El Gamal signature example

Question

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?

Answer 1

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.

Answer 2

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

You can use this calculator for example.