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.^[1]

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.^[2] 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 ${\displaystyle H}$ una funzione di hash resistente alle collisioni.
• Sia ${\displaystyle p}$ un numero primo sufficientemente grande, tale che calcolare il suo logaritmo discreto modulo ${\displaystyle p}$ risulti complesso.
• Sia ${\displaystyle g<p}$ un generatore scelto arbitrariamente nel gruppo di interi modulo p ${\displaystyle Z_{p}^{*}}$.

Generazione della chiave

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

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

Generazione della firma

Per firmare un messaggio ${\displaystyle m}$, l'utente compie i seguenti passi:

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

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

Verifica

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

• ${\displaystyle 0<r<p}$ e ${\displaystyle 0<s<p-1}$.
• ${\displaystyle 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:

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

Per il piccolo teorema di Fermat:

${\displaystyle {\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 ${\displaystyle x}$ o trovando collisioni nella funzione di hash ${\displaystyle H(m)\equiv H(M){\pmod {p-1}}}$. Entrambi i problemi sono ritenuti difficili.

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

Falsificazione esistenziale

La pubblicazione originale^[1] non prevedeva una funzione crittografica di hash come parametro di sistema. Il messaggio ${\displaystyle m}$ era usato direttamente nell'algoritmo al posto di ${\displaystyle 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:^[3]

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

Note

1. Elgamal, 1985.
2. (EN) K. Nyberg, R. A. Rueppel, Message recovery for signature schemes based on the discrete logarithm problem, in Designs, Codes and Cryptography, vol. 7, n. 1-2, 1996, pp. 61–81, DOI:10.1007/BF00125076.
3. (EN) David Pointcheval e Jacques Stern, Security Arguments for Digital Signatures and Blind Signatures (PDF), in J Cryptology, vol. 13, n. 3, 2000, pp. 361–396. URL consultato il 4 ottobre 2018 (archiviato dall'url originale il 5 dicembre 2014).

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

Portale Crittografia: accedi alle voci di Wikipedia che trattano di crittografia