Elgamal, DSA

“Curso de Introducción a la Criptografía” 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ón de firma

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

Basado sobre el algoritmo DH, y es base para el DSA y el ECDSA
(Elgamal se puede combinar para implementar firma o cifrado; veremos sólo la combinación de firma que es de la que partiremos para ver el DSA y el ECDSA)

Todos estos algoritmos se basan en
los problemas CDH y DDH (y estos, del DLP)

Recordemos la hipótesis DLP:

Dados $\mathbb{Z}_{p}^{*}$ ($p$ primo), y $\alpha$ un generador (por tanto $\mathbb{Z}_{p}^{*}$ es cíclico)

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

es computacionalmente difícil

$\Downarrow$

utilizaremos este hecho para generar las claves:
la privada será el logaritmo (modular) de la pública

Creación de los parámetros comunes

Todos los usuarios pueden compartir los parámetros básicos:
el grupo cíclico $\mathbb{Z}_{p}^{*}$ y un generador $\alpha$

Las mismas consideraciones de DH para $p$ y $\alpha$ aplican aquí

Generación de claves

Cada usuario $\text{u}$ debe generar:

• $a_\text{u}$: seleccionamos un valor aleatorio $1 \leq a_\text{u} \leq p-1$
• $y_\text{u}$: calculamos $y_\text{u} = \alpha^{a_\text{u}} \pmod p$

Gestión:

• Publicamos $y_\text{u}$ ya que nuestra clave pública será
  la tupla $(p, \alpha, y_\text{u})$ (o simplemente $y_\text{u}$)
• Guardamos $a_\text{u}$ ya que nuestra clave secreta será
  la tupla $(a_\text{u}, (p, \alpha, y_\text{u}))$ (o simplemente $a_\text{u}$)

Nota: comparemos el coste de generación de claves
de Elgamal (1 random + 1 exp) con la de RSA (2 primos)

Firma

1. calcula el hash del mensaje $h(m)$
2. generamos un random $k$, tal que $1 \leq k \leq p-1$ con $\text{mcd}(k, p-1)=1$; $\,k$ debe ser privado y único


3. $r = \alpha^k \bmod p$


4. $s = \dfrac{h(m)-a_\text{u}r}{k} \bmod {(p-1)}\quad$ (apunte: Fermat pequeño)

La firma de $m$ es la tupla $(r, s)$

Verificación

A partir de la recepción del mensaje $m$ y la firma $(r,s)$

1. previo: calculamos el hash del mensaje $m \rightarrow h(m)$
2. previo: verificamos que $r$ y $s$ son válidos: $\left\{ \begin{aligned} 1 & \leq r \leq p-1 \\ 1 & \leq s \leq p-1 \end{aligned} \right.$
3. $v_2 = \alpha^{h(m)} \bmod p$
4. $v_1 = (y_\text{u})^{r} r^s \bmod p$
5. sii $v_1$ y $v_2$ son iguales la firma es válida

Firma: $\begin{aligned} r &= \alpha^k \bmod p \\ s &= \dfrac{h(m)-a_\text{u}r}{k} \bmod {(p-1)} \\ \end{aligned}$

Verificación: $\begin{aligned} v_2 &= \alpha^{h(m)} \bmod p \\ v_1 &= (y_\text{u})^{r} r^s \bmod p \end{aligned}\longrightarrow$ $\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.$

Rendimiento: Elgamal vs RSA

debilidades $\rightarrow$ contramedidas

• sobre la predictibilidad del aleatorio $k$   ($r = \alpha^k \bmod p$)
• Ataques de tiempo $\rightarrow$ randomización en la ejecución
• Ataques sobre el consumo, la radiación, etc.
• compromiso de clave: acceso software o físico al sistema
• calidad de los números aleatorios
• a futuro: computación cuántica
• ...

Ataque sobre sobre $k$ conocido

Es fundamental mantener $k$ secreto, ya que si conocemos $k$…
conoceremos la clave privada $a_\text{u}$, así:

$\begin{aligned} s &= \dfrac{h(m)-a_\text{u}r}{k} \bmod {(p-1)} \\ s k &= (h(m)-a_\text{u}r) \bmod {(p-1)} \\ a_\text{u}r &= (h(m)-sk) \bmod {(p-1)} \\ a_\text{u} &= \dfrac{h(m)-sk}{r} \bmod {(p-1)} \\ \end{aligned}$

Ataque sobre el reúso de $k$

Es fundamental no reutilizar $k$, ya que un atacante que viera dos firmas:

$s_1 = \dfrac{h(m_1)-a_\text{u}\color{red}{r}}{\color{red}{k}} \bmod {(p-1)} \text{ y } s_2 = \dfrac{h(m_2)-a_\text{u}\color{red}{r}}{\color{red}{k}} \bmod {(p-1)}$

$\begin{aligned} s_2 - s_1 &= \dfrac{h(m_2)-h(m_1)}{\color{red}{k}} \bmod {(p-1)} \\ \color{red}{k} &= \dfrac{h(m_2)-h(m_1)}{s_2-s_1} \bmod {(p-1)} \end{aligned}$

Descubriría $k$… y por tanto nuestra clave privada $a_\text{u}$ (página anterior)

En general los distintos $k$ no deben tener ninguna relación entre ellos (deben ser aleatorios)

Longitud de clave

los ataques sobre Elgamal son los algoritmos para calcular el logaritmo discreto

DSA

{NIST, 1991}

Directamente basado en
el algoritmo Elgamal en combinación de firma

DSA (Digital Signature Algorithm) actualmente está siendo desplazado por la variante sobre curvas elípticas (ECDSA)

DSA vs Elgamal

DSA tiene una seguridad equivalente a Elgamal pero:

• Con mayor velocidad de proceso
• Con un tamaño de las firmas inferior (de hecho, inferior a RSA de seguridad equivalente)

Estos dos hechos hacen que Elgamal no se use para firma, en favor del equivalente DSA

Elgamal $\rightarrow$ DSA: reducimos $r$ y $s$ módulo $\color{red}{q}$, donde $\color{red}{q | (p-1)}$:

\[\begin{eqnarray} \text{random }k &\rightarrow& 1 \leq k \leq 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& 1 \leq k \leq \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}\]

Cuando veamos como dimensionar los parámetros para los diferentes algoritmos, veremos que el tamaño recomendado en bits es:
$\|q\| \approx \dfrac{1}{6}\|p\|$

DSA

   Parámetros: $p$, $q$, $\alpha$

   Clave privada: $a$ (un número aleatorio $1 \leq a \leq q-1$)

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

Rendimiento: DSA vs RSA

debilidades $\rightarrow$ contramedidas

ídem Elgamal

Longitud de clave

los ataques sobre DSA son los algoritmos para calcular el logaritmo discreto

el NIST recomienda $\|p\| \geq 2048$ bit y $\|q\| \geq 224$ hasta el 2030

(Criptografía de Curva Elíptica) $\rightarrow$