lunes, 26 de octubre de 2015

Criptografía


Algoritmos criptográficos

DSA (Digital Signature Algorithm, en español Algoritmo de Firma digital) es un estándar del Gobierno Federal de los Estados Unidos de América o FIPS para firmas digitales. Fue un Algoritmo propuesto por el Instituto Nacional de Normas y Tecnología de los Estados Unidos para su uso en su Estándar de Firma Digital(DSS), especificado en el FIPS 186. DSA se hizo público el 30 de agosto de 1991, este algoritmo como su nombre lo indica, sirve para firmar y no para cifrar información. Una desventaja de este algoritmo es que requiere mucho más tiempo de cómputo que RSA.

Generación de llaves

  • Elegir un número primo p de L bits, donde 512 ≤ L ≤ 1024 y L es divisible por 64.
  • Elegir un número primo q de 160 bits, tal que p−1 = qz, donde z es algún número natural.
  • Elegir h, donde 1 < h < p − 1 tal que g = hz(mod p) > 1.
  • Elegir x de forma aleatoria, donde 1 < x < q-1.
  • Calcular y = gx(mod p).
Los datos públicos son p, q, g e y. x es la llave privada.

Firma

  • Elegir un número aleatorio k, donde 1 < k < q.
  • Calcular r = (gk mod p)mod q.
  • Calcular s = k-1(H(m)+r*x) mod q, donde H(m) es la función hash SHA-1 aplicada al mensaje m.
  • La firma es el par (r, s).
Si r ó s es cero, se vuelve a repetir el procedimiento.

Verificación

  • Calcular w = (s)-1(mod q).
  • Calcular u1 = H(m)*w(mod q).
  • Calcular u2 = r*w(mod q).
  • Calcular v = [gu1*yu2mod p] mod q.
  • La firma es válida si v = r.

Demostración del algoritmo

El esquema de la firma está correcto en el sentido que el verificador aceptará siempre firmas genuinas. Esto puede ser demostrada como sigue:
De g = h^z \pmod p sigue g^q \equiv h^{qz} \equiv h^{p-1} \equiv 1 \pmod p por Pequeño teorema de Fermat. Ya que g>1 y q es primo sigue que g tiene orden q.
El firmante computa
s=k^{-1}(\mbox{SHA-1}(m)+xr) \mod{q}.
Entonces
\begin{matrix} k & \equiv & \mbox{SHA-1}(m)s^{-1}+xrs^{-1}\\ & \equiv & \mbox{SHA-1}(m)w + xrw \pmod{q}.\\ \end{matrix}
Ya que g tiene orden q tenemos que
\begin{matrix} g^k & \equiv & g^{{\rm SHA-1}(m)w}g^{xrw}\\ & \equiv & g^{{\rm SHA-1}(m)w}y^{rw}\\ & \equiv & g^{u1}y^{u2} \pmod{p}.\\ \end{matrix}
Finalmente, la correctitud de DSA surge de
r=(g^k \mod p) \mod q = (g^{u1}y^{u2} \mod p) \mod q = v.


ECDSA. Elliptic Curve Digital Signature Algorithm es una modificación del algoritmo DSA que emplea operaciones sobre puntos de curvas elípticas en lugar de las exponenciaciones que usa DSA (problema del logaritmo discreto). La principal ventaja de este esquema es que requiere números de tamaños menores para brindar la misma seguridad que DSA o RSA. Existen dos tipos de curvas dependiendo del campo finito en el que se definan que pueden ser GF(P) o GF(2m).

