MD5算法实现咨询：步骤1代码正确性验证及步骤2-3实现疑问

Hey there! Let's walk through your MD5 implementation questions step by step—this is a solid project to dive into cryptographic algorithms, nice work!

Your current Step 1 code has a critical issue: it only appends the '1' bit if the binary string length is less than 448. But MD5's padding rule requires always appending a single '1' bit first, regardless of the original length, then padding with '0's until the total length modulo 512 equals 448. If your input is already 448 bits or longer, you still need that leading '1' before padding to the next 512-bit boundary minus 64 bits (which is 448 bits).

Here's the corrected Step 1 code in C#:

// Step 1: Properly pad the input per MD5 rules
var textBytes = Encoding.UTF8.GetBytes(text);
var binaryBuilder = new StringBuilder();

// Convert each byte to an 8-bit binary string (pad with leading zeros to ensure 8 bits)
foreach (byte b in textBytes)
{
    binaryBuilder.Append(Convert.ToString(b, 2).PadLeft(8, '0'));
}

// Mandatory: Append a single '1' bit
binaryBuilder.Append('1');

// Pad with '0's until total length mod 512 equals 448
while (binaryBuilder.Length % 512 != 448)
{
    binaryBuilder.Append('0');
}

string paddedBinary = binaryBuilder.ToString();

Next, we need to append the original input's length (in bits) as a 64-bit little-endian value. This lets MD5 reconstruct the original input length even after padding. Key notes:

• Calculate length in bits (multiply byte count by 8)
• MD5 uses little-endian for this value (write least significant bytes first)

Here's how to implement it:

// Step 2: Append original bit length as 64-bit little-endian
long originalBitLength = textBytes.Length * 8L;
string lengthBinary = string.Empty;

// Extract each byte from the bit length, starting with the least significant
for (int i = 0; i < 8; i++)
{
    byte lengthByte = (byte)(originalBitLength >> (i * 8));
    lengthBinary += Convert.ToString(lengthByte, 2).PadLeft(8, '0');
}

// Append to our padded binary string
paddedBinary += lengthBinary;

The final step involves initializing MD5's hash registers, splitting the padded input into 512-bit blocks, and running 4 rounds of cryptographic transformations on each block. Here's a complete implementation framework:

// Step 3: Initialize MD5's 32-bit registers (little-endian values)
uint A = 0x67452301;
uint B = 0xEFCDAB89;
uint C = 0x98BADCFE;
uint D = 0x10325476;

// Predefined MD5 round constants
uint[] K = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
    0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
    0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
    0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
    0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
    0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
    0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
    0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
    0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
};

// Shift amounts for each round of operations
int[] shifts = {
    7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
    5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
    4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
    6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
};

// Process each 512-bit block
for (int blockIndex = 0; blockIndex < paddedBinary.Length; blockIndex += 512)
{
    string block = paddedBinary.Substring(blockIndex, 512);
    uint[] blockWords = new uint[16];

    // Split block into 16 32-bit little-endian words
    for (int i = 0; i < 16; i++)
    {
        string wordBinary = block.Substring(i * 32, 32);
        uint word = 0;
        // Convert 32-bit binary to uint (little-endian: reverse byte order)
        for (byte j = 0; j < 4; j++)
        {
            byte byteValue = Convert.ToByte(wordBinary.Substring(j * 8, 8), 2);
            word |= (uint)byteValue << (j * 8);
        }
        blockWords[i] = word;
    }

    // Save current register state
    uint a = A;
    uint b = B;
    uint c = C;
    uint d = D;

    // Run 4 rounds of 16 operations each
    for (int i = 0; i < 64; i++)
    {
        uint f, g;
        // Select round-specific function and word index
        if (i < 16)
        {
            f = (b & c) | ((~b) & d);
            g = (uint)i;
        }
        else if (i < 32)
        {
            f = (d & b) | ((~d) & c);
            g = (uint)((5 * i + 1) % 16);
        }
        else if (i < 48)
        {
            f = b ^ c ^ d;
            g = (uint)((3 * i + 5) % 16);
        }
        else
        {
            f = c ^ (b | (~d));
            g = (uint)((7 * i) % 16);
        }

        // Perform rotation and register updates
        uint temp = d;
        d = c;
        c = b;
        b = b + RotateLeft(a + f + K[i] + blockWords[g], shifts[i]);
        a = temp;
    }

    // Add block results to main registers
    A += a;
    B += b;
    C += c;
    D += d;
}

// Convert registers to little-endian hex string (final hash)
string md5Hash = string.Format("{0:x8}{1:x8}{2:x8}{3:x8}",
    ReverseBytes(A), ReverseBytes(B), ReverseBytes(C), ReverseBytes(D));
Console.WriteLine(md5Hash);

// Helper: Rotate 32-bit value left by specified shift
static uint RotateLeft(uint value, int shift)
{
    return (value << shift) | (value >> (32 - shift));
}

// Helper: Reverse byte order for little-endian to big-endian hex output
static uint ReverseBytes(uint value)
{
    return ((value & 0x000000FF) << 24) |
           ((value & 0x0000FF00) << 8) |
           ((value & 0x00FF0000) >> 8) |
           ((value & 0xFF000000) >> 24);
}

A quick breakdown of Step 3:

• We start with fixed initial register values defined by the MD5 spec
• Each 512-bit block is split into 16 32-bit words (converted to little-endian)
• Four rounds of transformations run, each using a different logical function, constant, and shift amount
• After processing all blocks, we reverse the byte order of each register (to match standard big-endian hex output) and combine them into the final MD5 hash string

内容的提问来源于stack exchange，提问作者Zeyad