Elgamal, DSA

“Curs d'Introducció a la criptografia” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto

Elgamal en combinació de signatura

{طاهر الجمل (Taher Elgamal), 1985}

Fonamentat sobre l'algorisme DH, i base pel DSA i l'ECDSA
(Elgamal es pot combinar per a fer signatura o xifrat; veurem només la combinació de signatura que és de la que partirem per a veure el DSA i l'ECDSA)

Tots aquests algorismes es basen en
els problemes CDH i DDH (i aquests, del DLP)

Recordem la hipòtesi DLP:

Donats $\mathbb{Z}_{p}^{*}$ ($p$ primer), i $\alpha$ un generador (per tant $\mathbb{Z}_{p}^{*}$ és cíclic)

$x \equiv \log_{\alpha} \beta \pmod p$

és computacionalment difícil

$\Downarrow$

farem servir aquest fet per a generar le claus:
la privada serà el logaritme (modular) de la pública

Creació dels paràmetres comuns

Tots els usuaris poden compartir els paràmetres bàsics:
el grup cíclic $\mathbb{Z}_{p}^{*}$ i un generador $\alpha$

Les mateixes consideracions de DH per a $p$ i $\alpha$ apliquen aquí

Generació de claus

Cada usuari $\text{u}$ ha de generar:

$a_\text{u}$: seleccionem un valor (pseudo)aleatori $0 < a_\text{u} < p-1$
$y_\text{u}$: calculem $y_\text{u} = \alpha^{a_\text{u}}$

Gestió:

Publiquem $y_\text{u}$ ja que la nostra clau pública serà
la tupla $(p, \alpha, y_\text{u})$ (o simplement $y_\text{u}$)
Guardem $a_\text{u}$ ja que la nostra clau secreta serà
la tupla $(a_\text{u}, (p, \alpha, y_\text{u}))$ (o simplement $a_\text{u}$)

Nota: comparem el cost de generació de claus
d'Elgamal (1 random + 1 exp) amb el d'RSA (2 primers)

Signatura

calcula el hash del missatge $h(m)$
generem un random $k$, tal que $0 < k < p-1$ amb $\text{mcd}(k, p-1)=1$; $\,k$ ha de ser privat i únic

$r = \alpha^k \bmod p$

$s = \dfrac{h(m)-a_\text{u}r}{k} \bmod {(p-1)}\quad$ (apunt: Fermat petit)

La signatura d'$m$ és la tupla $(r, s)$

Verificació

A partir de la recepció del missatge $m$ i la signatura $(r,s)$

(previ: calculem el hash $h(m)$)
(previ: verifiquem que $0 < r < p-1$)
$v_2 = \alpha^{h(m)} \bmod p$
$v_1 = (y_\text{u})^{r} r^s \bmod p$
$v_1 \overset{?}{=} v_2 \implies$ signatura vàlida

$\text{Nota: }\left\{ \begin{eqnarray} v_2 &=& \alpha^{h(m)} \bmod p \\ &=& \alpha^{a_\text{u}r+ks \bmod{(p-1)}} \bmod p \\ &=& \color{blue}{\alpha^{a_\text{u}r+ks} \bmod{p}} \\ v_1 &=& (y_\text{u})^{r} r^s \bmod p \\ &=& \alpha^{a_\text{u}r} \alpha^{ks} \bmod{p} \\ &=& \color{blue}{\alpha^{a_\text{u}r+ks} \bmod{p}} \end{eqnarray} \right.$

Rendiment: Elgamal vs RSA

	Generació	Signatura	Validació
RSA	molt lent	mig	ràpid
Elgamal	molt ràpid	mig	mig

DSA

{NIST, 1991}

Directament basat en
l'algorisme Elgamal en combinació de signatura

DSA (Digital Signature Algorithm) actualment està sent desplaçat per la variant sobre corbes el·líptiques (ECDSA)

DSA vs Elgamal

DSA té una seguretat equivalent a Elgamal però:

Amb major velocitat de procés
Amb una mida de les signatures inferior (de fet, inferior a RSA de seguretat equivalent)

Aquests dos fets fan que Elgamal no es faci servir per signatura, en favor de l'equivalent DSA

Elgamal $\rightarrow$ DSA: reduïm $r$ i $s$ mòdul $\color{red}{q}$, on $\color{red}{q | (p-1)}$:

\[\begin{eqnarray} \text{random }k &\rightarrow& 0 < k < p-1 \\ r &=& \alpha^k \bmod p \\ s &=& \dfrac{h(m)-a_\text{u}r}{k} \bmod{(p-1)}\quad \\ \end{eqnarray}\]

$\downarrow$

\[\begin{eqnarray} &&\color{red}{q | (p-1)} \\ \text{random }k &\rightarrow& 0 < k < \color{red}{q} \\ r &=& (\alpha^k \bmod p) \color{red}{\bmod q} \qquad\\ s &=& \dfrac{h(m)+a_\text{u}r}{k} \color{grey}{\bmod{(p-1)}} \color{red}{\bmod{q}}\quad \end{eqnarray}\]

Quan vegem com dimensionar els paràmetres pels diferents algorismes, veurem que la mida recomanada en bits és:
$\|q\| \approx \dfrac{1}{6}\|p\|$

DSA

Paràmetres: $p$, $q$, $\alpha$

Clau privada: $a$ (un nombre aleatori $0 < a < q-2$)

Clau pública: $\alpha^a \bmod p$

Com a Elgamal, tots els usuaris poden
compartir els paràmetres bàsics:
el grup cíclic $\mathbb{Z}_{p}^{*}$, el generador $\alpha$, i a més a més $q$

Les mateixes consideracions de DH i Elgamal per a $p$ apliquen aquí

En canvi en DSA, $\alpha$ no ha de ser generador de $\mathbb{Z}_p^*$
(no ha de tenir $\text{ord}{(\alpha)} = \phi(p) = p -1$),
si no que $\text{ord}{(\alpha)} = q$ i $q|(p-1)$

Rendiment: DSA vs RSA

	Generació	Signatura	Validació
RSA	molt lent	mig	ràpid
DSA	molt ràpid	mig	mig

debilitats $\rightarrow$ contramesures

sobre la predicibilitat de l'aleatori $k$ ($r = \alpha^k \bmod p$)

Atacs de temps $\rightarrow$ randomització en l'execució

Atacs sobre el consum, la radiació, etc.

compromís de clau: accés software o físic al sistema

qualitat dels nombres aleatoris

a futur: computació quàntica

...

Longitud de clau

els atacs sobre DSA són els algorismes per a calcular el logaritme discret

el NIST recomana $\|p\| \geq 2048$ bit i $\|q\| \geq 224$ fins el 2030

$p$	$q$		(bits de seguretat)
$1024$	$160$	$\leftrightarrow$	$80$
$2048$	$224$	$\leftrightarrow$	$112$
$3072$	$256$	$\leftrightarrow$	$128$