Proceso de firma y verificación

  • Generación de llaves
  1. Seleccione una curva elíptica E.
  2. Seleccione un punto P (que pertenezca a E) de orden n.
  3. Seleccione aleatoriamente un número d en el intervalo [1, n - 1].
  4. Calcule Q = dP.
  5. d será la llave privada.
  6. Q será la llave pública.
  • Proceso de firma
  1. Seleccione un número k de forma aleatoria.
  2. Calcule kP = (x1,y1).
  3. Calcule r = x1 mod n. Si r = 0 regresa al primer paso. (En este paso x1 es tratado como un entero).
  4. Calcule (k-1) mod n.
  5. Calcule s = k-1(H(m) + dr) mod n. Si s = 0 regrese al primer paso. (H(m) es el hash del mensaje a firmar, calculado con el algoritmo SHA-1).
  6. La firma del mensaje m son los números r y s.
  • Proceso de verificación
  1. Verifique que r y s estén dentro del rango [1,n - 1].
  2. Calcule w = s-1 mod n.
  3. Calcule u1 = H(m)w mod n.
  4. Calcule u2 = r·w mod n.
  5. Calcule u1P + u2Q = (x0,y0)
  6. Calcule v = x0 mod n
  7. La firma verifica si y solo si v = r












El Esquema de firma ElGamal es un esquema de firma digital basado en la complejidad del cálculo del logaritmo discreto. Fue descrito por Taher ElGamal en 1984. El algoritmo de firma ElGamal descrito en su artículo es raramente utilizado en la práctica. Con más frecuencia se utiliza una de sus variantes llamada Algoritmo de firma digital (DSA). El esquema de firma ElGamal no debe confundirse con el cifrado ElGamal también propuesto por Taher ElGamal.
El esquema de firma ElGamal permite que un verificador pueda confirmar la autenticidad de un mensaje m enviado por un emisor sobre un canal de comunicacióninseguro.

Parámetros

Los parámetros utilizados por el esquema ElGamal son:
Los parámetros utilizados pueden ser compartidos entre usuarios.

Generación de claves

  • Se selecciona un clave secreta x de forma aleatoria tal que 1<x<p-1.
  • Se calcula y=g^x \pmod p.
  • La clave pública será (p,g,y).
  • La clave secreta será x.
Estos pasos son realizados una sola vez por el firmante.

Generación de una firma

Para firmar un mensaje m el firmante realiza los pasos siguientes.
  • Selecciona un número aleatorio k tal que 0<k<p-1 y mcd(k,p-1)=1.
  • Calcula  r \, \equiv \, g^k \pmod p.
  • Calcula  s \, \equiv \, (H(m)-x r)k^{-1} \pmod{p-1}.
  • Si s=0 reinicia el proceso.
El par (r,s) así obtenido es la firma digital de m. El firmante repite estos pasos para cada mensaje m que desea firmar.

Verificación

La firma (r,s) de un mensaje m proveniente de un firmante con clave pública (p,g,y) y que utilizó una función de Hash H se verifica de la siguiente forma:
  • Se verifica que 0<r<p y que 0<s<p-1.
  • Se verifica que  g^{H(m)} \, \equiv \, y^r r^s \pmod p..
El verificante acepta el mensaje únicamente si estas tres condiciones se cumplen.

Corrección

El algoritmo es correcto en el sentido que una firma generada con este algoritmo de firma siempre será aceptada por un verificador.
La generación de firmas incluye
H(m) \, \equiv \, x r + s k \pmod{p-1}.
\begin{matrix} g^{H(m)} & \equiv & g^{xr} g^{ks} \\ & \equiv & (g^{x})^r (g^{k})^s \\ & \equiv & (y)^r (r)^s \pmod p.\\ \end{matrix}

Seguridad

Un tercero puede falsificar firmas si encuentra la clave secreta x del firmante o si encuentra colisiones en la función de Hash H(m) \equiv H(M) \pmod{p-1}. Se considera que ambos problemas son suficientemente difíciles.
El firmante debe tener cuidado y escoger una k diferente de forma uniformemente aleatoria para cada firma. Así asegura que k o aún información parcial sobre k no es deducible. Malas selecciones de k pueden representar fugas de información que facilitan el que un atacante deduzca la clave secreta x. En particular, si dos mensajes son enviados con el mismo valor de k entonces es factible deducir el valor de la clave secreta x.

Esquema ElGamal

Recordamos que todo usuario posee una llave pública (pU,xU,yU) y una llave secreta zU, donde p es primo, xU 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 zU 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:

    yUu ue=xUzU uxUke=xUm


    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: 

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


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 quehu-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).
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)