Algoritmo de firma digital

El Algoritmo de Firma Digital (DSA) es un criptosistema de clave pública y Estándar Federal de Procesamiento de Información para firmas digitales, basado en el concepto matemático de exponenciación modular y la discreta problema de logaritmo DSA es una variante de los esquemas de firma Schnorr y ElGamal.

El Instituto Nacional de Estándares y Tecnología (NIST) propuso DSA para su uso en su Estándar de Firma Digital (DSS) en 1991 y lo adoptó como FIPS 186 en 1994. Se han publicado cuatro revisiones a la especificación inicial. La especificación más reciente es: FIPS 186-4 de julio de 2013. DSA está patentado pero NIST ha hecho que esta patente esté disponible en todo el mundo libre de regalías. Una versión preliminar de la especificación FIPS 186-5 indica que DSA ya no se aprobará para la generación de firmas digitales, pero se puede usar para verificar las firmas generadas antes de la fecha de implementación de ese estándar.

Resumen

El DSA funciona en el marco de los criptosistemas de clave pública y se basa en las propiedades algebraicas de la exponenciación modular, junto con el problema del logaritmo discreto, que se considera computacionalmente intratable. El algoritmo utiliza un par de claves que consta de una clave pública y una clave privada. La clave privada se usa para generar una firma digital para un mensaje, y dicha firma se puede verificar usando la clave pública correspondiente del firmante. La firma digital proporciona autenticación de mensajes (el receptor puede verificar el origen del mensaje), integridad (el receptor puede verificar que el mensaje no ha sido modificado desde que se firmó) y no repudio (el remitente no puede afirmar falsamente que no ha firmó el mensaje).

Historia

En 1982, el gobierno de EE. UU. solicitó propuestas para un estándar de firma de clave pública. En agosto de 1991, el Instituto Nacional de Estándares y Tecnología (NIST) propuso DSA para su uso en su Estándar de Firma Digital (DSS). Inicialmente hubo críticas importantes, especialmente de las empresas de software que ya habían invertido esfuerzos en desarrollar software de firma digital basado en el criptosistema RSA. Sin embargo, NIST adoptó DSA como estándar federal (FIPS 186) en 1994. Se publicaron cuatro revisiones de la especificación inicial: FIPS 186–1 en 1998, FIPS 186–2 en 2000, FIPS 186–3 en 2009 y FIPS 186 –4 en 2013. Una versión preliminar del estándar FIPS 186-5 prohíbe firmar con DSA, mientras que permite la verificación de firmas generadas antes de la fecha de implementación del estándar como documento. Será reemplazado por esquemas de firma más nuevos, como EdDSA.

DSA está cubierto por U.S. Patente 5.231.668, presentada el 26 de julio de 1991 y ahora vencida, y atribuida a David W. Kravitz, ex empleado de la NSA. Esta patente fue otorgada a "Los Estados Unidos de América representados por el Secretario de Comercio, Washington, D.C.", y el NIST ha hecho que esta patente esté disponible en todo el mundo libre de regalías. Claus P. Schnorr afirma que su U.S. la patente 4,995,082 (también ahora vencida) cubría DSA; esta afirmación está en disputa.

Operación

El algoritmo DSA implica cuatro operaciones: generación de claves (que crea el par de claves), distribución de claves, firma y verificación de firma.

1. Generación de claves

La generación de claves tiene dos fases. La primera fase es una elección de parámetros de algoritmo que pueden compartirse entre diferentes usuarios del sistema, mientras que la segunda fase calcula un solo par de claves para un usuario.

Generación de parámetros

