Programa de algoritmo md5 + comentarios detallados, puntuaciones altas, ¡pide consejo!

Introducción al algoritmo de cifrado MD5

1. Descripción general

El nombre completo de MD5 es algoritmo de resumen de mensajes 5 (algoritmo de resumen de mensajes), que fue desarrollado. por el MIT a principios de la década de 1990. Desarrollado por ronald l. rivest del laboratorio de informática y rsa data security inc., se desarrolló a partir de md2, md3 y md4. Su función es permitir que la información de gran capacidad se "comprima" en un formato confidencial (es decir, convertir una cadena de bytes de cualquier longitud en un 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 información de 128 bits. Aunque las estructuras de estos algoritmos son más o menos similares, el diseño de md2 es completamente diferente al de md4 y md5. Esto se debe a que md2 está diseñado y optimizado para máquinas de 8 bits, mientras que md4 y md5 están diseñados para computadoras de 32 bits. La descripción de estos tres algoritmos y el código fuente del lenguaje C se describen en detalle en Internet rfcs 1321 (http://www.ietf.org/rfc/rfc1321.txt. Este es el documento más autorizado, escrito por ronald l). Rivest fue presentado al IEFT en agosto de 1992.

Rivest desarrolló el algoritmo md2 en 1989. En este algoritmo, la información primero se rellena con datos de modo que la longitud en bytes de la información sea múltiplo de 16. Luego, se agrega una suma de verificación de 16 bits al final del mensaje. Y calcule el valor hash en función de esta información recién generada. Más tarde, rogier y chauvaud descubrieron que se producirían conflictos md2 si se omitía la suma de comprobación. El resultado cifrado del algoritmo md2 es único: no hay duplicación.

Para mejorar la seguridad del algoritmo, rivest desarrolló el algoritmo md4 en 1990. El algoritmo md4 también necesita rellenar la información para garantizar que la longitud del byte de la información más 448 sea divisible por 512 (longitud del byte de información mod 512 = 448). Luego, se agrega una representación binaria de 64 bits de la longitud original del mensaje. La información se procesa en bloques de iteraciones damgörd/merkle de 512 bits, y cada bloque se procesa en tres pasos diferentes. Den Boer, Bosselaers y otros descubrieron rápidamente vulnerabilidades que atacaron el primer y tercer paso de la versión md4. Dobbertin demuestra cómo usar una PC común para encontrar un conflicto en la versión completa de md4 en unos minutos (este conflicto es en realidad una vulnerabilidad que conducirá a un cifrado de contenido diferente pero al mismo resultado de cifrado). No hay duda de que md4 ha sido eliminado.

Aunque el algoritmo md4 tiene una laguna de seguridad tan grande, tiene un papel rector que no se puede ignorar en la aparición de varios algoritmos de cifrado de seguridad de la información que se desarrollaron posteriormente. Además de md5, los más famosos incluyen sha-1, rip-md y haval.

Un año después, en 1991, rivest desarrolló el algoritmo md5, que era técnicamente más maduro. Añade el concepto de "cinturones de seguridad" a md4. Aunque md5 es ligeramente más lento que md4, es más seguro. Este algoritmo obviamente consta de cuatro pasos que son ligeramente diferentes del diseño md4. En el algoritmo md5, las condiciones necesarias para el tamaño y el relleno del resumen del mensaje son exactamente las mismas que para md4. Den Boer y Bosselaers descubrieron pseudocolisiones en el algoritmo md5, pero aparte de eso, no se descubrieron otros resultados de cifrado.

van Oorschot y Wiener habían considerado una función hash de fuerza bruta que buscaba colisiones en el hash, y plantearon la hipótesis de que una máquina diseñada específicamente para buscar colisiones md5 (esta máquina (El costo de fabricación en 1994 era aproximadamente $1 millón) y se encontró un promedio de un conflicto cada 24 días. Pero en los 10 años transcurridos entre 1991 y 2001, no hubo ningún md6 que reemplazara al algoritmo md5 o un nuevo algoritmo llamado con otro nombre. Podemos ver que esta falla no afectó demasiado la seguridad de md5. Todo lo anterior no es suficiente para ser un problema para md5 en aplicaciones prácticas. Además, dado que el uso del algoritmo md5 no requiere el pago de derechos de autor, en circunstancias normales (no en campos de aplicación ultrasecretos). Pero incluso si se aplica en campos ultrasecretos, md5 puede considerarse como un algoritmo muy excelente tecnología intermedia), ¿cómo puede md5? Debe considerarse muy seguro.

2. Aplicación del algoritmo

Una aplicación típica de md5 es generar un resumen de mensaje (message-digest) para una información (mensaje) para evitar que sea manipulado. . Por ejemplo, al descargar muchos programas en Unix, todos tienen un archivo con el mismo nombre y una extensión de archivo .md5. Por lo general, solo hay una línea de texto en este archivo y la estructura general es la siguiente:

md5 ( tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461

Esta es la firma digital del archivo tanajiya.tar.gz. md5 trata el archivo completo como un mensaje de texto grande y genera este resumen de mensaje md5 único a través de su algoritmo de transformación de cadenas irreversible. Si en el proceso de distribución de este archivo en el futuro, no importa si el contenido del archivo cambia de alguna manera (incluidas modificaciones humanas o errores de transmisión causados ​​por líneas inestables durante el proceso de descarga, etc.), lo descubrirá como Siempre que vuelva a calcular el md5 de este archivo, el resumen de información es diferente, por lo que puede estar seguro de que obtuvo un archivo incorrecto. Si hay una agencia de certificación de terceros, el uso de md5 también puede evitar el "repudio" del autor del archivo. Esta es la llamada aplicación de firma digital.

MD5 también se utiliza ampliamente en tecnología de cifrado y descifrado. Por ejemplo, en un sistema Unix, la contraseña del usuario se cifra mediante md5 (u otros algoritmos similares) y se almacena en el sistema de archivos. Cuando el usuario inicia sesión, el sistema calcula la contraseña ingresada por el usuario en un valor md5 y luego la compara con el valor md5 almacenado 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 el código claro de la contraseña 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 este motivo que el método más utilizado por los hackers para descifrar contraseñas es un método llamado "ejecución de 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, use el programa md5 para calcular los valores md5 de estos elementos del diccionario. y luego use los valores md5 del objetivo que se recuperan en este diccionario. Suponemos que la longitud máxima de la contraseña es de 8 bytes, y la contraseña solo puede contener letras y números, ***26+26+10=62 caracteres, y el número de elementos en el diccionario formado por permutación es p(62 ,1)+p(62,2)….+p (62,8), que ya es un número astronómico. Almacenar este diccionario requiere una matriz de discos a nivel de terabytes, y este método también tiene una La premisa es que el md5. Se puede obtener el valor de la contraseña de la cuenta de destino. Esta tecnología de cifrado se usa ampliamente en los sistemas Unix, lo cual es una razón importante por la cual los sistemas Unix son más robustos que los sistemas operativos generales.

3. Descripción del algoritmo

Una breve descripción del algoritmo md5 puede ser la siguiente: md5 procesa la información de entrada en grupos de 512 bits y cada grupo se divide en 16 de 32 bits. Agrupación, después de una serie de procesamiento, la salida del algoritmo consta de cuatro grupos de 32 bits. Después de concatenar estos cuatro grupos de 32 bits, se generará un valor hash de 128 bits.

En el algoritmo md5, primero se debe completar la información para que la longitud del byte sea igual a 448 después del módulo de 512. Por lo tanto, la longitud de bytes de la información (longitud de bits) se ampliará a n*512+448, es decir, n*64+56 bytes, n es un entero positivo. El método de llenado es el siguiente: complete un 1 e innumerables ceros detrás de la información y deje de completar la información con ceros hasta que se cumplan las condiciones anteriores. Luego, a este resultado se le añade una representación binaria de 64 bits de la longitud de la información previa al relleno. Después de estos dos pasos de procesamiento, la longitud del byte 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 procesamiento posterior.

Hay cuatro parámetros enteros de 32 bits llamados variables de encadenamiento en md5. Son: a=0x01234567, b=0x89abcdef, c=0xfedcba98, d=0x76543210.

Después de configurar estas cuatro variables de enlace, comienza la operación de bucle de cuatro rondas del algoritmo. El número de ciclos es el número de paquetes de información 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, d a d.

El bucle principal tiene cuatro rondas (md4 solo tiene tres rondas) y cada bucle es muy similar. Hay 16 operaciones en la primera ronda. Cada operación realiza una operación de función no lineal en tres de a, b, cyd, y luego suma el resultado a una cuarta variable, un subgrupo del texto y una constante. Luego mueve el resultado hacia la derecha un número indefinido y suma uno de a, b, c o d. Finalmente reemplace uno de a, b, c o d con este resultado.

Las siguientes son las cuatro funciones no lineales utilizadas en cada operación (una para cada ronda).

f(x,y,z) =(x&y)|((~x)&z)

g(x,y,z) =(x&z)|(y&( ~z))

h(x,y,z) =x^y^z

i(x,y,z)=y^(x|(~z) )

(& es AND, | es OR, ~ no es, ^ es XOR)

Descripción de estas cuatro funciones: Si los bits correspondientes de x, y y z son independientes y uniforme, entonces cada bit del resultado también debe ser independiente y uniforme.

f es una función que opera poco a poco. Es decir, si x, entonces y, en caso contrario z. La función h es un operador de paridad bit a bit.

Supongamos que mj representa el j-ésimo subgrupo del mensaje (de 0 a 15),

<< ff(a,b,c,d,mj,s,ti) representa a =b+((a+(f(b,c,d)+mj+ti)

<< gg(a,b,c,d,mj,s,ti) significa a=b+ (( a+(g(b,c,d)+mj+ti)

<< hh(a,b,c,d,mj,s,ti) significa a=b+((a+( h( b,c,d)+mj+ti)

<< ii(a,b,c,d,mj,s,ti) significa a=b+((a+(i(b, c, d)+mj+ti)

<< Estas cuatro rondas (64 pasos) son:

Primera ronda

ff(a,b,c , d,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)

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,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,m11,16,0x6d9d6122)

hh(b,c,d,a,m14,23,0xfde5380c)

p>

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,0xbebfbc70)

hh(a ,b,c,d,m13,4,0x289b7ec6)

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)

Cuarta ronda

ii(a,b, c,d ,m0,6,0xf4292244)

ii(d,a,b,c,m7,10,0x432aff97)

ii(c,d,a,b, m14,15 ,0xab9423a7)

ii(b,c,d,a,m5,21,0xfc93a039)

ii(a,b,c,d,m12,6, 0x655b59c3)

ii(d,a,b,c,m3,10,0x8f0ccc92)

ii(c,d,a,b,m10,15,0xffeff47d)

ii(b,c,d,a,m1,21,0x85845dd1)

ii(a,b,c,d,m8,6,0x6fa87e4f)

ii( d,a,b,c,m15,10,0xfe2ce6e0)

ii(c,d,a,b,m6,15,0xa3014314)

ii(b ,c, d,a,m13,21,0x4e0811a1)

ii(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 la unidad de i es radianes. (4294967296 es igual a 2 elevado a la potencia 32)

Después de completar todo esto, suma a, b, c, d a a, b, c, d respectivamente. Luego continúe ejecutando el algoritmo con el siguiente grupo de datos y el resultado final es la cascada de a, b, cy d.

Después de implementar el algoritmo md5 de acuerdo con el método que mencioné anteriormente, puede usar la siguiente información para realizar una prueba simple en el programa que creó para ver si hay algún error en el programa.

md5 ("") = d41d8cd98f00b204e9800998ecf8427e

md5 ("a") = 0cc175b9c0f1b6a831c399e269772661

md5 ("abc") = 900150983c f7d28e17f72

md5 ("resumen del mensaje") = f96b697d7cb7938d525a2f31aaf161d0

md5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b

md5 ("abcdefgh ijklmnopqrstuvwxyzab cdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f

md5 (" 1234567890123456789012345678901234567890123456789012345678901234567890 ") = 57edf4a22be3c955ac49da2e2107b67a

La información anterior se utiliza para probar el ejemplo del algoritmo md5. La conclusión final es exactamente la misma que la respuesta estándar, así que te diré algo aquí. . Sabes, la primera vez que mi programa se compiló con éxito, no produjo el mismo resultado que el anterior.

4. Seguridad de MD5

Mejoras realizadas por md5 sobre md4:

1. Se agregó la cuarta ronda

2 . el paso tiene una constante de suma única

3. Para debilitar la simetría de la función g en la segunda ronda, cambia de (x&y)|(x&z)|(y&z) a (x&z)|( y& (~z));

4. El primer paso agrega el resultado del paso anterior, lo que provocará un efecto de avalancha más rápido

5. Cambia la segunda ronda y The; el orden de acceso a los subgrupos de mensajes en la tercera ronda lo hace más diferente

6. Optimice aproximadamente el desplazamiento cíclico hacia la izquierda en cada ronda para lograr un efecto de avalancha más rápido. El desplazamiento de cada rueda es diferente entre sí.