Algoritmo de firma digital

El algoritmo de firma digital ( DSA ) es un estándar federal de procesamiento de información para firmas digitales , basado en el concepto matemático de exponenciación modular y el problema del logaritmo discreto . DSA es una variante de los esquemas de firma de Schnorr y ElGamal . ^{[1] : 486}

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. ^[2] Se han publicado cuatro revisiones a la especificación inicial. La especificación más reciente es FIPS 186-4 de julio de 2013. ^[3] DSA está patentado, pero el 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 los DSA ya no serán aprobados para la generación de firmas digitales, pero pueden usarse para verificar firmas generadas antes de la fecha de implementación de ese estándar.

Resumen

El algoritmo 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 intratable computacionalmente. El algoritmo utiliza un par de claves que consta de una clave pública y una clave privada. La clave privada se utiliza para generar una firma digital para un mensaje, y dicha firma se puede verificar utilizando la clave pública correspondiente del firmante. La firma digital proporciona autenticación del mensaje (el receptor puede verificar el origen del mensaje), integridad (el receptor puede verificar que el mensaje no ha sido modificado desde que fue firmado) y no repudio. (el remitente no puede afirmar falsamente que no ha firmado 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 el desarrollo de software de firma digital basado en el criptosistema RSA . ^{[1] : 484} No obstante, NIST adoptó DSA como estándar federal (FIPS 186) en 1994. Se han publicado cuatro revisiones de la especificación inicial: FIPS 186–1 en 1998, ^[4] FIPS 186–2 en 2000, ^{[5 ]} FIPS 186-3 en 2009, ^[6]y FIPS 186–4 en 2013. ^[3] Una versión preliminar del estándar FIPS 186-5 prohíbe la firma con DSA, al tiempo 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 . ^[7]

La DSA está cubierta por la patente estadounidense 5.231.668 , presentada el 26 de julio de 1991 y ahora vencida, y atribuida a David W. Kravitz, ^[8] un ex empleado de la NSA . Esta patente fue otorgada a "Los Estados Unidos de América representados por el Secretario de Comercio , Washington, DC", y NIST ha hecho que esta patente esté disponible en todo el mundo libre de regalías. ^[9] Claus P. Schnorr afirma que su patente de Estados Unidos 4.995.082 (también ahora vencida) cubría DSA; esta afirmación está en disputa. ^[10]

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 firmas.

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 hash criptográfica aprobada con bits de longitud de salida . En el DSS original, siempre fue SHA-1 , pero las funciones hash SHA-2 más fuertes están aprobadas para su uso en el DSS actual. ^{[3] [11]} Si es mayor que la longitud del módulo , solo se utilizan los bits más a la izquierda de la salida hash.${\displaystyle H}$${\displaystyle |H|}$${\displaystyle H}$${\displaystyle |H|}$${\displaystyle N}$${\displaystyle N}$
• Elija una longitud de clave . El DSS original restringido a ser un múltiplo de 64 entre 512 y 1024 inclusive. NIST 800-57 recomienda longitudes de 2048 (o 3072) para llaves con una vida útil de seguridad que se extiende más allá de 2010 (o 2030). ^[12]${\displaystyle L}$${\displaystyle L}$
• Elija la longitud del módulo tal que y . FIPS 186-4 especifica y tener uno de los valores: (1024, 160), (2048, 224), (2048, 256) o (3072, 256). ^[3]${\displaystyle N}$${\displaystyle N<L}$${\displaystyle N\leq |H|}$${\displaystyle L}$${\displaystyle N}$
• Elija un primo de -bit .${\displaystyle N}$${\displaystyle q}$
• Elija un primo de -bit tal que - 1 sea un múltiplo de .${\displaystyle L}$${\displaystyle p}$${\displaystyle p}$${\displaystyle q}$
• Elija un número entero al azar .${\displaystyle h}$${\displaystyle \{2\ldots p-2\}}$
• Calcular . En el raro caso de que vuelva a intentarlo con un archivo . Se usa comúnmente . Esta exponenciación modular se puede calcular de manera eficiente incluso si los valores son grandes.${\displaystyle g:=h^{(p-1)/q}\mod p}$${\displaystyle g=1}$${\displaystyle h}$${\displaystyle h=2}$

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

Claves por usuario

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

• Elija un número entero al azar .${\displaystyle x}$${\displaystyle \{1\ldots q-1\}}$
• Calcular .${\displaystyle y:=g^{x}\mod p}$

${\displaystyle x}$es la clave privada y es la clave pública.${\displaystyle y}$

Distribución de claves

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

Firmando

Un mensaje está firmado de la siguiente manera:${\displaystyle m}$

• Elija un número entero al azar de${\displaystyle k}$${\displaystyle \{1\ldots q-1\}}$
• Calcular . En el improbable caso , comience de nuevo con un azar diferente .${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$${\displaystyle r=0}$${\displaystyle k}$
• Calcular . En el improbable caso , comience de nuevo con un azar diferente .${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}$${\displaystyle s=0}$${\displaystyle k}$

La firma es ${\displaystyle \left(r,s\right)}$

El cálculo y la cantidad para crear una nueva clave por mensaje. La exponenciación modular en computación es la parte más costosa computacionalmente de la operación de firma, pero puede calcularse antes de que se conozca el mensaje. El cálculo de la inversa modular es la segunda parte más cara, y también se puede calcular antes de que se conozca el mensaje. Puede calcularse usando el algoritmo euclidiano extendido o usando el pequeño teorema de Fermat como .${\displaystyle k}$${\displaystyle r}$${\displaystyle r}$${\displaystyle k^{-1}{\bmod {\,}}q}$${\displaystyle k^{q-2}{\bmod {\,}}q}$

Verificando una firma

Se puede verificar que una firma es una firma válida para un mensaje de la siguiente manera:${\displaystyle \left(r,s\right)}$${\displaystyle m}$

• Verifique eso y .${\displaystyle 0<r<q}$${\displaystyle 0<s<q}$
• Calcular .${\displaystyle w:=s^{-1}{\bmod {\,}}q}$
• Calcular .${\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}$
• Calcular .${\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}$
• Calcular .${\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q}$
• La firma es válida si y solo si .${\displaystyle v=r}$

Corrección del algoritmo

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

Primero, ya que , se sigue eso por el pequeño teorema de Fermat . Dado que y es primo, debe tener orden  .${\textstyle g=h^{(p-1)/q}~{\text{mod}}~p}$${\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}$${\displaystyle g>0}$${\displaystyle q}$${\displaystyle g}$${\displaystyle q}$

El firmante calcula

${\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q}$

Por lo tanto

${\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}}$

Ya que tiene orden tenemos${\displaystyle g}$${\displaystyle q~({\text{mod}}~p)}$

${\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned}}}$

