Texto del diccionario de contraseñas
1. Descripción general
El nombre completo de MD5 es algoritmo 5 de resumen de mensajes. Fue desarrollado a principios de la década de 1990 por Ronald L. Rivest del MIT Computer Science Laboratory y RSA Data Security Company, y fue desarrollado por md2 y desarrollo md3. y md4. Su función es "comprimir" información de gran capacidad en un formato seguro (es decir, convertir una cadena de bytes de cualquier longitud en un número entero grande de cierta longitud) antes de firmar la clave privada con un software de firma digital. Ya sea md2, md4 o md5, todos necesitan obtener una longitud aleatoria de información y generar un resumen de mensaje de 128 bits. Aunque la estructura de estos algoritmos es más o menos similar, el diseño de md2 es completamente diferente al de md4 y md5, porque md2 está optimizado para computadoras de 8 bits, mientras que md4 y md5 están diseñados para computadoras de 32 bits. Las descripciones y el código fuente en lenguaje C de estos tres algoritmos se detallan en Internet rfcs 1321 (http://www.ietf.org/RFC/RFC1321.txt), que se envió a ronald l rivest en agosto de 1992, la documentación más autorizada de ieft. .
Rivest desarrolló el algoritmo md2 en 1989. En este algoritmo, la información primero se complementa con datos de modo que la longitud en bytes de la información sea múltiplo de 16. Luego, la suma de verificación de 16 bits se agrega al final del mensaje. Y calcule un valor hash basado en esta información recién generada. Más tarde, rogier y chauvaud descubrieron que si se ignoraba la suma de comprobación, se producirían conflictos md2. El resultado del cifrado del algoritmo md2 es único: no hay duplicados.
Para mejorar la seguridad del algoritmo, rivest desarrolló el algoritmo md4 en 1990. El algoritmo md4 también necesita información de relleno para garantizar que la longitud del byte de la información pueda ser divisible por 512 después de sumar 448 (longitud del byte de información mod 512 = 448). Luego, agregue la longitud inicial del mensaje binario de 64 bits. ¿La información se procesa en damg de 512 bits? Bloques de estructura de iteración rd/merkle, cada bloque pasa por tres pasos diferentes. Den boer, bosselaers y otros descubrieron rápidamente vulnerabilidades que atacaban el primer y tercer paso de la versión md4. Dobbertin le muestra cómo encontrar un conflicto en la versión completa de md4 (este conflicto es en realidad una vulnerabilidad que dará como resultado el cifrado de contenido diferente pero posiblemente el mismo resultado de cifrado) en unos minutos usando una computadora personal común y corriente. No hay duda de que md4 ha sido eliminado.
Aunque existen lagunas tan grandes en la seguridad del algoritmo md4, jugó un papel rector importante en el surgimiento de varios algoritmos de cifrado de seguridad de la información que se desarrollaron posteriormente. Además de md5, también existen sha-1, rip-md, Haval, etc.
Un año después, en 1991, rivest desarrolló un algoritmo md5 técnicamente más maduro. Añade el concepto de "cinturón de seguridad" sobre la base de md4. Aunque md5 es ligeramente más lento que md4, es más seguro. El algoritmo aparentemente consta de cuatro pasos que son ligeramente diferentes del diseño md4. En el algoritmo md5, el tamaño del resumen de información y las condiciones necesarias para el relleno son exactamente los mismos que en md4. Den boer y bosselaers descubrieron una vez colisiones espurias en el algoritmo md5, pero no se descubrieron otros resultados criptográficos.
Van oorschot y Wiener habían considerado utilizar una función hash de fuerza bruta para buscar colisiones en hashes, y especularon sobre una máquina diseñada específicamente para buscar colisiones md5 (el coste de fabricar esta máquina fue de 1994, aproximadamente 1 dólar). millones) detecta una media de un conflicto cada 24 días. Sin embargo, en los 10 años transcurridos entre 1991 y 2001, no apareció ningún nuevo algoritmo llamado md6 que reemplazara a md5, por lo que podemos ver que esta falla no tuvo mucho impacto en la seguridad de md5. En la aplicación real de md5, nada de lo anterior es suficiente para ser un problema. Además, dado que no es necesario pagar ninguna tarifa de derechos de autor para utilizar el algoritmo md5, en circunstancias generales (no en áreas de aplicación ultrasecretas. Pero incluso en áreas ultrasecretas, md5 es una excelente tecnología intermedia), se debe considerar md5. muy seguro.
2. Aplicación del algoritmo
Una aplicación típica de md5 es generar un resumen de un mensaje para evitar que sea manipulado. Por ejemplo, en Unix, muchos programas tienen un nombre de archivo con el mismo nombre y extensión de archivo cuando se descargan. archivo md5. En este archivo normalmente hay una sola línea de texto y la estructura general es la siguiente:
MD5 (tanajiya.tar.gz) = 0ca 175 B9 c0f 726 a 831d 895 e 269332461
Esta es tanajiya Firma digital del documento .tar.gz. MD5 trata el archivo completo como un mensaje de texto grande y, a través de su algoritmo de conversión de cadenas irreversible, genera este resumen de mensaje MD5 único. Si en el proceso de distribución de este archivo en el futuro, no importa qué cambios ocurran en el contenido del archivo (incluidas modificaciones manuales o errores de transmisión causados por líneas inestables durante la descarga, etc.), simplemente vuelva a calcular el md5 de este archivo y podrá encontrará el resumen de información. Es diferente. Puede estar seguro de que acaba de obtener un archivo incorrecto. Si existe una autoridad de certificación de terceros, md5 también puede evitar el "repudio" del autor del documento, que es la llamada aplicación de firma digital.
Md5 también se utiliza ampliamente en tecnología de cifrado y descifrado. Por ejemplo, en sistemas Unix, la contraseña de un usuario se cifra mediante md5 (u otro método de cálculo similar) y se almacena en el sistema de archivos. Cuando un usuario inicia sesión, el sistema calcula la contraseña ingresada por el usuario como un valor md5 y luego la compara con el valor md5 guardado en el sistema de archivos para determinar si la contraseña ingresada es correcta. A través de tales pasos, el sistema puede determinar la legitimidad del inicio de sesión del usuario en el sistema sin conocer la contraseña clara del usuario. Esto no sólo evita que los usuarios con derechos de administrador del sistema conozcan la contraseña del usuario, sino que también aumenta en cierta medida la dificultad de descifrar la contraseña.
Es por esta razón que uno de los métodos más comunes utilizados por los piratas informáticos para descifrar contraseñas es un método llamado "manipulación del diccionario". Hay dos formas de obtener un diccionario, una es una colección diaria de tablas de cadenas utilizadas como contraseñas y la otra se genera mediante un método de permutación y combinación. Primero, los valores md5 de estos elementos del diccionario se calculan a través del programa md5 y luego se busca el valor md5 del objetivo en el diccionario. Suponemos que la longitud máxima de la contraseña es 8 bytes, la contraseña solo puede contener letras y números, ***26+26+10=62 caracteres y el número de entradas en el diccionario es p(62,1)+ p(62, 2)...+p(62). Esta tecnología de cifrado se utiliza ampliamente en los sistemas Unix, lo que también es una razón importante por la que los sistemas Unix son más robustos que los sistemas operativos generales.
3. Descripción del algoritmo
La descripción simple del algoritmo md5 es la siguiente: md5 procesa la información de entrada en paquetes de datos de 512 bits y cada paquete de datos se divide en 16 de 32 bits. paquetes de datos de bits. Después de una serie de procesos, la salida del algoritmo consta de cuatro paquetes de 32 bits y la concatenación de estos cuatro paquetes de 32 bits generará un valor hash de 128 bits.
En el algoritmo md5, primero se debe completar la información para que el resultado de 512 bytes sea igual a 448. Por lo tanto, la longitud de bits de la información se ampliará a n*512+448, es decir, n*64+56 bytes, donde n es un entero positivo. El método de llenado es el siguiente: llenar un 1 e innumerables ceros después de la información, y no dejar de llenar la información con ceros hasta que se cumplan las condiciones anteriores. Luego, después de este resultado, se agrega la longitud de la información de relleno previo expresada en binario de 64 bits. Después de estos dos pasos, la longitud de la palabra de información actual = n * 512+448+64 = (n+1) * 512, es decir, la longitud es exactamente un múltiplo entero de 512. La razón de esto es cumplir con los requisitos de longitud de la información en el posprocesamiento.
Hay cuatro parámetros enteros de 32 bits en md5 llamados variables de enlace, son: a=0x01234567, b=0x89abcdef, c=0xxfedcba98, d=0x76543210.
Cuando se establecen estas cuatro variables de enlace, el algoritmo comienza a ingresar en una operación de bucle de cuatro rondas. El número de ciclos es el número de paquetes de 512 bits en el mensaje.
Copie las cuatro variables de enlace anteriores a las otras cuatro variables: A a A, B a B, C a C y D a D.
Hay cuatro ciclos principales (md4 solo tiene tres), y cada ciclo es muy similar. 16 operaciones en la primera vuelta.
Realiza una función no lineal en tres de A, B, C y D, luego agrega una cuarta variable, un subgrupo de texto y una constante al resultado. Luego desplaza el resultado hacia la derecha una cantidad indeterminada y suma uno de A, B, C o D. Finalmente, reemplace uno de A, B, C o D con el resultado.
Veamos las cuatro funciones no lineales utilizadas en cada operación (una para cada turno).
f(x,y,z)=(x&y)|((x)&z)
g(x,y,z)=( x & ampz)|(y & amp (~z)
h(x,y,z)=x^y^z
i(x,y,z) =y^(x|( ~z)
(& amp sí y | sí o ~ sí o no, XOR)
Explicación de estas cuatro funciones: Si X, Los bits correspondientes de Y y Z son independientes y unificado, entonces cada bit del resultado también debe ser independiente y unificado.
f es una función de operaciones de bits. Es decir, si x, entonces y, de lo contrario, la función h es el operador de paridad bit a bit.
Supongamos que mj representa el subgrupo j del mensaje (de 0 a 15),
& lt& ltff(a, b, c, d, mj, s, ti) significa a = b+((a+(f(b,c,d)+mj+ti)).
& lt& ltgg(a, b, c, d ,mj,s,ti) significa a = b+ ((a+(g(b,c,d)+mj+ti).
& lt& lthh(a,b,c,d,mj, s,ti) significa a = b+((a+ (h(b,c,d)+mj+ti)).
& lt& ltii (a, b, c, d, mj, s, ti) significa a = b + ((a + (I (b, c, d) + mj + ti)) < /p >
& lt& ltEstas cuatro rondas (64 pasos) son:
La primera ronda
ff (a, b, c, d, m0, 7, m0, 7 ,0xd76aa478)
ff(d,a,b,c,m1,12,0xe8c7b756)
ff(c,d,a,b,m2,17,0x242070db)
ff(b,c,d,a,m3,22,0xc1bdceee)
ff(a,b,c,d,m4,7,0xf57c0faf)
ff(d,a,b,c,m5,12,0x4787c62a)
ff(c,d,a,b,m6,17,0xa8304613)
ff ( b, c, d, a, m7, 22, 0xfd469501)
ff (a, b, c, d, m8, 7, 0x698098d8)
ff (d, a , b, c, m9, 12, 0x8b44f7af)
ff (c, d, a, b, m10, 17, 0xffff5bb1)
ff (b, c, d, a , m11, 22, 0x895cd7be)
ff (a, b, c, d, m12, 7, 0x6b901122)
ff (d, a, b, c, m13, 12 , 0xfd987193)
ff(c,d,a,b,m14,17,0xa679438e)
ff(b,c,d,a,m15,22,0x49b40821)
p>Segunda ronda
gg (a, b, c, d, m1, 5, 0xf61e2562)
gg (d, a, b, c, m6, 9, 0xc040b340)
gg(c,d,a,b,m11,14,0x265e5a51)
gg(b,c,d,a,m0,20, 0xe9b6c7aa)
gg(a,b,c,d,m5,5,5,0xd62f105d)
gg(d,a,b,c,m10,9,0x02441453)
gg(c,d,a,b,m15,14,0xd8a1e681)
gg(b,c,d,a,m4,20,0xe7d3fbc8)
gg (a, b, c, d, m9, 5, 0x21e1cde6)
gg (d, a, b, c, m14, 9, 0xc33707d6)
gg (c , d , a, b, m3, 14, 0xf4d50d87)
gg (b, c, d, a, m8, 20, 0x455a14ed)
gg (a, b, c , d , m13, 5, 0xa9e3e905)
gg (d, a, b, c, m2, 9, 0xfcefa3f8)
gg (c, d, a, b, m7 , 14 , 0x676f02d9)
gg (b, c, d, a, m12, 20, 0x8d2a4c8a)
Tercera ronda
hh (a, b, c , d, m5, 4, 0xfffa3942)
hh (d, a, b, c, m8, 11, 0x8771f681)
hh (c, d, a, b, m 116, 0x6d9d6122)
hh(b,c,d,a,m14,23,0xfde5380c)
hh(a,b,c,d,m1,4,0xa4beea44 )
hh(d,a,b,c,m4,11,0x4bdecfa9)
hh(c,d,a,b,m7,16,0xf6bb4b60)
hh(b,c
, d, a, m10, 23, 0x befbc 70)
hh (a, b, c, d, m13, 4, 0x 289 b7c 6)
hh (d, a, b, c, m0, 11, 0xeaa127fa)
hh (c, d, a, b, m3, 16, 0xd4ef3085)
hh (b, c, d, a, m6, 23, 0x04881d05)
hh (a, b, c, d, m9, 4, 0xd9d4d039)
hh (d, a, b, c, m12, 11, 0xe6db99e5)
hh (c, d, a, b, m15, 16, 0x1fa27cf8)
hh (b, c, d, a, m2, 23, 0xc4ac5665)
La cuarta ronda
ii (a, b, c, d, m0, 6, 0xf4292244)
Dos (d, a, b, c, m7, 10, 0x 432 af 97)
Dos (c, d, a, b, m14, 15, 0xab9423a7)
Dos (b, c, d, a, m5 , 21, 0xfc93a039)
Dos (a, b, c, d, m12, 6, 0x655b59c3)
Dos (d, a, b, c, m3, 10, 0x8f0ccc92 )
II (c, d, a, b, m10, 15, 0xffeff47d)
ii (b, c, d, a, m1, 21, 0x85845dd1)
Dos (a, b, c, d, m8, 6, 0x6fa87e4f)
Dos (d, a, b, c, m15, 10, 0xfe2ce6e0)
Dos (c, d, a, b, m6, 15, 0xa3014314)
Dos (b, c, d, a, m13, 21, 0x4e0811a1)
Dos (a, b, c, d, m4, 6, 0xf7537e82)
II (d, a, b, c, m11, 10, 0xbd3af235)
ii (c, d, a, b, m2, 15, 0x2ad7d2bb)
ii (b, c, d, a, m9, 21, 0xeb86d391)
La constante ti se puede seleccionar de la siguiente manera:
En el paso I, ti es la parte entera de 4294967296*ABS(sin(I)), y la unidad de I es radianes. (4294967296 es igual a 2 elevado a la 32ª potencia)
Después de hacer todo esto, suma A, B, C y D respectivamente. Luego continúe ejecutando el algoritmo en el siguiente paquete y el resultado final es la concatenación de A, B, C y D.
Cuando implemente el algoritmo md5 de acuerdo con el método que mencioné anteriormente, puede usar La siguiente información proporciona una prueba sencilla de su programa para ver si contiene algún error.
MD5("") = d 41 D8 CD 98 f 00 b 204 e 9800998 ECF 8427 e
MD5("a") = 0cc 175 B9 c0f 1b6a 831c 399 e 269772661
MD5("ABC") = 900150983 CD 24 fb0d 6963 f 7d 28e 17f 72
md5("Resumen de mensajes") = f96b 697 D7 CB 7938d 525 a2f 31 AAF 161 d0
MD5("abcdefghijklmnopqrstuvwxyz") = C3 fcd 3d 76192 e 4007 DFB 496 CCA 67 e 13b
MD5("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz 0123456789" ) = d 174 ab 277 d9f9 F5 a 5611c2c 9f 419d9f
MD5("1234567890123456789012345678901234567890123456789012345678901234578901234565438
Si utiliza la información anterior para probar el algoritmo md5 que creó como ejemplo, y el conclusión es completamente consistente con la respuesta estándar, entonces Quiero felicitarte. Sabes, mi programa no obtuvo el mismo resultado que el anterior cuando se compiló con éxito por primera vez.
Cuarto, la seguridad de MD5.
Mejoras de md5 a md4:
1. Se agregó una cuarta ronda;
2. Cada paso tiene una constante de bonificación única;
3. En la segunda ronda, la simetría de la función G se debilita y la función G cambia de (x &; y) (x & z) (y & z) a (x &; z) | (y & amp; (~ z);
4. El primer paso agrega los resultados del paso anterior, lo que conducirá a un efecto de avalancha más rápido;
5. Cambió el segunda ronda y el orden de acceso a los subpaquetes de mensajes en la tercera ronda, haciéndolos más diferentes;
6 El desplazamiento del desplazamiento a la izquierda en cada ronda se optimiza aproximadamente para lograr un efecto de avalancha más rápido. No es lo mismo.