So I started implementing the MD5GPU algorithm. It’s pretty straightforward. Matter of fact, I will be brief. (Note, I have not tested the code below)
From the original MD5 algo., we need to break the input into 512 bit chunks. So, we need to first pad the input to a length a, and then add 64 bit to it in order to be able to break our input into 512 bit chunks, such that:
a congurent to 448 mod 512. So we keep on appending 0 to our digest (after we appended a 1 first) so that (a – 448) mod 512 = 0. Since, (note ~ is the equivalence relation)
a ~ b mod n => (a-b) = cn, => (a-b)/n = c, where c is in Z (integers), iff (a-b) mod n = 0. (Maybe in a future post I will talk about how this relates to group theory.)
But for our problem, since the message length is a constant 128 bit, then we know from the get-go that a is 448.
…
Okay, that’s not all that interesting, since I’m just describing the algorithm. I may post some more on this tomorrow. I’m heading out for the night.
The interesting part is WHY does this thing work? Why does it produce results that passes all the DIEHARD tests? My intitutive understanding of this (but I’m not sure. Never studied crypto) this is due to the combinatoric explosion nature of working with 512 bit chunks. The compression functions are such that a change in ONE single input bit results in change of each output bit with a probability of 1/2. So, it’s like we are ’scrambling’ the input in this 512 bit combinatoric ’space’, which is a huge space… (I’m really sorry if the above bit totally pisses you off due to all the hand waving due to ignorant understanding)
Not sure tho. That’s just my intuition…
What do you think?
