L'algoritmo di ElGamal venne proposto nel 1985 da Taher Elgamal. È un algoritmo di crittografia asimmetrico che si basa sul problema del Logaritmo Discreto (Discrete Logarithm Problem - DLP).
Algoritmo di ElGamal
Generazione delle chiavi
Nell'algoritmo di ElGamal la generazione delle chiavi avviene in questo modo:
- Viene generato un numero primo p e calcolato un generatore $\alpha$del gruppo moltiplicativo Z*p
- Si seleziona un numero intero a casuale, tale che $1 \leq a \leq (p-2)$ e viene calcolato $\alpha^a mod\:p$
- La chiave pubblica è formata dalla terna (p, $\alpha$, $\alpha^a$), mentre la chiave privata è costituita da a
La difficoltà nel risolvere il logaritmo discreto impedisce ad un attaccante di ricavare la chiave privata conoscendo quella pubblica. Infatti noto p ed $\alpha$, per ricavare a è necessario calcolare $log_{\alpha} \alpha^a$.
Cifratura
Dato un messaggio m, tale che m < p-1, la generazione del messaggio cifrato c avviene in questo modo:
- Si genera un numero intero k casuale tale che $1 \leq k \leq (p-2)$
- Si calcolano le quantità $\lambda = \alpha^k mod\:p$ e $\delta = m (\alpha^a)^k mod\:p$
- Il messaggio cifrato è costituito dalle due quantità $\lambda$ e $\delta$: $c = (\lambda, \delta)$
Decifratura
Il destinatario riceve $c = (\lambda, \delta)$ ed effettua i seguenti calcoli per recuperare il messaggio m:
- calcola $\lambda^a = (\alpha^k)^a mod\:p$
- divide $\delta = m (\alpha^a)^k mod\:p$ per $\lambda^a = (\alpha^k)^a mod\:p$ ottenendo m
Si può osservare che un attaccante per recuperare il messaggio m deve riuscire a calcolare $(\alpha^a)^k mod\:p$ conoscendo $(\alpha^k) mod\:p$ (il valore $\lambda$) e $\alpha^a mod\:p$ (contenuto nella chiave pubblica). Questa è una formulazione del problema di Diffie-Hellman.
Sicurezza
Algoritmi
| Fattorizzazione Interi | Logaritmo Discreto | Curve Ellittiche | |
|---|---|---|---|
| Cifratura | RSA, Rabin | ElGamal, DHIES |
