Algoritmo de firma digital

Norma de verificación digital

El algoritmo de firma digital ( DSA ) es un criptosistema de clave pública y 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 . En un criptosistema de clave pública, se generan dos claves: los datos solo se pueden cifrar con la clave pública y los datos cifrados solo 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 el 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 reciente es: FIPS 186-5 de febrero de 2023. ^[3] El DSA está patentado, pero el NIST ha puesto esta patente a disposición en todo el mundo libre de regalías. La especificación FIPS 186-5 indica que el DSA ya no será aprobado para la generación de firmas digitales, pero se puede utilizar para verificar firmas generadas antes de la fecha de implementación de ese estándar.

Descripción general

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 consiste en una clave pública y una clave privada. La clave privada se utiliza para generar una firma digital para un mensaje, y dicha firma puede verificarse 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 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 el uso de DSA en su Estándar de Firma Digital (DSS). Al principio hubo críticas significativas, especialmente por parte 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} Sin embargo, NIST adoptó DSA como un 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, 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 . ^[8]

La DSA está amparada 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 puesto esta patente a disposición 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 la DSA; esta afirmación es discutida. ^[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 eliminar DSA 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 consta de dos fases. La primera fase consiste en la elección de parámetros de algoritmo que pueden ser compartidos entre distintos usuarios del sistema, mientras que la segunda fase consiste en calcular un único par de claves para un usuario.

Generación de parámetros

• Elija una función hash criptográfica aprobada con una longitud de salida de bits. 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] [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 restringía su uso a 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 extienda más allá de 2010 (o 2030). ^[15] ${\displaystyle L}$ ${\displaystyle L}$
• Elija la longitud del módulo de manera que y . FIPS 186-4 especifica que y tenga 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 primo de -bit tal que sea múltiplo de . ${\displaystyle L}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle q}$
• Elija un número entero al azar entre . ${\displaystyle h}$ ${\displaystyle \{2\ldots p-2\}}$
• Calcular . En el caso poco frecuente de que se vuelva a intentar con un . 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 pueden 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 solo usuario:

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

El 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 , comience de nuevo con un valor aleatorio diferente . ${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$ ${\displaystyle r=0}$ ${\displaystyle k}$
• Calcular . En el improbable caso de que , comience de nuevo con un valor aleatorio 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 computacionalmente de la operación de firma, pero puede calcularse antes de que se conozca el mensaje. Calcular la inversa 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 que 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 auténticas. Esto se puede demostrar de la siguiente manera:

En primer lugar, dado que , se deduce que por el pequeño teorema de Fermat . Como 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 computa

${\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}}}$

Desde que tenemos 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 corrección del DSA se desprende 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. Son tan críticos 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 algunos bits de 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 a DSA como a Elliptic Curve Digital Signature Algorithm ( ECDSA ): en diciembre de 2010, el grupo fail0verflow anunció la recuperación de la clave privada ECDSA utilizada por Sony para firmar software para la consola de juegos PlayStation 3. El ataque fue posible porque Sony no generó una nueva clave aleatoria para cada firma. ^[18] ${\displaystyle k}$

Este problema se puede evitar derivando de manera determinista de 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 cuando se desee filtrar información de manera subliminal a través de firmas. Por ejemplo, una clave privada sin conexión podría filtrarse desde un dispositivo sin conexión perfecto que solo publicara 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ánica
• Castillo inflable
• criptalib
• Criptomoneda++
• libgcrypt
• Ortiga
• OpenSSL
• Cripta del lobo
• GnuTLS

Véase también

• Aritmética modular
• RSA (criptosistema)
• Sistema de alerta temprana 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), 1994-05-19". 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), 27 de enero de 2000" (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 Estados Unidos. 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 de 1994 de la 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 Volume 14 Issue 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: Estándar de hash seguro (SHS), marzo de 2012" (PDF) . csrc.nist.gov .
15. "Publicación especial 800-57 del NIST" (PDF) . csrc.nist.gov . Archivado desde el original (PDF) el 6 de junio de 2014.
16. "El desastre de Debian PGP que casi ocurrió". root labs rdist . 18 de mayo de 2009.
17. Requisitos del valor k {\displaystyle k} de DSA
18. Bendel, Mike (29 de diciembre de 2010). "Los piratas informáticos describen la seguridad de PS3 como un fracaso épico y obtienen acceso sin restricciones". Exophase.com . Consultado el 5 de enero de 2011 .
19. Verbücheln, Stephan (2 de enero de 2015). "Cómo las carteras offline perfectas 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 NIST 800-57, págs. 62-63