ElGamal Public Key Cryptosystem and Digital Signature Scheme

Question

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this:

A) P=23, g=5.

B) x=3, then y=10 (for 53 mod 23=10 ).

C) Sign for the message M=8.

D) Select k=5 between 1 and 22 (P-1).

E) Compute r = gk mod P = 55 mod 23 = 20.

F) Compute s = k-1(M-xr) mod (P-1) = 5-1(8-3×20) mod 22 = 9×14 mod 22 = 16.

G) Verification:

   gM= 58 mod 23 =16

   (rs)(yr) mod P = 2016 × 1020 mod 23= 13×3 mod 23 = 16

In (F) section you can see:

s = k-1(M-xr) mod (P-1)

s = 5-1(8-3×20) mod 22 --->> This is the hard part for me, I don't understand how "5-1(8-3×20)" can transform in "9×14"

s = 9×14 mod 22

s = 16.

This isn't a simple example for me, but I'm working in that algorithm and I really wanna now how this work Mathematically talking.

Thanks

Answer 1

$$5^{-1} \pmod{22} = 9$$

This is a modular inverse.

$$(8 - 3 \times 20) \pmod{22} = 14$$

Note:

• $-60 \pmod{22} = 6$, and
• $(8 + 6) \pmod{22} = 14$.