DSA

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de septiembre de 2016; las comprobaciones requieren 76 ediciones .

DSA, algoritmo de firma digital
Creador	NIST
Creado	1991
publicado	1998
Tamaño de clave	cerrado: 160-256 bits, abierto: 1024-3072 bits
Tamaño de la firma	dos números de 160-256 bits

DSA ( algoritmo de firma digital - algoritmo de firma digital ): un algoritmo criptográfico que utiliza una clave privada (de un par de claves: <pública; privada>) para crear una firma electrónica , pero no para el cifrado (a diferencia de RSA y el esquema ElGamal ). La firma se crea en secreto (clave privada) pero se puede verificar públicamente (clave pública). Esto significa que solo un sujeto puede crear una firma de mensaje, pero cualquiera puede verificar que sea correcta. El algoritmo se basa en la complejidad computacional de tomar logaritmos en campos finitos .

El algoritmo fue propuesto por el Instituto Nacional de Estándares y Tecnología ( EE . UU .) en agosto de 1991 y está patentado [1] (autor de la patente: David W. Kravitz), NIST puso esta patente a disposición para su uso sin regalías . DSA es parte del DSS ( Digital Signature Standard), publicado por primera vez el 15 de diciembre de 1998 (documento FIPS-186 [2] ( Federal Information Processing Standards ) . El estándar ha sido actualizado varias veces [3] [4] , la última versión es FIPS-186-4 [5] . (Julio 2013).

Descripción del algoritmo

DSA incluye dos algoritmos (S, V): para crear una firma de mensaje (S) y para verificarla (V).

Ambos algoritmos calculan primero el hash del mensaje utilizando una función hash criptográfica . El algoritmo S usa el hash y la clave secreta para crear la firma, el algoritmo V usa el hash del mensaje, la firma y la clave pública para verificar la firma.

Vale la pena enfatizar que no es el mensaje (de longitud arbitraria) lo que realmente está firmado, sino su hash (160 - 256 bits), por lo que las colisiones son inevitables y una firma, en general, es válida para varios mensajes con el mismo hash. . Por lo tanto, la elección de una función hash suficientemente "buena" es muy importante para todo el sistema en su conjunto. La primera versión del estándar usó la función hash SHA-1 [6] [2] ( Secure Hash Algorithm - algoritmo hash seguro) , en la última versión también puede usar cualquier algoritmo de la familia SHA-2 [6] [5 ] . En agosto de 2015, se publicó FIPS-202 [7] , que describe la nueva función hash SHA-3 . Pero hoy en día no está incluido en el estándar DSS [5] .

El sistema requiere una base de correspondencia entre los datos reales del autor (puede ser un individuo o una organización) y las claves públicas , así como todos los parámetros necesarios del esquema de firma digital (función hash, números primos ). Por ejemplo, una autoridad de certificación puede servir como base .

Opciones del esquema de firma digital

Para construir un sistema de firma digital, debe realizar los siguientes pasos:

Elección de la función hash criptográfica H(x).
Elegir un número primo q cuya dimensión N en bits sea la misma que la dimensión en bits de los valores hash H(x).
Elegir un número primo p tal que (p-1) sea divisible por q . La longitud de bits p se denota por L .
Elegir un número g ( ) tal que su orden multiplicativo módulo p sea igual a q . Para calcularlo, puedes usar la fórmula , donde h es un número arbitrario tal que . En la mayoría de los casos, el valor h = 2 satisface este requisito. [5] $g\neq 1$ $g=h^{{(p-1)/q}}\mod p$ $h\in(1;p-1)$ $g\neq 1$

Como se mencionó anteriormente, el parámetro principal del esquema de firma digital es la función hash criptográfica utilizada para convertir el texto del mensaje en un número para el cual se calcula la firma. Una característica importante de esta función es la longitud en bits de la secuencia de salida, indicada como N a continuación . En la primera versión del estándar DSS , se recomienda la función SHA-1 [2] y, en consecuencia, la longitud de bits del número con signo es de 160 bits. Ahora SHA-1 ya no es lo suficientemente seguro [8] [9] . La norma especifica los siguientes posibles pares de valores para los números L y N :

L=1024, N=160
L=2048, N=224
L=2048, N=256
L=3072, N=256

Las funciones hash de la familia SHA-2 se recomiendan bajo este estándar . Las organizaciones del gobierno de los EE. UU. deben usar una de las tres primeras opciones, las CA deben usar un par que sea igual o mayor que el par que usan los suscriptores [5] . El diseñador del sistema puede elegir cualquier función hash válida. Por lo tanto, no se centrará más atención en el uso de una función hash particular.

La fuerza de un criptosistema basado en DSA no supera la fuerza de la función hash utilizada y la fuerza del par (L,N), cuya fuerza no es mayor que la fuerza de cada uno de los números por separado. También es importante considerar cuánto tiempo debe permanecer seguro el sistema. Actualmente, para los sistemas que deben ser persistentes hasta 2010 ( 2030 ), se recomienda una longitud de 2048 (3072) bits. [5] [10]

Claves públicas y privadas

La clave secreta es un número. $x\in(0,q)$
La clave pública se calcula mediante la fórmula $y=g^{x}\mod p$

Los parámetros públicos son números (p, q, g, y) . Solo hay un parámetro privado: el número x . En este caso, los números (p, q, g) pueden ser comunes para un grupo de usuarios, y los números x e y son las claves pública y privada de un usuario en particular, respectivamente. Al firmar un mensaje, se utilizan números secretos x y k , y el número k debe elegirse aleatoriamente (en la práctica, pseudoaleatoriamente) al calcular la firma de cada mensaje siguiente.

Dado que (p, q, g) puede utilizarse para varios usuarios, en la práctica los usuarios suelen dividirse según algunos criterios en grupos con el mismo (p, q, g) . Por lo tanto, estos parámetros se denominan Parámetros de Dominio. [5]

Firma del mensaje

La firma del mensaje se realiza de acuerdo con el siguiente algoritmo [5] :

Escoger un número al azar $k\in(0,q)$
cálculo $r=(g^{k}\mod p)\mod q$
Elegir otro k si $r=0$
cálculo $s=k^{{-1}}(H(m)+x\cdot r)\mod q$
Elegir otro k si $s=0$
La firma es un par de largo total $(r, s)$ $2N$

Las operaciones computacionalmente complejas son módulo de exponenciación (cálculo ), para el cual existen algoritmos rápidos , cálculo hash , donde la complejidad depende del algoritmo hash elegido y del tamaño del mensaje de entrada, y encontrar el elemento inverso usando, por ejemplo, el euclidiano extendido algoritmo o pequeño teorema de Fermat en forma . $g^{k}{\bmod {p))$ $H(x)$ $k^{-1}{\bmod {q))$ $k^{-1}{\bmod {q}}=k^{q-2}{\bmod {q}}$

Verificación de firma

La verificación de la firma se realiza de acuerdo con el algoritmo [5] :

1 Cálculo 2 Cálculo 3 Cálculo 4 Cálculo 5 La firma es correcta si

w=s^{{-1}}\modq

u_{1}=H(m)\cdot w\mod q

u_{2}=r\cdot w\mod q

v=(g^{{u_{1}}}\cdot y^{{u_{2}}}\mod p)\mod q

{\ estilo de visualización v = r}

Cuando está marcada, las operaciones computacionalmente complejas son dos exponenciaciones , un cálculo hash y la búsqueda del elemento inverso . $g^{u_{1}}y^{u_{2}}$ $H(x)$ $s^{-1}{\bmod {q))$

Corrección del esquema

Este esquema de firma digital es correcto en la medida en que una persona que desee verificar la autenticidad de la firma siempre recibirá un resultado positivo en caso de autenticidad. Vamos a mostrarlo:

Primero, si , entonces por el Pequeño Teorema de Fermat se sigue que . Dado que g > 1 y q es primo, entonces g debe tener el orden multiplicativo q módulo p . $g=h^{{(p-1)/q}}\mod p$ $g^{q}=h^{{p-1}}=1\mod p$

Para firmar un mensaje, calcula

s=k^{{-1}}(H(m)+x\cdot r)\mod {q}.

Por lo tanto

k=H(m)\cdot s^{{-1}}+x\cdot r\cdot s^{{-1}}=H(m)\cdot w+x\cdot r\cdot w\mod { q}.

Como g es de orden q , obtenemos

g^{k}=g^{{H(m)\cdot w\mod q}}g^{{x\cdot r\cdot w\mod q}}=g^{{H(m)\cdot w \mod q}}y^{{r\cdot w\mod q}}=g^{{u1}}y^{{u2}}\mod {p}.

Finalmente, la corrección del esquema DSA se sigue de

r=(g^{k}\mod p)\mod q=(g^{{u1}}y^{{u2}}\mod p)\mod q=v.

[5]

Ejemplo de trabajo

Demos un ejemplo de cómo funciona el algoritmo para números pequeños. Dejemos el valor hash de nuestro mensaje . ${\ estilo de visualización H = 9}$

Generación de parámetros

$H=9_{10}=1001_{2}$
longitud de hash , para que pueda elegir $cuatro$ ${\ estilo de visualización q = 11_ {10} = 1011_ {2))$
elegir porque ${\ estilo de visualización p = 23}$ ${\ estilo de visualización 23-1 = 22 = 2 * q}$
elegir ${\ estilo de visualización g = 2 ^ {2} = 4}$

Creación de claves

elegir como la clave secreta ${\ estilo de visualización x = 7}$
entonces la clave publica $y=g^{x}{\bmod {p}}=4^{7}{\bmod {2}}3=16384{\bmod {2}}3=(712\cdot 23+8) {\bmod {2}}3=8$

Firma del mensaje

elegir $k = 3$
después $r=(g^{k}{\bmod {p))){\bmod {q}}=(4^{3}{\bmod {2}}3){\bmod {1}}1 =7$
${\ estilo de visualización r \ neq 0}$ , siga adelante
$s=k^{-1}(H(m)+x\cdot r){\bmod {q}}=4(9+7\cdot 7){\bmod {1}}1=1$ , donde se tiene en cuenta que $3^{-1}{\bmod {1}}1=4$
$s\neq 0$ , siga adelante
la firma es un par de numeros ${\ estilo de visualización (r, s) = (7,1)}$

Verificación de firma

$w=s^{-1}{\bmod {q}}=1^{-1}{\bmod {1}}1=1$
$u_{1}=H(m)\cdot w{\bmod {q}}=9\cdot 1{\bmod {1}}1=9$
$u_{2}=r\cdot w{\bmod {q}}=7\cdot 1{\bmod {1}}1=7$
$v=(g^{u_{1}}\cdot y^{u_{2}}{\bmod {p}}){\bmod {q}}=(4^{9}\cdot 8^ {7}{\bmod {2}}3){\bmod {1}}1=7$
recibido, lo que significa que la firma es correcta. $v = r$

Análogos

El algoritmo DSA se basa en la dificultad de calcular logaritmos discretos y es una modificación del esquema clásico de ElGamal [11] , en el que se agrega hash de mensajes y todos los logaritmos se calculan mediante , lo que hace posible que la firma sea más corta en comparación con los análogos. [12] . Con base en el esquema de ElGamal, también se construyeron otros algoritmos, por ejemplo, el ruso GOST 34.10-94 , que ahora se considera obsoleto. Fue reemplazado por el estándar GOST R 34.10-2012 [13] , que utiliza un grupo de puntos de una curva elíptica . $mod~q$

Tal modificación, i.e. la transición del grupo multiplicativo módulo un número primo al grupo de puntos de curva elíptica también existe para DSA - ECDSA [14] ( Algoritmo de firma digital de curva elíptica - algoritmo de firma digital en curvas elípticas) . Se utiliza, por ejemplo, en la criptomoneda bitcoin para confirmar transacciones. Esta traducción le permite reducir el tamaño de las claves sin sacrificar la seguridad: en el sistema bitcoin, el tamaño de la clave privada es de 256 bits y la clave pública correspondiente es de 512 bits.

Otro algoritmo común de clave pública (utilizado tanto para el cifrado como para la firma digital), RSA (llamado así por los autores: Rivest , Shamir , Adleman ), se basa en la dificultad de factorizar números grandes.

Fuerza criptográfica

Cualquier ataque al algoritmo se puede describir de la siguiente manera: un atacante recibe todos los parámetros de la firma pública y un determinado conjunto de pares (mensaje, firma) e intenta, utilizando este conjunto, crear una firma válida para un nuevo mensaje no representado en el conjunto. .

Estos ataques se pueden dividir condicionalmente en dos grupos: en primer lugar, un atacante puede intentar recuperar la clave secreta e inmediatamente tiene la oportunidad de firmar cualquier mensaje y, en segundo lugar, puede intentar crear una firma válida para un nuevo mensaje sin recuperar directamente la clave secreta. $X$

Previsibilidad de un parámetro aleatorio

La distribución uniforme del parámetro aleatorio es muy importante para la seguridad del sistema. Si se conocen varios bits de parámetros consecutivos para una serie de firmas, la clave secreta se puede recuperar con una alta probabilidad. [quince] $k$ $k$

Repetir el parámetro para dos mensajes conduce a una simple piratería del sistema. Esto puede suceder cuando se utiliza un generador de números pseudoaleatorios defectuoso . Esta vulnerabilidad en el sistema PlayStation 3 permitía firmar cualquier programa en nombre de Sony . En algunas implementaciones del sistema bitcoin para Android, un atacante podría acceder a la billetera. [16] [17] Ambos ejemplos utilizaron el sistema ECDSA [14] .

Si se usó el mismo parámetro para dos mensajes , entonces sus firmas tendrán la misma pero diferente , llamémoslos . $m_{1},m_{2}$ $k$ $(r, s)$ $r$ $s$ ${\ estilo de visualización s_{1},s_{2))$

De la expresión para podemos expresar el total : $s$ $k$

$k=(H(m)+xr)s^{-1}\mod q$ .

Y equiparar común para diferentes mensajes: $k$

$(H(m_{1})+xr)s_{1}^{-1}\mod q=(H(m_{2})+xr)s_{2}^{-1}\mod q$

Desde aquí es fácil expresar la clave secreta : $X$

$x={\frac {H(m_{1})s_{1}^{-1}-H(m_{2})s_{2}^{-1}}{r(s_{2} ^{-1}-s_{1}^{-1})}}$

Falsificación existencial

Algunos algoritmos de firma digital pueden ser atacados por una falsificación existente (falsificación existencial) . Se encuentra en el hecho de que para una firma (ya sea aleatoria o creada de acuerdo con alguna regla) es posible crear un mensaje correcto (que, sin embargo, generalmente no tiene sentido) utilizando solo parámetros públicos.

Para el esquema DSA, la firma , en cualquier caso , es válida para un mensaje con hash . $r=g^{e}y\mod p\mod q$ ${\ estilo de visualización s = r}$ $mi$ $H(m)=es$

Esta es una de las razones para codificar el mensaje de entrada. Si la función hash se elige correctamente, el algoritmo DSA está protegido de este ataque, porque la inversión de la función hash criptográfica (es decir, para un hallazgo dado tal que ) es computacionalmente difícil. [Dieciocho] $k$ $metro$ ${\ Displaystyle H (m) = k}$

Recuperación de clave

la condición de corrección de la firma se puede reescribir en una forma diferente:

$g^{ks}\mod p\mod q=g^{H(m)+xr}\mod p\mod q$

esta ecuación es equivalente (porque el orden multiplicativo de g módulo p es igual a q)

$H(m)\mod q=ks-xr\mod q$

por lo que podemos suponer que para recuperar la clave, el atacante necesita resolver un sistema de ecuaciones de la forma

$H(m_{i})\mod q=k_{i}s_{i}-xr_{i}\mod q$

pero en este sistema es incógnita y nada más , lo que quiere decir que el número de incógnitas es una más que las ecuaciones, y para cualquiera existen las que satisfacen el sistema. Dado que q es un número primo grande, se requerirá un número exponencial de pares (mensaje, firma) para la recuperación. [una] $X$ $k_i$ $X$ $k_i$ ${\ estilo de visualización x \ mod q}$

Falsificación de firma

Puedes intentar falsificar una firma sin conocer la clave secreta, es decir, intentar resolver la ecuación

$r^{s}\mod p\mod q=g^{H(m)}y^{r}\mod p\mod q$

con respecto a y . Para cada fijo , la ecuación es equivalente a calcular el logaritmo discreto. [una] $r$ $s$ $r$

Sistema de Verificación de Implementación de Algoritmos

Los términos de la licencia le permiten implementar el algoritmo en software y hardware. NIST creó DSAVS [19] ( Ing. The Digital Signature Algorithm Validation System - un sistema para verificar el algoritmo de firma digital ). DSAVS consta de varios módulos de prueba de cumplimiento que prueban cada componente del sistema independientemente de los demás. Componentes de implementación probados:

Generación de parámetros de dominio
Comprobación de la configuración del dominio
Generación de un par de claves pública-privada
crear una firma
Verificación de firma

Para probar la implementación, el desarrollador debe enviar una solicitud para probar su implementación al laboratorio CMT ( Laboratorio de Pruebas de Módulos Criptográficos ) . [5]

Generación de números primos

El algoritmo DSA requiere dos primos ( y ), por lo que se necesita un generador de primos o pseudo -primos . $pags$ $q$

El algoritmo de Shaw-Taylor [20] se utiliza para generar números primos .

Los pseudoprimos se generan usando una función hash y la prueba probabilística de Miller-Rabin se usa para probar la primalidad . Se le puede agregar una sola prueba de primalidad de Luke . [5]

El número requerido de iteraciones depende de la longitud de los números utilizados y del algoritmo de verificación [5] :

opciones	solo prueba M-R	Prueba M-R + prueba de Luke
p: 1024 bits q: 160 bits probabilidad de error ${\ estilo de visualización 2^{-80}}$	40	pag: 3 q:19
p: 2048 bits q: 224 bits probabilidad de error ${\ estilo de visualización 2^{-112}}$	56	pag: 3 q:24
p: 2048 bits q: 256 bits probabilidad de error ${\ estilo de visualización 2^{-112}}$	56	pag: 3 q:27
p: 3072 bits q: 256 bits probabilidad de error ${\ estilo de visualización 2^{-128}}$	64	pag: 2 q:27

Generación de números aleatorios

El algoritmo también requiere un generador de números aleatorios o pseudoaleatorios . Este generador es necesario para generar una clave privada de usuario x , así como para generar un parámetro aleatorio secreto . $k$

El estándar ofrece varias formas de generar números pseudoaleatorios utilizando cifrados de bloques o funciones hash. [5] [21]

Notas

↑ 123 Patente de EE. UU. 5231668 A .
↑ 123 FIPS 186-1 ._ _
↑ FIPS 186-2 .
↑ FIPS 186-3 .
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 FIPS 186-4 .
↑ 12 FIPS 180-4 .
↑ FIP 202 .
↑ Encontrar colisiones en el SHA-1 completo .
↑ Colisión de inicio libre para SHA-1 completo .
↑ Publicación especial del NIST 800-57 .
↑ Elgamal, 1985 .
↑ CP Schnorr. Identificación y Firmas Eficientes para Tarjetas Inteligentes // Avances en Criptología - CRYPTO' 89 Proceedings / Gilles Brassard. — Nueva York, NY: Springer, 1990. — P. 239–252 . - ISBN 978-0-387-34805-6 . -doi : 10.1007/ 0-387-34805-0_22 . Archivado desde el original el 12 de abril de 2022.
↑ GOST R 34.11-2012
↑ 1 2 El algoritmo de firma digital de curva elíptica (ECDSA) .
↑ La inseguridad del algoritmo de firma digital con nonces parcialmente conocidos .
^ ECDSA: fallas de aplicación e implementación .
↑ Criptografía de curva elíptica en la práctica .
↑ Argumentos de seguridad para firmas digitales y firmas ciegas .
↑ El sistema de validación del algoritmo de firma digital .
↑ Generación de números primos fuertes .
↑ Generación de números aleatorios .

Literatura

Normas y patentes

FIPS. PUBLICACIÓN 186-1 .
FIPS. PUBLICACIÓN 186-2 .
FIPS. PUBLICACIÓN 186-3 .
FIPS. PUBLICACIÓN 186-4 .
FIPS. PUBLICACIÓN 180-4 . Archivado desde el original el 26 de noviembre de 2016.
FIPS. PUB 202 (inglés) .
FIPS. PUB 202 (inglés) .
David W. Kravitz. Algoritmo de firma digital 5231668 A (inglés) .
Publicación especial NIST 800-57 Parte 1 Revisión 4. Recomendación para la administración de claves .
GOST R 34.10-2012. Tecnologías de la información. Protección criptográfica de la información. Procesos de formación y verificación de firma digital electrónica . (Ruso)
El Sistema de Validación de Algoritmo de Firma Digital .

Artículos

Marc Stevens, Pierre Karpman, Thomas Peyrin. Colisión de inicio libre para SHA- 1 completo .
Publicación especial NIST 800-90A Recomendación para la generación de números aleatorios mediante generadores de bits aleatorios deterministas .
J. Shawe-Taylor. Generación de primos fuertes .
Xiaoyun Wang, Yiqun Lisa, Hongbo Yu. Búsqueda de colisiones en el SHA-1 completo .
Phong Q. Nguyen, Igor E. Shparlinski. La Inseguridad del Algoritmo de Firma Digital con Nonces Parcialmente Conocidos .
David Pointcheval, Jacques Stern. Argumentos de Seguridad para Firmas Digitales y Firmas Ciegas .
Markus Schmid. ECDSA - Fallos de Aplicación e Implementación .
Don Johnson, Alfred Menezes, Scott Vanstone. El algoritmo de firma digital de curva elíptica (ECDSA ) .
Elgamal T. Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos, un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos // IEEE Trans . inf. Teoría / F. Kschischang - IEEE , 1985. - Vol. 31, edición. 4.- Pág. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Joppe W. Bos, J. Alex Halderman, Nadia Heninger, Jonathan Moore, Michael Naehrig, Eric Wustrow. Criptografía de curva elíptica en la práctica .

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP