I understand the process of MD5 padding and the purpose, but I don't understand why we have to append 1 first (next bit to last bit of message) and then zeros as many to get 512 (including the msg length).
Can you explain the purpose of appending 1 (one) at the end of the message bit and zeros after that (1/0*)? Can we have any other combinations for padding? Say, first append zeros and then one (0|1*)?
The reason is that a hash function needs to return a different output for different inputs. With a 128-bit hash, it's obvious that there must exist two 17-byte sequences that return the same 16-byte hash (for example), but you don't want it to be easy to figure out what they might be in advance.
This is the reason why things get padded out, and the first bit is a 1 bit. This way, if someone hashes a 0, and then two zeros, then three, they end up with different end hashes.
The simplest way to manage that is to always append a 1 bit. What you use to round out to an even 512 bits doesn't matter. Anything would do. Zeroes happen to be easy to generate.
For more information on this topic, visit these other SearchSecurity.com resources:
Ask the Expert: MD5 versus RC4 with 128-bit encryption
Best Web Links: Encryption