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?