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 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 .[1]
Falsificazione esistenziale
La pubblicazione originale[1] 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:[3]
- 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
- ^ a b c Elgamal, 1985.
- ^ (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.
- ^ (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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Ambox_padlock_green.svg/25px-Ambox_padlock_green.svg.png)