| DSS, estándar de firma digital | |
|---|---|
| Creador | Instituto Nacional de Normas y Tecnología |
| Creado | agosto de 1991 |
| Tamaño de clave | 512-1024 bits |
| Tamaño de la firma | dos números de 160 bits |
DSS ( Digital Signature Standard ) es un estándar estadounidense que describe el algoritmo de firma digital ( DSA ) que se puede utilizar para generar una firma digital . La firma digital se utiliza para establecer cambios de datos y para autenticar al firmante. El destinatario de los datos firmados puede utilizar la firma digital para demostrar a un tercero que la firma fue efectivamente realizada por el remitente.
Cuando se recibe un mensaje, el destinatario puede desear verificar si el mensaje ha sido alterado en tránsito. El destinatario también puede querer verificar la identidad del firmante. El DSA hace posible hacer esto.
El DSA es utilizado por un lado para generar la firma de datos y el otro lado para autenticar al suscriptor. La firma se genera utilizando la clave privada. Cualquiera de las partes puede verificar la autenticidad de una firma digital utilizando la clave pública. La clave pública se envía junto con los datos firmados. Las claves pública y privada no coinciden.
Al generar una firma, se utiliza una función hash para obtener una versión comprimida de los datos. Los datos recibidos son procesados por el DSA para obtener una firma digital. La misma función hash se utiliza para verificar la firma. La función hash se describe en SHS (Secure Hash Standard).
| Uso de SHA con DSA |
|---|
DSA utiliza los siguientes parámetros:
1. p es un número primo p, donde 2 L-1 < p < 2 L , 512 =< L =< 1024 y L es un múltiplo de 64 2. q es un divisor primo de p-1, donde 2 159 < q < 2 160 3. g = h (p-1)/q mod p, donde h es cualquier entero 1 < h < p - 1 tal que h (p-1)/q mod p > 1 4. x es un número entero aleatorio o pseudoaleatorio, donde 0 < x < q 5. y = g x módulo p 6. k es un número entero aleatorio o pseudoaleatorio, donde 0 < k < q.Los números enteros p, q y g pueden ser públicos y pueden ser compartidos por un grupo de personas. x e y son claves privadas y públicas, respectivamente. Los parámetros x y k solo se utilizan para generar la firma y deben mantenerse en secreto. El parámetro k es diferente para cada firma.
La firma del mensaje M es un par de números r y s, donde
SHA(M) es una cadena binaria de 160 bits.
Si r = 0 o s = 0, se debe generar una nueva k y calcular una nueva firma. Si la firma se calculó correctamente, la probabilidad de que r = 0 o s = 0 es muy pequeña.
La firma se envía junto con el mensaje al destinatario.
Los números p, q, g y la clave pública son de dominio público.
Sean M', r' y s' las versiones recibidas de M, r y s, respectivamente, y sea y la clave pública. Al verificar una firma, primero debe ver si se cumplen las siguientes desigualdades:
0 < r' < q 0 < s' < q.Si al menos una desigualdad no se cumple, la firma debe ser rechazada. Si se cumplen las condiciones de desigualdad, se realizan los siguientes cálculos:
Si v = r', entonces se confirma la autenticidad de la firma.
Si v ≠ r', entonces el mensaje puede haber sido alterado, el mensaje puede haber sido firmado incorrectamente o el mensaje puede haber sido firmado por un estafador. En este caso, los datos recibidos deben considerarse dañados.
Esta sección incluye algoritmos para generar números primos p y q para DSA. Estos algoritmos utilizan un generador de números aleatorios.
Para generar primos p y q, se necesita una prueba de primalidad. Hay varias pruebas rápidas de probabilidad. En nuestro caso, se utilizará una versión simplificada de la prueba de Miller-Rabin . Si la prueba se repite n veces, producirá un número primo con una probabilidad de error de 1/4 n como máximo . Para verificar si un número entero es primo, debe:
Paso 1. Establecer i = 1 y elegir n>=50. Paso 2. Iguale w con el número que se está probando y represéntelo como w = 1 + 2 a m, donde m es un número impar. Paso 3. Genera un número aleatorio b: 1 < b < w. Paso 4. Establecer j = 0 y z = b m mod w. Paso 5. Si j = 0 y z = 1, o si z = w - 1, vaya al paso 9. Paso 6. Si j > 0 y z = 1, vaya al paso 8. Paso 7. j = j + 1. Si j < a, establezca z = z 2 mod w y vaya al paso 5. Paso 8. w no es simple. Deténgase. Paso 9. Si i < n, establezca i = i + 1 y vaya al paso 3. De lo contrario, tal vez w sea un número primo.DSS requiere 2 números primos p y q, que deben cumplir las siguientes condiciones:
2 159 < q < 2 160 2 L-1 < p < 2 L , donde L = 512 + 64j, y 0 <= j < = 8 p - 1 es divisible por q.Para generar un q simple: 2 159 < q < 2 160 , se utilizan SHA-1 y una semilla SEED. Después de eso, el número SEED se usa para crear el número X: 2 L-1 < X < 2 L . Se obtiene un primo p redondeando X de modo que el número resultante sea 1 mod 2q.
Sea L - 1 = n*160 + b, donde b y n son números enteros y toman valores de 0 a 160.
Paso 1. Elegimos una secuencia arbitraria de al menos 160 bits y la llamamos SEMILLA. Sea g la longitud de la SEMILLA en bits. Paso 2. Calcular U = SHA[SEED] XOR SHA[(SEED+1) mod 2 g ]. Paso 3. Cree q a partir de U configurando LSB y MSB en 1: q = U O 2 159 O 1. Tenga en cuenta que 2 159 < q < 2 160 . Paso 4. Compruebe q por simplicidad. Paso 5. Si q no es simple, vaya al paso 1. Paso 6. Sea contador = 0 y compensación = 2. Paso 7. Para k = 0,...,n calcule Vk = SHA[(SEED + offset + k) mod 2 g ]. Paso 8 Calcular W = V 0 + V 1 *2 160 + ... + V n-1 *2 (n-1)*160 + (V n mod 2 b ) * 2 n*160 X = W + 2 L -1 . Tenga en cuenta que 0 <= W < 2 L-1 y 2 L-1 <= X < 2 L . Paso 9. Sea c = X mod 2q y p = X - (c - 1). Tenga en cuenta que p es igual a 1 mod 2q. Paso 10. Si p < 2 L-1 , vaya al paso 13. Paso 11. Compruebe p por simplicidad. Paso 12. Si p pasó la prueba en el paso 11, vaya al paso 15. Paso 13. contador = contador + 1 y desplazamiento = desplazamiento + n + 1. Paso 14. Si contador >= 2 12 = 4096 vaya al paso 1, de lo contrario vaya al paso 7. Paso 15 Guarde el SEED y el contador para confirmar que p y q se generaron correctamente.Cualquier implementación de DSA requiere números enteros aleatorios o pseudoaleatorios. Estos números se seleccionan utilizando los métodos descritos en esta sección u otros métodos aprobados por FIPS .
El algoritmo de la Sección 7.1 se puede utilizar para generar x. El algoritmo para k y r se describe en la sección 7.2. Los algoritmos utilizan una función unidireccional (una función cuyo recíproco es muy difícil de calcular) G(t, c) donde t es 160 bits, c es b bits (160 < b < 512) y G(t, c) es 160 bits G se puede crear utilizando el Algoritmo hash seguro ( SHA-1 ) o utilizando el Estándar de cifrado de datos ( DES ), descrito en las secciones 7.3 y 7.4, respectivamente.
Sea x la clave privada del firmante. El siguiente algoritmo se puede utilizar para generar m valores de x:
Paso 1. Elija un nuevo valor para la clave original, XKEY. Paso 2. En el sistema numérico hexadecimal t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. Este es el valor inicial para H 0 ||H 1 ||H 2 ||H 3 ||H 4 en SHS. Paso 3. Para j = 0..m - 1 una. XSEED j = valor opcional ingresado por el usuario. b. XVAL = (XKEY + XSEED j ) mod 2 b . C. xj = G(t, XVAL ) mod q. d. TECLAX = (1 + TECLAX + x j ) mod 2 b .Este algoritmo se puede utilizar para precalcular k, k −1 y r para m mensajes al mismo tiempo. Algoritmo:
Paso 1. Seleccione una semilla secreta para KKEY. Paso 2. En el sistema numérico hexadecimal t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301. Este es el cambio inicial para H 0 ||H 1 ||H 2 ||H 3 ||H 4 en SHS. Paso 3. Para j = 0..m - 1: una. k = G(t,KKEY) módulo q. b. Calcula k j −1 = k −1 mod q. C. Calcule r j = (g k mod p) mod q. d. KKEY = (1 + KKEY + k) mod 2 b . Paso 4. Suponga que M 0 , ... , M m-1 son los siguientes m mensajes. Para j = 0..m - 1: una. Sea h = SHA(M j ). b. s j = (k j −1 (h + xr j )) mod q. C. r j ,s j ) - firma para M j . Paso 5. t = h. Paso 6. Vaya al paso 3.El paso 3 permite calcular las cantidades necesarias para firmar los próximos m mensajes. El paso 4 se ejecuta inmediatamente después de recibir estos m mensajes.
G(t, c) se puede obtener usando SHA-1 , pero antes de eso, {H j } y M 1 deben inicializarse de la siguiente manera:
1. Inicialice {Hj} dividiendo el valor t de 160 bits en cinco segmentos de 32 bits: t = t 0 ||t 1 ||t 2 ||t 3 ||t 4 Entonces Hj = t j para j = 0..4. 2. El bloque de mensajes M 1 se define como sigue: M 1 = c||0 512-b (Los primeros b bits del mensaje M 1 contienen c, y los restantes (512-b) bits se ponen a cero).Después de eso, se ejecuta SHA-1 [1] y obtenemos una cadena G(t, c) de 160 bits, representada como:
H 0 || H 1 || H 2 || H 3 || H 4 .Sea a XOR b denote bit a bit XOR ( suma de módulo 2 ). Sean a 1 , a 2 , b 1 , b 2 de 32 filas. Sea b 1 ' los 24 bits menos significativos de b 1 . Sean K = b 1 '||b 2 y A = a 1 ||a 2 . Denotar
DES b1,b2 (a 1 ,a 2 ) = DES K (A)DES K (A) indica el cifrado DES normal [2] de un bloque A de 64 bits con una clave K de 56 bits. Supongamos que t y c tienen 160 bits cada uno. Para calcular G(t, c):
Paso 1. Grabación t = t 1 ||t 2 ||t 3 ||t 4 ||t 5 c = c 1 ||c 2 ||c 3 ||c 4 ||c 5 Cada t i y c i son 32 bits . Paso 2. Para i = 1..5: x yo = t yo XOR c yo Paso 3. Para i = 1..5: b 1 = c ((i+3) mod 5) + 1 b 2 = c ((i+2) mod 5) + 1 a 1 = x i a 2 = x (i mod 5) + 1 XOR x (( i+3) mod 5) + 1 y i,1 ||y i,2 = DES b1,b2 (a 1 ,a 2 ) (y i,1 , y i,2 = 32 bits) Paso 4. Para i = 1..5: z i = y i,1 XOR y ((i+1) mod 5)+1,2 XOR y ((i+2) mod 5)+1,1 Paso 5. G(t,c) = z 1 | |z 2 ||z 3 ||z 4 ||z 5Esta sección proporciona algoritmos para generar g, k −1 y s −1 que se utilizan en DSS. Para generar g:
Paso 1. La generación de p y q se describe anteriormente. Paso 2. Sea e = (p - 1)/q. Paso 3. Igualar h a cualquier número entero: 1 < h < p - 1. Paso 4. g = h e mod p. Paso 5. Si g = 1, vaya al paso 3.Para calcular n −1 mod q, donde 0 < n < q y 0 < n −1 < q:
Paso 1. i = q, h = n, v = 0 y d = 1. Paso 2. Sea t = i DIV h, donde DIV es la división de enteros. Paso 3. x = h. Paso 4. h = i - tx. Paso 5. i = x. Paso 6. x = d. Paso 7. d = v - tx. Paso 8. v = x. Paso 9. Si h > 0, vaya al paso 2. Paso 10. Sea n −1 = v mod q.Tenga en cuenta que en el paso 10, v puede ser negativo.
Sea L = 512 (tamaño p). En este ejemplo, todos los valores estarán en notación hexadecimal. Los valores p y q se generaron como se describe anteriormente utilizando el siguiente valor SEED de 160 bits:
SEMILLA = d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3Con esta SEMILLA, el algoritmo encontró p y q en el contador de tiempo = 105. x se generó usando el algoritmo descrito en la sección 7.1 usando SHA-1 para generar G (sección 7.3) XKEY de 160 bits:
XKEY=bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6 t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 x = G(t,XKEY) módulo qk se generó como se describe en la sección 7.2 usando SHA-1 para generar G (sección 7.3) KKEY de 160 bits:
KKEY = 687a66d9 0648f993 867e121f 4ddf9ddb 01205584 t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301 k = G(t,KKEY) módulo qFinalmente:
h = 2 p = 8df2a494 492276aa 3d25759b b06869cb eac0d83a fb8d0cf7 cbb8324f 0d7882e5 d0762fc5 b7210eaf c2e9adac 32ab7aac 49693dfb f83724c2 ec0736ee 31c80291 q=c773218c 737ec8ee 993b4f2d ed30f48e dace915f g = 626d0278 39ea0a13 413163a5 5b4cb500 299d5522 956cefcb 3bff10f3 99ce2c2e 71cb9de5 fa24babf 58e5b795 21925c9c c42e9f6f 464b088c c572af53 e6d78802 x = 2070b322 3dba372f de1c0ffc 7b2e3b49 8b260614 k = 358dad57 1462710f 50e254cf 1a376b2b muertofbf k − 1 = 0d516729 8202e49b 4116ac10 4fc3f415 ae52f917M = la palabra "abc" del alfabeto inglés ( ASCII )
(SHA-1)(M) = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d y = 19131871 d75b1612 a819f29d 78d1b0d7 346f7aa7 7bb62a85 9bfd6c56 75da9d21 2d3a36ef 1672ef66 0b8c7c25 5cc0ec74 858fba33 f44c0669 9630a76b 030ee333 r = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0 s = 41e2345f 1f56df24 58f426d1 55b4ba2d b6dcd8c8 w = 9df4ece5 826be95f ed406d41 b43edc0b 1c18841b tu 1 = bf655bd0 46f0b35e c791b004 804afcbb 8ef7d69d u 2 = 821a9263 12e97ade abcc8d08 2b527897 8a2df4b0 g u1 mod p=51b1bf86 7888e5f3 af6fb476 9dd016bc fe667a65 aafc2753 9063bd3d 2b138b4c e02cc0c0 2ec62bb6 7306c63e 4db95bbf 6f96662a 1987a21b e4ec1071 010b6069 yu2 mod p= 8b510071 2957e950 50d6b8fd 376a668e 4b0d633c 1e46e665 5c611a72 e2b28483 be52c74d 4b30de61 a668966e dc307a67 c19441f4 22bf3c34 08aeba1f 0a4dbec7 v = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0