Algoritmo de firma digital

Estándar de verificación 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 el problema del logaritmo discreto . En un criptosistema de clave pública, se generan dos claves: los datos sólo se pueden cifrar con la clave pública y los datos cifrados sólo se pueden descifrar con la clave privada. DSA es una variante de los esquemas de firma 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 cinco revisiones de la especificación inicial. La especificación más nueva es: FIPS 186-5 de febrero de 2023. ^[3] DSA está patentada, pero el NIST ha hecho que esta patente esté disponible en todo el mundo sin derechos de autor. La especificación FIPS 186-5 indica que DSA ya no será aprobado para la generación de firmas digitales, pero podrá usarse para verificar las firmas generadas antes de la fecha de implementación de ese estándar.

Descripción general

El DSA funciona en el marco de 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 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 lo ha hecho). firmó el mensaje).

Historia

En 1982, el gobierno de Estados Unidos 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). Al principio hubo críticas importantes, especialmente por parte de empresas de software que ya habían invertido esfuerzos en desarrollar software de firma digital basado en el criptosistema RSA . ^{[1] : 484} Sin embargo, NIST adoptó DSA como estándar federal (FIPS 186) en 1994. Se han publicado cinco revisiones de la especificación inicial: FIPS 186–1 en 1998, ^[4] FIPS 186–2 en 2000, ^{[5 ]} FIPS 186–3 en 2009, ^[6] FIPS 186–4 en 2013, ^[3] y FIPS 186–5 en 2023. ^[7] El estándar FIPS 186-5 prohíbe firmar con DSA, pero permite la verificación de firmas generadas antes de la fecha de implementación de la norma como documento. Será reemplazado por esquemas de firma más nuevos, como EdDSA . ^[8]

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, ^[9] 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 el NIST ha hecho que esta patente esté disponible en todo el mundo libre de regalías. ^[10] Claus P. Schnorr afirma que su patente estadounidense 4.995.082 (también ahora vencida) cubría DSA; esta afirmación está en disputa. ^[11]

En 1993, Dave Banisar logró obtener confirmación, a través de una solicitud FOIA , de que el algoritmo DSA no había sido diseñado por el NIST, sino por la NSA. ^[12]

OpenSSH anunció que está previsto que DSA se elimine en 2025. ^[13]

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 único 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 potentes están aprobadas para su uso en el DSS actual. ^{[3] [14]} 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 estaba obligado a ser un múltiplo de 64 entre 512 y 1024 inclusive. NIST 800-57 recomienda longitudes de 2048 (o 3072) para claves con una vida útil de seguridad que se extiende más allá de 2010 (o 2030). ^[15] ${\displaystyle L}$ ${\displaystyle L}$
• Elija la longitud del módulo tal que y . FIPS 186-4 especifica y debe 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 bit primo . ${\displaystyle N}$ ${\displaystyle q}$
• Elija un número primo de bits que sea múltiplo de . ${\displaystyle L}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle q}$
• Elija un número entero al azar de . ${\displaystyle h}$ ${\displaystyle \{2\ldots p-2\}}$
• Calcular . En el raro caso de que vuelva a intentarlo con un archivo diferente . Se utiliza 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 podrán ser compartidos 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 único usuario:

• Elija un número entero al azar de . ${\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}$

2. 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 en secreto la clave privada. ${\displaystyle y}$ ${\displaystyle x}$

3. Firma

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 de que así sea , 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 de que así sea , 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 de y equivale a crear una nueva clave por mensaje. La exponenciación modular en informática es la parte más costosa desde el punto de vista computacional de la operación de firma, pero puede calcularse antes de que se conozca el mensaje. Calcular el inverso modular es la segunda parte más costosa y también puede calcularse antes de que se conozca el mensaje. Puede calcularse utilizando el algoritmo euclidiano extendido o utilizando el pequeño teorema de Fermat como . ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle k^{-1}{\bmod {\,}}q}$ ${\displaystyle k^{q-2}{\bmod {\,}}q}$

4. Verificación de 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 sólo si . ${\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 , se sigue que 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}$

De este modo

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

Como tiene orden tenemos ${\displaystyle g}$ ${\displaystyle q}$

${\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 unicidad 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. ^[16] Usar el mismo valor dos veces (incluso mientras se mantiene en secreto), usar un valor predecible o filtrar incluso unos pocos bits en cada una de varias firmas es suficiente para revelar la clave privada . ^[17] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x}$

Este problema afecta tanto al DSA como al algoritmo de firma digital de curva elíptica ( ECDSA ): en diciembre de 2010, el grupo fail0verflow anunció la recuperación de la clave privada ECDSA utilizada por Sony para firmar el software de la consola de juegos PlayStation 3 . El ataque fue posible porque Sony no logró generar una nueva secuencia aleatoria para cada firma. ^[18] ${\displaystyle k}$

Este problema se puede evitar derivando de manera determinista la clave privada y el hash del mensaje, como se describe en RFC  6979. Esto garantiza 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, se podría filtrar una clave privada fuera de línea desde un dispositivo fuera de línea perfecto que solo emitiera firmas de apariencia inocente. ^[19] ${\displaystyle k}$

Implementaciones

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

• botánico
• Castillo inflable
• criptolib
• Cripto++
• libgcrypt
• Ortiga
• AbiertoSSL
• loboCripta
• GnuTLS

Ver también

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

Referencias

1. Schneier, Bruce (1996). Criptografía aplicada. Wiley. 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), 15 de diciembre de 1998" (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. "FIPS PUB 186-5: Estándar de firma digital (DSS), febrero de 2023" (PDF) . csrc.nist.gov .
8. "Estándar de firma digital (DSS)". Departamento de Comercio de EE. UU. 31 de octubre de 2019 . Consultado el 21 de julio de 2020 .
9. Dr. David W. Kravitz Archivado el 9 de enero de 2013 en Wayback Machine .
10. Werner Koch. "DSA y patentes"
11. "Informe Anual 1994 de CSSPAB". 26 de agosto de 2009. Archivado desde el original el 26 de agosto de 2009.
12. Neumann, Peter G. (29 de febrero de 2020). "The RISKS Digest Volumen 14, Número 59". Archivado desde el original el 29 de febrero de 2020 . Consultado el 3 de octubre de 2023 .{{cite web}}: CS1 maint: bot: original URL status unknown (link)
13. "OpenSSH anuncia el cronograma de eliminación de DSA [LWN.net]". lwn.net . Consultado el 11 de enero de 2024 .
14. "FIPS PUB 180-4: Secure Hash Standard (SHS), marzo de 2012" (PDF) . csrc.nist.gov .
15. "Publicación especial del NIST 800-57" (PDF) . csrc.nist.gov . Archivado desde el original (PDF) el 6 de junio de 2014.
16. "El desastre de Debian PGP que casi fue". laboratorios raíz rdist . 18 de mayo de 2009.
17. DSA k {\displaystyle k} -valor Requisitos
18. Bendel, Mike (29 de diciembre de 2010). "Los piratas informáticos describen la seguridad de PS3 como un error épico y obtienen acceso sin restricciones". Exofase.com . Consultado el 5 de enero de 2011 .
19. Verbücheln, Stephan (2 de enero de 2015). "Cómo las billeteras perfectas sin conexión aún pueden filtrar 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 DSA.
• Recomendación para la gestión de claves - Parte 1: general, Publicación especial del NIST 800-57, p. 62–63