Siguiente: Digital Signature Standard Un nivel arriba: Diversos esquemas de autentificación Anterior: Esquema RSA

Esquema ElGamal

Recordamos que todo usuario posee una llave pública (p_U,x_U,y_U) y una llave secreta z_U, donde p es primo, x_U es un elemento primitivo de $Z\!\!\!Z_p^*$ e $y_U=x_U^{z_U}\mbox{\rm mod }p$. Se tiene pues:

• Para un entero k aleatorio: $\mbox{\it rub}_{U,k}:m\mapsto F=(u,e)$ donde $\begin{array}[t]{rcl} u &=& x_U^{k}\mbox{\rm mod }p \\ e &=& \left(m-z_U u\right)k^{-1}\mbox{\rm mod }(p-1) % \end{array}$ ¡Atención! Si se mostrase k entonces podría calcularse la llave secreta z_U a partir de la firma: $z_U=(m-ku)e^{-1}\mbox{\rm mod }(p-1).$
• $\mbox{\it ver}_U:(m,f)\mapsto [x_U^m=y_U^u u^{e}\mbox{\rm mod }p]?$,
  pues en el caso de que (u,e) resultase del proceso de firmar, necesariamente:
  
  y_U^u u^e=x_U^{z_U u}x_U^ke=x_U^m
  
  
  ya que $z_U u + ke =z_U u + m-z_U u = m\mbox{\rm mod }(p-1)$.

Un intruso S que conociese el mensaje m buscaría generar los correspondientes coeficientes (u,e) de la firma. Si conociese u, el exponente e podría conocerse calculando $\log_u\left(x_U^m y_U^{-u}\right)$. Si conociese e, el elemento u podría conocerse tratando de reslver la ecuación: $x_U^m=y_U^u u^{e}\mbox{\rm mod }p$. Algún otro intento consistiría en tratar de calcular simultáneamente u,e. No se conoce de un algoritmo eficiente que lo haga. Tampoco se ha demostrado que no exista tal algoritmo. Sn embargo, de manera aleatoria un intruso podría generar mensajes firmados: Sean $i,j\in [\![0,p-2]\!]$ tales que j y p-1 sean primos relativos. Definamos:

$$\begin{eqnarray*}u &=& x^i y^j\mbox{\rm mod }p \\ e &=& -uj^{-1}\mbox{\rm mod ... ...{\rm mod }(p-1)\right)\\ m &=& -eij^{-1}\mbox{\rm mod }(p-1) \end{eqnarray*}$$

Entonces (u,e) es una firma de m con la llave pública (p,x,y). En efecto, módulo p valen las igualadades siguientes:

$$y^u u^e = y^u \left(x^i y^j\right)^{-uj^{-1}} = x^{-uij^{-1}} = x^m.$$

Un segundo procedimiento para generar firmas legítimas sobre ciertos mensajes es el siguiente: Supongamos conocido unmensaje m con su firma correspondiente (u,e). Sean $h,i,j\in [\![0,p-2]\!]$ tales que hu-je y p-1 sean primos relativos. Definamos:

$$\begin{eqnarray*}u' &=& u^h x^i y^j\mbox{\rm mod }p \\ e' &=& eu'\left(hu-je\r... ...(hm-ie\right)\cdot \left(hu-je\right)^{-1}\mbox{\rm mod }(p-1) \end{eqnarray*}$$

Entonces (u',e') es una firma de m' con la llave pública (p,x,y).
Siguiente: Digital Signature Standard Un nivel arriba: Diversos esquemas de autentificación Anterior: Esquema RSA