Schema di firma ElGamal

Lo schema di firma ElGamal è un crittosistema di firma digitale basato sulla presunta difficoltà computazionale del calcolo di logaritmi discreti. È stato descritto da Taher Elgamal nel 1984.

L'originale algoritmo di firma di Elgamal è raramente usato nella pratica, in favore di una variante sviluppata dalla NSA nota come Digital Signature Algorithm. Esistono molte altre varianti. Lo schema di firma ElGamal non dev'essere confuso con l'omonimo sistema di cifratura a chiave pubblica, anch'esso proposto da Taher Elgamal.

Parametri di sistema

• Sia $H$ una funzione di hash resistente alle collisioni.
• Sia $p$ un numero primo sufficientemente grande, tale che calcolare il suo logaritmo discreto modulo $p$ risulti complesso.
• Sia $g<p$ un generatore scelto arbitrariamente nel gruppo di interi modulo p $Z_{p}^{*}$.

Generazione della chiave

L'autore della firma compie una sola volta i seguenti passi:

• Scegliere un numero casuale $x$ tale che $1<x<p-2$.
• Calcolare $y=g^{x}\mod p$.
• La chiave pubblica è $y$.
• La chiave privata $x$.

Generazione della firma

Per firmare un messaggio $m$, l'utente compie i seguenti passi:

• Scegliere un numero casuale $k$ tale che $1<k<p-1$ e $gcd(k,p-1)=1$ (ovvero, $k$ e $p-1$ siano coprimi).
• Calcolare $r\,\equiv \,g^{k}{\pmod {p}}$.
• Calcolare $s\,\equiv \,(H(m)-xr)k^{-1}{\pmod {p-1}}$.
• Se $s=0$ ricominciare.

La coppia $(r,s)$ sarà la firma digitale di $m$.

Verifica

Una firma $(r,s)$ di un messaggio $m$ è accettata se le seguenti condizioni di verifica sono soddisfatte:

• $0<r<p$ e $0<s<p-1$.
• $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$

Correttezza

L'algoritmo è corretto nel senso che una firma correttamente generata verrà sempre accettata se verificata come sopra.

La generazione della firma implica che:

$H(m)\,\equiv \,xr+sk{\pmod {p-1}}.$

Per il piccolo teorema di Fermat:

${\begin{aligned}g^{H(m)}&\equiv g^{xr}g^{ks}\\&\equiv (g^{x})^{r}(g^{k})^{s}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{aligned}}$

Sicurezza

Un utente terzo può falsificare la firma entrando a conoscenza della chiave segreta $x$ o trovando collisioni nella funzione di hash $H(m)\equiv H(M){\pmod {p-1}}$. Entrambi i problemi sono ritenuti difficili.

Il firmatario deve stare attento a scegliere i valori di $k$ in maniera sufficientemente casuale per ogni firma e deve essere sicuro che $k$, o qualunque informazione parziale riguardo esso, non venga rivelata. Altrimenti, potrebbe essere più semplice per un attaccante dedurre la chiave $x$, talvolta abbastanza da permettere un attacco praticabile. In particolare, se due messaggi sono inviati usando lo stesso valore di $k$ e la stessa chiave, allora l'attaccante può direttamente calcolare $x$.

Falsificazione esistenziale

La pubblicazione originale non prevedeva una funzione crittografica di hash come parametro di sistema. Il messaggio $m$ era usato direttamente nell'algoritmo al posto di $H(m)$. Questo permetteva un attacco noto come falsificazione esistenziale, come descritto nella sezione IV dell'articolo. Pointcheval e Stern hanno generalizzato questo caso descrivendo due distinti livelli di falsificazione:

1. Falsificazione ad un parametro. Sia $1<e<p-1$ un numero casuale. Se $r=g^{e}y{\pmod {p}}$ e $s=-r{\pmod {p-1}}$, la coppia $(r,s)$ è una firma valida per il messaggio $m=es{\pmod {p-1}}$.
2. Falsificazione a due parametri. Siano $1<e,v<p-1$ due numeri casuali e sia $\gcd(v,p-1)=1$. Se $r=g^{e}y^{v}{\pmod {p}}$ e $s=-rv^{-1}{\pmod {p-1}}$, la coppia $(r,s)$ è una firma valida per il messaggio $m=es{\pmod {p-1}}$.

Bibliografia

• (EN) T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in IEEE Trans Inf Theory, vol. 31, n. 4, 1985, pp. 469–472. URL consultato il 17 febbraio 2021.

Voci correlate

• Aritmetica modulare
• Digital Signature Algorithm
• Elliptic Curve Digital Signature Algorithm
• ElGamal
• Firma di Schnorr