Guide

8.4 – schema di firma con ElGamal

A differenza di prima l’ElGamal non è commutativo, in ogni modo esiste uno schema di firma molto simile.

Prima di tutto bisogna costruirsi la chiave:

- Si sceglie un numero primo p in comune e una radice primitiva/generatore del gruppo di riferimento a pubblico, poi ogni utente sceglie un numero casuale x privato.

- La chiave pubblica è (y, a, p) dove y = ax mod p

- La chiave privata è (x)

Per firmare un messaggio M:

- si sceglie un numero casuale k che sia primo con p – 1, da distruggere dopo l’uso.

- si calcola K = ak mod p

- siccome M = x*K + k*S mod (p-1) allora si trova S = k-1(M – x*K) mod (p-1)tramite l’algoritmo esteso di Euclide.

- la firma è (K, S)(notare che l’ElGamal raddoppia la grandezza)

Per verificare una firma (K, S) su un messaggio M:

- bisogna confermare quest’identità yK*KSmod p = aMmod p.

I tipi di attacco noti per lo schema sono il metodo di calcolo dell’indice (index-calculus attack), l’attacco Pohlig-Hellman, e quelli basati su generatori deboli, comunque non efficaci se si usa un modulo p di almeno 768 bit (1024 o più grandi sono però consigliati). Notare che l’algoritmo originariamente è descritto nell’insieme del gruppo moltiplicativo Zp*, ma può essere generalizzato in maniera che lavori su un generico gruppo abeliano finito G, come quello costruito da un insieme di punti su una curva ellittica sopra un campo finito Fq*.