Cifrario ElGamal: demo

Crittografia a chiave pubblica - Il cifrario ElGamal

Cifrario ElGamal: demo con N = 257 , generatore = 5

Questa pagina permette di simulare il comportamento della cifra ElGamal usando inevitabilmente numeri molto più piccoli di quelli usati realmente. Va intesa quindi solo come un demo.

Secondo consuetudine immaginiamo due persone Alice e Bruno, che devono generare una chiave segreta.

Nella tabella a destra si leggono i vari passi necessari per cifrare e nelle ultime due righe la chiave generata.

Inserimento dati
$255 \lt N \lt 511$ (Numero primo )
$ g \lt N $ (Generatore)
$M$ Carattere (ASCII) in chiaro

Facendo ripetutamente clic qui sopra, senza cambiare nulla, si noterà che le cifre $c_1, c_2$ cambiano ogni volta, dipendendo anche da numeri generati a caso. Questo fatto si sintetizza dicendo che ElGamal è un algoritmo probabilistico, non deterministico.

Alice e Bruno generano la chiave
Descrizione	Variabile/i	Formula	Valore/i
Alice e Bruno scelgono pubblicamente un numero primo $N$ e un suo generatore $g$	N numero primo g generatore	---	$ N = 257 \\ g =5$
Alice genera un numero casuale $a \lt N$ e lo usa come esponente per calcolare $A$, da pubblicare	$a \lt N$ casuale	$A = g^a \pmod N$	$\color{red}{a = 136} \\ \color{green}{A =15}$
Bruno cifra il messaggio
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	$M$ testo $m$ numero	$m = f(M)$	$M = A\\ m =65$
Bruno genera un numero casuale $b \lt N$ e lo usa come esponente per calcolare la chiave pubblica $B$	$b \lt N$ casuale	$B = g^b \pmod N$	$\color{red}{b = 171} \\ \color{green}{B =210}$
Bruno, conoscendo $A$ che è pubblico e il suo esponente segreto $b$ può calcolare la chiave segreta $S$	$S$	$S = A^b \pmod N$	$\color{red}{S = 30}$
Bruno invia per un canale pubblico il cifrato composto da una coppia di numeri: il primo è $c_1 = B = g^b$, il secondo è $c_2 = m S\pmod N$	$(c_1, c_2)$	$c_1 = B = g^b \pmod N \\\ c_2 = m S \pmod N $	$\color{green}{(c_1, c_2)=} \\ \color{green}{(210, 151)}$
Alice decifra il cifrato
Alice calcola $s = c_1^a$ che è uguale a $S$ infatti $ c_1^a = (g^b)^a = g^{ab} = (g^a)^b = A^b = S $	$s$ chiave	$s = c_1^a$	$\color{red}{s=30}$
Alice calcola $s^{-1}$ inverso di $s$ (in aritmetica modulare)	Inverso	$s^{-1}$	$\color{red}{s^{-1}=60}$
Alice calcola ora $m =c_2 s^{-1}$ e quindi $M = f^{-1}(m)$	$m$ numero per $M$	$m =c_2 s^{-1}$	$\color{red}{m = 65 \\ M = A}$

Ovviamente, essendo $A = g^a$ ne segue che $a = log_g {A}$ e se qualcuno riuscisse a calcolare questo logaritmo avrebbe scoperto l'esponente segreto $a$ e potrebbe calcolare agevolmente la chiave $S=B^a \pmod N$. La sicurezza di ElGamal come quella di DH poggia prima di tutto sulla difficoltà proibitiva del calcolo del logaritmo discreto in un aritmetica modulare con modulo molto grande.

Inoltre se qualcuno ottenesse una coppia chiaro-cifrato, ovvero $m$ e $(c_1, c_2)$ potrebbe facilmente ricavare la chiave perché essendo $c_2 = m S $ ne segue che $S = c_2 m^{-1}$. Quindi per incrementare la sicurezza si deve generare ogni volta una nuova chiave. Insomma si tratta di una chiave “usa e butta”.