[Tarea 1] Dudas implementación MD5

[VicenteMerino]

Hola, me surgieron un par de dudas con respecto a la implementación de MD5 y el pseudo-código existente en wikipedia.

1) Aparecen ciertas tablas K y s que no se entra en mucho detalle de lo que hacen, viendo las notas de una clases de otra universidad, habla que son 'constantes mágicas' que supongo que tienen que ver con la implementación del algoritmo más que nada y no es necesario entrar en mucho detalle con ellas. Es válido usar la misma definición de estas tablas que son utilizadas en el pseudo-código de wikipedia?

2) En el pseudo-código de wikipedia al definir la función leftrotate aparece una operación binary or. En que se diferencia esto a los otros or presentes por ejemplo al hacer el cálculo de F := (B and C) or ((not B) and D)?. Me surge esta duda, ya que según yo todos los cálculos se está haciendo a nivel de operación binario, quizás solo se fue redundante en esta definición?.

[mugartec]

Hola @VicenteMerino, abajo las respuestas.

1. Aparecen ciertas tablas K y s que no se entra en mucho detalle de lo que hacen, viendo las notas de una clases de otra universidad, habla que son 'constantes mágicas' que supongo que tienen que ver con la implementación del algoritmo más que nada y no es necesario entrar en mucho detalle con ellas. Es válido usar la misma definición de estas tablas que son utilizadas en el pseudo-código de wikipedia?

K y s son constantes que se usan como parte del algoritmo mismo, en particular s indica cuánto rotar ciertas variables y K es una matriz de números que debiesen ser aleatorios (pero como vimos en clases, para no ser sospechosos se usan nothing up my sleeve numbers). No es necesario entrar en detalle, pero sí es importante entender que son simples parámetros del scramble que se hace para que la función no sea reversible.

2. En el pseudo-código de wikipedia al definir la función leftrotate aparece una operación binary or. En que se diferencia esto a los otros or presentes por ejemplo al hacer el cálculo de F := (B and C) or ((not B) and D)?. Me surge esta duda, ya que según yo todos los cálculos se está haciendo a nivel de operación binario, quizás solo se fue redundante en esta definición?.

La función leftrotate lo que hace es rotar los bits de un número hacia la izquierda de forma cíclica. Entendiendo eso podemos deducir que binary or es lo mismo que un or, probablemente sacaron el código de otra parte y lo dejaron así. Algo para pensar es que en la función leftrotate se podría cambiar ese or por un xor. ¿A alguien se le ocurre por qué?

Saludos!

[VicenteMerino]

Gracias por la respuesta profe!! Repecto a lo del xor me imagino que en el x << c al hacer shift left c posiciones, desde la posición 32 - c (asumiendo x es de 32 bits). hasta el bit 32 hay solamente 0s. Algo similar pasaría con x >> (32 - c) donde el bit 0 al 32 - c habrían solamente 0's. Luego independiente de si hago xor o el or solo se mantendría el valor del mensaje que no haya quedado solo con 0s en ese segmento.

Este mismo punto me lleva a la siguiente pregunta: como mantenemos lo que entra al leftrotate en el rango de 32 bits? En mi código al imprimir el paso a paso me pasa que lo que se va guardando en la variable F (y por ende en B e iteraciones después en todas las otras variables) crece indefinidamente

Esto no hace ningún sentido, ya que claramente al terminar el numero hasheado será mucho mayor a 128 bits que es lo que se espera. No se si al calcular los F debo hacerlo con algún módulo (2³² por ejemplo) para mantener que todo lo que entre al leftrotate sea de 32 bits. Creo que este detalle no aparece en el el código de Wikipedia (o quizás esté pasando algo por alto)

[mugartec]

Hola @VicenteMerino,

Luego independiente de si hago xor o el or solo se mantendría el valor del mensaje que no haya quedado solo con 0s en ese segmento

Efectivamente, como para cada posición sabemos de antemano que al menos uno de los valores será cero, el or es lo mismo que el xor.

Respecto de tu segunda pregunta,

como mantenemos lo que entra al leftrotate en el rango de 32 bits?

lo que ocurre aquí es que el leftrotate que se muestra en Wikipedia está suponiendo números de exactamente 32 bits (que pueden comenzar con ceros), y que los bits de la izquierda que pasan más allá de la posición 32 no son considerados. Esto en Python no es lo mismo, debido a que Python trabaja con números arbitrariamente grandes. La operación leftrotate se define para una cantidad máxima de bits. Por ejemplo si tengo el número 11000110 y le aplico leftrotate(2) con una cantidad máxima de 8 bits, obtengo 00011011, es decir 11011. Sin embargo, si aplico leftrotate(2) con una cantidad máxima de 9 bits, obtengo 100011001. La razón es que el número original 11000110 escrito en 9 bits es 011000110, y al rotar esto dos bits a la izquierda se obtiene 100011001. En MD5 todas las rotaciones se aplican sobre una cantidad máxima de 32 bits.

Independiente de la explicación anterior, al trabajar con números de 32 bits todas las operaciones tales como sumas o shifts deben hacerse módulo 32.

Me cuentas por favor si hay más dudas. Saludos!