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 una funzione di hash resistente alle collisioni. Sia un numero primo sufficientemente grande, tale che calcolare il suo logaritmo discreto modulo risulti complesso. Sia un generatore scelto arbitrariamente nel gruppo di interi modulo p .
Generazione della chiave L'autore della firma compie una sola volta i seguenti passi: Scegliere un numero casuale tale che . Calcolare . La chiave pubblica è . La chiave privata .
Generazione della firma Per firmare un messaggio , l'utente compie i seguenti passi: Scegliere un numero casuale tale che e (ovvero, e siano coprimi). Calcolare . Calcolare . Se ricominciare. La coppia sarà la firma digitale di .
Verifica Una firma di un messaggio è accettata se le seguenti condizioni di verifica sono soddisfatte: e .
Correttezza L'algoritmo è corretto nel senso che una firma correttamente generata verrà sempre accettata se verificata come sopra.
La generazione della firma implica che:
Per il piccolo teorema di Fermat:
Sicurezza Un utente terzo può falsificare la firma entrando a conoscenza della chiave segreta o trovando collisioni nella funzione di hash . Entrambi i problemi sono ritenuti difficili.
Il firmatario deve stare attento a scegliere i valori di in maniera sufficientemente casuale per ogni firma e deve essere sicuro che , o qualunque informazione parziale riguardo esso, non venga rivelata. Altrimenti, potrebbe essere più semplice per un attaccante dedurre la chiave , talvolta abbastanza da permettere un attacco praticabile. In particolare, se due messaggi sono inviati usando lo stesso valore di e la stessa chiave, allora l'attaccante può direttamente calcolare .
Falsificazione esistenziale La pubblicazione originale non prevedeva una funzione crittografica di hash come parametro di sistema. Il messaggio era usato direttamente nell'algoritmo al posto di . 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: Falsificazione ad un parametro. Sia un numero casuale. Se e , la coppia è una firma valida per il messaggio . Falsificazione a due parametri. Siano due numeri casuali e sia . Se e , la coppia è una firma valida per il messaggio .
Note
Bibliografia
Voci correlate Aritmetica modulare Digital Signature Algorithm Elliptic Curve Digital Signature Algorithm ElGamal Firma di Schnorr
ElGamal