Finalmente, la exactitud de DSA se deriva de

${\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}}$

Sensibilidad

Con DSA, la entropía, el secreto y la singularidad del valor de la firma aleatoria son fundamentales. Es tan crítico que violar cualquiera de esos tres requisitos puede revelar la clave privada completa a un atacante. ^[13] Usar el mismo valor dos veces (incluso mientras se mantiene en secreto), usar un valor predecible o filtrar incluso algunos bits de cada una de las firmas es suficiente para revelar la clave privada . ^[14]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle x}$

Este problema afecta tanto a DSA como a ECDSA : en diciembre de 2010, un grupo que se hacía llamar fail0verflow anunció la recuperación de la clave privada ECDSA utilizada por Sony para firmar el software para la consola de juegos PlayStation 3 . El ataque fue posible porque Sony no pudo generar un nuevo aleatorio para cada firma. ^[15]${\displaystyle k}$

Este problema se puede evitar derivando determinísticamente de la clave privada y el hash del mensaje, como se describe en RFC 6979 . Esto asegura que sea ​​diferente para cada uno e impredecible para los atacantes que no conocen la clave privada .${\displaystyle k}$ ${\displaystyle k}$${\displaystyle H(m)}$${\displaystyle x}$

Además, se pueden crear implementaciones maliciosas de DSA y ECDSA donde se elija para filtrar información subliminalmente a través de firmas. Por ejemplo, una clave privada fuera de línea podría filtrarse desde un dispositivo perfecto fuera de línea que solo lanzó firmas de apariencia inocente. ^[dieciséis]${\displaystyle k}$

Implementaciones

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

• Botan
• Castillo inflable
• cryptlib
• Cripto ++
• libgcrypt
• Ortiga
• OpenSSL
• WolfCrypt
• GnuTLS

Ver también

• Aritmética modular
• RSA (criptosistema)
• ECDSA

Referencias

1. Schneier, Bruce (1996). Criptografía aplicada . ISBN 0-471-11709-9.
2. "FIPS PUB 186: estándar de firma digital (DSS), 19 de mayo de 1994" . qcsrc.nist.gov . Archivado desde el original el 13 de diciembre de 2013.
3. "FIPS PUB 186-4: Estándar de firma digital (DSS), julio de 2013" (PDF) . csrc.nist.gov .
4. "FIPS PUB 186-1: Estándar de firma digital (DSS), 1998-12-15" (PDF) . csrc.nist.gov . Archivado desde el original (PDF) el 26 de diciembre de 2013.
5. "FIPS PUB 186-2: Estándar de firma digital (DSS), 2000-01-27" (PDF) . csrc.nist.gov .
6. "FIPS PUB 186-3: Estándar de firma digital (DSS), junio de 2009" (PDF) . csrc.nist.gov .
7. "Estándar de firma digital (DSS)" . Departamento de Comercio de Estados Unidos. 31 de octubre de 2019 . Consultado el 21 de julio de 2020 .
8. Dr. David W. Kravitz Archivado el 9 de enero de 2013 en la Wayback Machine.
9. Werner Koch. "DSA y patentes"
10. . 26 de agosto de 2009 https://web.archive.org/web/20090826042831/http://csrc.nist.gov/groups/SMA/ispab/documents/94-rpt.txt . Archivado desde el original el 26 de agosto de 2009.
11. "FIPS PUB 180-4: Secure Hash Standard (SHS), marzo de 2012" (PDF) . csrc.nist.gov .
12. "Publicación especial NIST 800-57" (PDF) . csrc.nist.gov . Archivado desde el original (PDF) el 6 de junio de 2014.
13. "El desastre de Debian PGP que casi fue" . root labs rdist .
14. Requisitos de valor de DSA k {\displaystyle k}
15. Bendel, Mike (29 de diciembre de 2010). "Los piratas informáticos describen la seguridad de PS3 como una falla épica, obtienen acceso sin restricciones" . Exophase.com . Consultado el 5 de enero de 2011 .
16. Verbücheln, Stephan (2 de enero de 2015). "Cómo las carteras sin conexión perfectas pueden filtrar las claves privadas de Bitcoin". arXiv : 1501.00447 [ cs.CR ].

Enlaces externos

• FIPS PUB 186-4: Estándar de firma digital (DSS) , la cuarta (y actual) revisión de la especificación oficial de DSA.
• Recomendación para la gestión de claves - Parte 1: general , Publicación especial del NIST 800-57, p. 62–63