Padding in MD5 Hash Algorithm

Question

I need to understand the Md5 hash algorithm. I was reading a documents and it states

"The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512."

I need to understand what this means in simple terms, especially the 448 modulo 512. The word MODULO is the issue. Please I will appreciate simple examples to this. Funny though, this is the first step to MD5 hash! :)

Thanks

Solution 1

Modulo or mod, is a function that results in telling you the remainder when two numbers are divided by each other.

For example:

5 modulo 3:

5/3 = 1, with 2 remainder. So 5 mod 3 is 2.

10 modulo 16 = 10, because 16 cannot be made.

15 modulo 5 = 0, because 15 goes into 5 exactly 3 times. 15 is a multiple of 5.

Back in school you would have learnt this as "Remainder" or "Left Over", modulo is just a fancy way to say that.

What this is saying here, is that when you use MD5, one of the first things that happens is that you pad your message so it's long enough. In MD5's case, your message must be n bits, where n= (512*z)+448 and z is any number.

As an example, if you had a file that was 1472 bits long, then you would be able to use it as an MD5 hash, because 1472 modulo 512 = 448. If the file was 1400 bits long, then you would need to pad in an extra 72 bits before you could run the rest of the MD5 algorithm.

Solution 2

Modulus is the remainder of division. In example

512 mod 448 = 64
448 mod 512 = 448

Another approach of 512 mod 448 would be to divide them 512/448 = 1.142..

Then you subtract 512 from result number before dot multiplied by 448:

512 - 448*1 == 64 That's your modulus result.

What you need to know that 448 is 64 bits shorter than multiple 512.

But what if it's between 448 and 512??

Normally we need to substract 448 by x(result of modulus).

 447 mod 512 = 447; 448 - 447 = 1; (all good, 1 zero to pad)

 449 mod 512 = 1; 448 - 449 = -1 ???

So this problem solution would be to take higher multiple of 512 but still shorter of 64;

512*2 - 64 = 960
449 mod 512 = 1; 960 - 449 = 511;

This happens because afterwards we need to add 64 bits original message and the full length have to be multiple of 512.

960 - 449 = 511; 
511 + 449 + 64 = 1024; 
1024 is multiple of 512;