Firmare con ElGamal

Vediamo ora come arrivare al medesimo risultato utilizzando il critto-sistema ElGamal. Per firmare il medesimo contratto Alice deve scegliere un numero grande e primo p e una radice primitiva a . Successivamente deve anche sceglie un numero b tale che:
1 \le b \le (p-2)

Alice calcola il numero c :
c = a^b \pmod{p}

Alice sceglie poi il numero k , in modo che sia: 1 \le k \le (p-2) e co-primo con p-1 : \text{MCD}(k, p-1) = 1

Per firmare il contratto Alice dovrà calcolare:
x = a^k \pmod{p}
y = k^{-1} \cdot (m - b \cdot x) \pmod{(p-1)}

La firma verrà garantita dalla tripletta (m, x, y) . Se Bob volesse controllare la firma di Alice dovrebbe scaricare le triplette (m, x, y) e (p, a, c) e successivamente calcolare:
v_1 = c^x \cdot x^y \pmod{p}
v_2 = a^m \pmod{p}

e infine confrontare v_1 con v_2 :
v_1 = v_2

Dimostrazione matematica

Dimostriamo matematicamente la funzionalità dell’algoritmo:
v_2 = a^m

y = k^{-1} \cdot (m-b \cdot x) \pmod{p-1}
y \cdot k = m - b \cdot x \pmod{p-1}
m = y \cdot k + b \cdot x \pmod{p}

v_2 = a^m = a^{y \cdot k + b \cdot x} = (a^k)^y + (a^b)^x = r^y + c^x = v_1 \pmod{p}

Il sistema di firma digitale al momento più utilizzato è DSA, esso deriva dall’algoritmo di firma tramite ElGamal visto in precedenza.