Cifrari a chiave pubblica
Il cifrario ElGamal
Il cifrario RSA - Algoritmo DH → ElGamal: demo

Storia

Questo cifrario fu proposto nel 1985 da Taher Elgamal*, dal quale ha preso il nome, riprendendo l'idea base dell'algoritmo DH, la intrattabilità del calcolo del logaritmo discreto in aritmetiche modulari di grande dimensione. A differenza di DH che si limita a generare una chiave condivisa, ElGamal è un vero e proprio cifrario, e permette di cifrare testi brevi, essendo molto più lento dei cifrari a chiave segreta come DES e AES; di fatto poi è utile soprattutto per cifrare parole chiave come le password e in pratica lo scopo è lo stesso di DH.

ElGamal non riuscì a spodestare RSA come principale cifrario a chiave pubblica, ma fu usato dal sistema PGP, Pretty Good Privacy

Le procedure di cifra e decifra sono descritte usando l'esempio seguente, che per semplicità si limita a cifrare una sola letter la J.

Esempio

Innanzitutto Alice e Bruno concordano due numeri pubblici $N$ e $g$:

  1. Alice e Bruno scelgono pubblicamente un numero primo per esempio $N = 257$ e un generatore dell'aritmetica modula $N$, per esempio $g =5$;
  2. Alice genera un numero casuale minore di 257, per esempio a = 121, da mantenere segreto, e lo usa come esponente per calcolare $A = g^a = 5^{121} \pmod {257}= 86$

Ora Bruno può inviare un messaggio $M$ cifrato come segue:

  1. Bruno scrive un messaggio $M$ e lo converte in un numero $m$ usando una funzione $f$ biiettiva, che può per esempio essere il codice ASCII a 8 bit; prendendo la lettera J come messaggio $M$ ed essendo il codice ASCII di J il numero $74$ si ha $m = f('J') = 74$.
  2. Bruno genera un numero casuale $b \lt N$ per esempio $147$ e lo usa come esponente per calcolare la chiave pubblica B come potenza $B = g^b \pmod N $, quindi $B = 5^{147} \pmod {257}= 145 $
  3. Bruno, conoscendo $A$ che è pubblico e il suo esponente segreto $b$ può calcolare la chiave segreta $ S = A^{b} \pmod N = 86^{147} \pmod {257} = 94 $
  4. Bruno invia per un canale pubblico il cifrato composto da una coppia di numeri: il primo è $c_1=B=g^b = 145$, il secondo è $c2=mS \pmod N = 74 \times 94 \pmod {257} = 17$; la coppia è quindi $(c_1,c_2)=(145,17)$

Alice riceve quindi la coppia $(145,17)$ e la decifra come segue:

  1. Alice recupera la chiave segreta calcolando $s=c_1^a=145^{17}= 94$, infatti per le proprietà delle potenze, valide anche in aritmetica modulare, si ha $c_1^a =(g^b)^a = g^{ab}=(g^a)^b=A^b=S$.
  2. Alice calcola l'inverso di $s$ : $s^{−1} \pmod {N}=94^{-1} \pmod {257}=216$
  3. Alice calcola ora $m=c_2 s^{−1}\pmod N = 17 \times 216 \pmod {257} = 74$ e quindi il carattere ASCII $74$ che è J

È notevole il fatto che il cifrario non è deterministico, nel senso che dipendendo anche da un numero casuale, alla stessa lettera potranno di volta in volta corrispondere numeri diversi, detto in altri termini la funzione cifrante non è univoca, mentre la funzione decifrante è necessariamente univoca, e quindi non vi sono problemi. Una situazione che ricorda quella degli omofoni usati nella crittografia classica e che avrebbero dovuto essere appunto usati a casaccio!

Alla pagina ElGamal: demo è possibile provare il cifrario in modo interattivo, verificando anche la predetta caratteristica..

Sicurezza

La cosa importante per la sicurezza è che un terzo che intercettasse i quattro numeri pubblici $N, g, A, B$ non sarebbe in grado di ottenere la chiave $k = g^{ab} \mod N$ non conoscendo né $a$ né $b$. In realtà basterebbe calcolare i logaritmi $a = \log_g{A} \quad e \quad b = \log_g{B}$ ma il calcolo del logaritmo discreto è computazionalmente proibitivo per numeri molto grandi (1024 bit e oltre).

Come altri sistemi a chiave pubblica, anche ElGamal è esposto all'attacco del terzo uomo interposto. Nel nostro esempio immaginiamo che Carlo intercetti il numero A che Alice invia a Bruno e, fingendo di essere Bruno, generi un suo numero B e lo invii ad Alice. A questo punto Alice e Carlo generano la chiave segreta k e comunicano via DES; e Carlo può tranquillamente leggere tutti i messaggi che Alice crede di inviare a Bruno! Peggio ancora: Carlo può ripetere il gioco anche con Bruno fingendosi Alice e di qui in avanti, intercettare e leggere tutta la corrispondenza tra gli inconsapevoli Alice e Bruno.

Per prevenire simili attacchi la soluzione è anche qui quella di usare un ente certificatore che garantisca l'identità dei corrispondenti. Alice e Bruno potranno p.es. identificarsi con un meccanismo di firma digitale, utilizzando le chiavi pubbliche fornite dall'ente certificatore.

È quello che capita per il protocollo https di Internet, che richiede un certificato SSL emesso da un ente autorizzato, e contenente le chiavi RSA o in questo caso ElGamal. Tra l'altro fu proprio Taher Elgamal a ideare i certificati SSL.

Riferimenti bibliografici
Siti e pagine web
X Taher Elgamal, Il Cairo 18-08-1955, è un ingegnere egiziano emigrato negli USA, che si è occupato principalmente della sicurezza informatica e quindi di crittografia. Il nome che in arabo si scrive (da destra a sinistra): طاهر الجمل viene variamente trascritto come El Gamal, ElGamal o Elgamal. Per evitare confusioni si usa scrivere Elgamal il cognome della persona, come lo scrive lui stesso, ElGamal invece è il nome del cifrario.