• Elija una función de hash criptográfica aprobada H{displaystyle H. con longitud de salida SilencioHSilencio{displaystyle TENSIA bits. En el DSS original, H{displaystyle H. fue siempre SHA-1, pero las funciones más fuertes SHA-2 hash están aprobadas para su uso en el DSS actual. Si SilencioHSilencio{displaystyle TENSIA es mayor que la longitud del módulo N{displaystyle N}, sólo el más izquierdo N{displaystyle N} Se utilizan bits de la salida de hash.
• Elija una longitud clave L{displaystyle L.. El DSS original limitó L{displaystyle L. ser un múltiple de 64 entre 512 y 1024 inclusive. NIST 800-57 recomienda longitudes de 2048 (o 3072) para llaves con vida útil de seguridad que se extienden más allá de 2010 (o 2030).
• Elija la longitud del módulo N{displaystyle N} tales que <math alttext="{displaystyle NN.L{displaystyle No.<img alt="{displaystyle N y N≤ ≤ SilencioHSilencio{displaystyle Nleq Наливаный sobre la vida. FIPS 186-4 especifica L{displaystyle L. y N{displaystyle N} tener uno de los valores: (1024, 160), (2048, 224), (2048, 256), o (3072, 256).
• Elija un N{displaystyle N}- Vale. q{displaystyle q}.
• Elija un L{displaystyle L.- Vale. p{displaystyle p} tales que p− − 1{displaystyle p-1} es un múltiple de q{displaystyle q}.
• Elija un entero h{displaystyle h} aleatoriamente desde {}2...... p− − 2}{displaystyle {2ldots p-2}}.
• Computación g:=h()p− − 1)/qmodp{displaystyle g:=h^{(p-1)/q}mod p}. En el caso raro que g=1{displaystyle g=1} probar de nuevo con otro h{displaystyle h}. Comúnmente h=2{displaystyle h=2} se utiliza. Esta exponencia modular se puede calcular eficientemente incluso si los valores son grandes.

Los parámetros del algoritmo son (p{displaystyle p}, q{displaystyle q}, g{displaystyle g}). Estos pueden ser compartidos entre diferentes usuarios del sistema.

Claves por usuario

Dado un conjunto de parámetros, la segunda fase calcula el par de claves para un solo usuario:

• Elija un entero x{displaystyle x} aleatoriamente desde {}1...... q− − 1}{displaystyle {1ldots q-1}.
• Computación Sí.:=gxmodp{displaystyle y:=g^{x}mod p}.

x{displaystyle x} es la clave privada y Sí.{displaystyle y} es la clave pública.

2. Distribución de llaves

El firmante debe publicar la clave pública Sí.{displaystyle y}. Es decir, deben enviar la clave al receptor a través de un mecanismo confiable, pero no necesariamente secreto. El firmante debe mantener la llave privada x{displaystyle x} secreto.

3. Firma

Un mensaje m{displaystyle m} se firma como sigue:

• Elija un entero k{displaystyle k} aleatoriamente desde {}1...... q− − 1}{displaystyle {1ldots q-1}
• Computación r:=()gkmodp)modq{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}. En el caso improbable de que r=0{displaystyle r=0}, empezar de nuevo con un azar diferente k{displaystyle k}.
• Computación s:=()k− − 1()H()m)+xr))modq{displaystyle s:=left(k^{-1}left(H(m)+xrright)right){bmod {,}q}. En el caso improbable de que s=0{displaystyle s=0}, empezar de nuevo con un azar diferente k{displaystyle k}.

La firma es ()r,s){displaystyle left(r,sright)}

El cálculo k{displaystyle k} y r{displaystyle r} equivale a crear una nueva clave de mensajería. La exponencia modular en computación r{displaystyle r} es la parte más costosa computacionalmente de la operación de firma, pero puede ser calculada antes de que se conozca el mensaje. Calculando el inverso modular k− − 1modq{fnMicrosoft} es la segunda parte más cara, y también puede ser computada antes de que se conozca el mensaje. Puede ser calculado usando el algoritmo de Euclidean extendido o usando el pequeño teorema de Fermat como kq− − 2modq{fnMicrosoft Sans Serif}.

4. Verificación de firma

Uno puede verificar que una firma ()r,s){displaystyle left(r,sright)} es una firma válida para un mensaje m{displaystyle m} como sigue:

• Verificar eso <math alttext="{displaystyle 0<r0.r.q{displaystyle 0cantador se hizo realidad}<img alt="{displaystyle 0<r y <math alttext="{displaystyle 0<s0.s.q{displaystyle 0 realizadas<img alt="{displaystyle 0<s.
• Computación w:=s− − 1modq{fnMicrosoft Sans Serif}.
• Computación u1:=H()m)⋅ ⋅ wmodq{displaystyle U_{1}:=H(m)cdot w,{bmod {,}q}.
• Computación u2:=r⋅ ⋅ wmodq{displaystyle ¿Qué?.
• Computación v:=()gu1Sí.u2modp)modq{displaystyle v:=left(g^{u_{1}y}{u_{2}{bmod {,}pright){bmod {,}q}.
• La firma es válida si y sólo si v=r{displaystyle v=r}.

Corrección del algoritmo

El esquema de firma es correcto en el sentido de que el verificador siempre aceptará firmas genuinas. Esto se puede demostrar de la siguiente manera:

Primero, desde g=h()p− − 1)/qmodp{textstyle g=h^{(p-1)/q}{text{mod}~p}, sigue que gq↑ ↑ hp− − 1↑ ↑ 1modp{textstyle g^{q}equiv h^{p-1}equiv 1mod p} por el pequeño teorema de Fermat. Desde 0}" xmlns="http://www.w3.org/1998/Math/MathML">g■0{displaystyle g]0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7bf4ccb218a98120f6af86b98a83f1e56fb9f3b1" style="vertical-align: -0.671ex; width:5.377ex; height:2.509ex;"/> y q{displaystyle q} es primo, g{displaystyle g} debe tener ordenq{displaystyle q}.

El firmante calcula

s=k− − 1()H()m)+xr)modq{fnMicrosoft Sans Serif}

Así

k↑ ↑ H()m)s− − 1+xrs− − 1↑ ↑ H()m)w+xrw()modq){fnMicrosoftware {fnMicrosoft Sans Serif}fnMicrosoft}fn}f}\fnunci}}fnuncié a un grupo de personas.

Desde g{displaystyle g} tiene orden q{displaystyle q} tenemos

gk↑ ↑ gH()m)wgxrw↑ ↑ gH()m)wSí.rw↑ ↑ gu1Sí.u2()modp){displaystyle {begin{aligned}g^{k} g^{H(m)w} {xrw}\\\equiv g^{H(m)w}y^{rw}\\\\equiv - Sí. {p}end{aligned}}

Finalmente, la corrección de DSA se deriva de

r=()gkmodp)modq=()gu1Sí.u2modp)modq=v{fnMicrosoft {fnMicrosoft {fnMicrosoft} {fnMicrosoft {fnMicrosoft {f}p}}p} {bmod {,}p}p}p} {bmod {,}p}p}p} {bmod {,}bmod {,}}}q\\\\\cH0}d}d}d}d}d} {c}d}}}}dc} {c}}}}d} {c}d} {c}d}} {c}}}}}}dcc}}}}dc} {c} {c}p}p} {c} {c}p}p} {cccccc}p}p}c}}p}p}p}p}p}p}p}p}p}ccccccc}p}p}}

Sensibilidad

Con DSA, la entropía, el secreto y la singularidad del valor de firma al azar k{displaystyle k} son críticos. Es tan crítico que violar cualquiera de esos tres requisitos puede revelar toda la clave privada para un atacante. Usando el mismo valor dos veces (incluso manteniendo k{displaystyle k} secreto), usando un valor predecible, o filtrando incluso algunos trozos de k{displaystyle k} en cada una de las firmas, es suficiente para revelar la clave privada x{displaystyle x}.

Este problema afecta tanto a DSA como a Elliptic Curve Digital Signature Algorithm (ECDSA) – en diciembre de 2010, el grupo Fall0verflow anunció la recuperación de la llave privada ECDSA utilizada por Sony para firmar software para la consola de juegos PlayStation 3. El ataque fue posible porque Sony no generó un nuevo azar k{displaystyle k} para cada firma.

Esta cuestión puede prevenirse al llegar k{displaystyle k} deterministamente de la clave privada y el hash del mensaje, como se describe en RFC 6979. Esto garantiza que k{displaystyle k} es diferente para cada H()m){displaystyle H(m)} e impredecible para los atacantes que no conocen la llave privada x{displaystyle x}.

Además, se pueden crear implementaciones maliciosas de DSA y ECDSA donde k{displaystyle k} es elegido con el fin de filtrar subliminalmente información a través de firmas. Por ejemplo, una clave privada fuera de línea podría ser filtrada de un dispositivo sin conexión perfecto que sólo lanzó firmas de aspecto inocente.

Implementaciones

A continuación se muestra una lista de bibliotecas criptográficas que brindan soporte para DSA:

• Botan
• Bouncy Castle
• cryptlib
• Crypto+
• Ligcrypt
• Nettle
• OpenSSL
• lobo Crypt
• GnuTLS