题目描述

给定一个字符串，计算其MD5哈希值，并以十六进制小写字符串形式输出。

输入格式

第一行，一个正整数 $T (1 \leq T \leq 100)$ ，表示有 $T$ 组测试用例

对于每组测试用例，一行一个字符串$S（1 ≤ |S| ≤ 1000）$，仅包含大小写字母和数字或空格。

输出格式

对于每组测试用例，输出一行，包含字符串 $S$ 的 MD5 哈希值

2
abc
hello world

900150983cd24fb0d6963f7d28e17f72
5eb63bbbe01eeed093cb22bb8f5acdc3

8
Rust is faster than CPlusPlus
Rust is more save than CPlusPlus
Rust can use ffi build cdylib or static libs with its stable C ABI
Rust was used to build faster module in python
But we dont use rust
We use python
Let us use Python buildin module to solve this problme
Our target is use Python buildin module to calc MD5 value of string

3af48e382439ffd980b531dfda1e6b93
f804aab4d84f3501eaf63d9dc9967569
801687047585911d47201d1fd7ddd427
faea0fffb3fd499797455e4156d7dcba
6ce7bfd25c0190735fa6115c8f4e43dc
05ce95b8735c2aa388b42af8936cddfd
f925e254ada1bb141f23282515c1c67f
409fbc5525bd062d7d14561c11336195

提示（MD5算法流程）

MD5算法将任意长度的输入转换为 $128$ 位（$16$字节）的固定长度输出。算法分为三个主要步骤：补位、分块和哈希计算。

1. 补位

1. 将输入字符串转换为字节序列（使用ASCII编码）
2. 在字节序列末尾添加一个0x80字节（二进制10000000）
3. 添加零字节0x00，直到字节序列长度满足：$长度 \mod 64 == 56$ （若本来就满足，那么就不需要添加零字节）
4. 最后添加8个字节，以小端序（最低有效字节在前）存储原始消息的位长度（原始字节数 $× 8$）

小端序（Little-endian）：数字的低位字节存储在低地址（或先出现）

比如数字 0x12345678（十六进制）：0x78 0x56 0x34 0x12「（低位）在前面」

2. 分块

将补位后的消息按$512$位（$64$字节）分块。每个块包含$16$个$32$位字$M_0 \dots M_{15}$，每个字按小端序解析：

3. 哈希计算

初始化

初始化$4$个$32$位变量（小端序）：

A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476

执行$4$轮操作（每轮$16$步，共$64$步）：

第$1$轮（步骤$0-15$）：

• 使用函数$F$
• 对于第 $i$ 步$（0≤i≤15）$：
  • $g = i$
  • $s = [7,12,17,22][i \mod 4]$
  • 操作：$A = B + left\_rotate((A + F(B,C,D) + M_g + T_{i+1}), s)$

第$2$轮（步骤$16-31$）：

• 使用函数$G$
• 对于第 $i$ 步$（16≤i≤31）$：
  • $g = (5 \times i + 1) \mod 16$
  • $s = [5,9,14,20][i \mod 4]$
  • 操作：$A = B + left\_rotate((A + G(B,C,D) + M_g + T_{i+1}), s)$

第$3$轮（步骤$32-47$）：

• 使用函数$H$
• 对于第 $i$ 步$（32≤i≤47）$：
  • $g = (3 \times i + 5) \mod 16$
  • $s = [4,11,16,23][i \mod 4]$
  • 操作：$A = B + left\_rotate((A + H(B,C,D) + M_g + T_{i+1}), s)$

第$4$轮（步骤$48-63$）：

• 使用函数 $I$
• 对于第 $i$ 步$（48≤i≤63）$：
  • $g = (7\times i) \mod 16$
  • $s = [6,10,15,21][i \mod 4]$
  • 操作：$A = B + left\_rotate((A + I(B,C,D) + M_g + T_{i+1}), s)$

注意：在每步操作后，需要旋转寄存器：$(A,B,C,D) = (D,A,B,C)$，且所有加法结果需要对 $2³²$取模。

处理完所有数据块后，将$A、B、C、D$变成其小端序

最终输出

$A、B、C、D$ 的十六进制表示（中间不用空格风格）

最后的转成十六进制数后输出可以使用以下代码快速完成转换输出

• C语言

printf("%08x%08x%08x%08x\n", a, b, c, d)

• C++

cout << hex << setfill('0') 
     << setw((8) << a 
     << setw((8) << b 
     << setw((8) << c 
     << setw((8) << d;

• Pyhon

print(f"{a:08x}{b:08x}{c:08x}{d:08x}")

附录

辅助函数

定义4个非线性函数（所有变量均为$32$位无符号整数）：

$F(X,Y,Z) = (X ∧ Y) ∨ (¬X ∧ Z)$

$G(X,Y,Z) = (X ∧ Z) ∨ (Y ∧ ¬Z)$

$H(X,Y,Z) = X ⊕ Y ⊕ Z$

$I(X,Y,Z) = Y ⊕ (X ∨ ¬Z)$

其中 $⊕$ 意为异或运算， $∧$ 意为位与运算，$∨$ 意为位或运算，$¬$意为按位取反操作

定义循环左移函数：$left\_rotate(x, n) = ((x \ll n) | (x \gg (32-n))) ∧ 0xFFFFFFFF$

其中

• $x \ll n$ 意为： 将 $x$ 左移 $n$ 位，右侧补0
• $x \gg k$ 意为： 将 $x$ 右移 $k$ 位，左侧补0

常数表 T

使用预定义的$64$个$32$位常数（$T_1$到$T_{64}$）：

T[1] = 0xd76aa478, T[2] = 0xe8c7b756, T[3] = 0x242070db, T[4] = 0xc1bdceee
T[5] = 0xf57c0faf, T[6] = 0x4787c62a, T[7] = 0xa8304613, T[8] = 0xfd469501
T[9] = 0x698098d8, T[10] = 0x8b44f7af, T[11] = 0xffff5bb1, T[12] = 0x895cd7be
T[13] = 0x6b901122, T[14] = 0xfd987193, T[15] = 0xa679438e, T[16] = 0x49b40821
T[17] = 0xf61e2562, T[18] = 0xc040b340, T[19] = 0x265e5a51, T[20] = 0xe9b6c7aa
T[21] = 0xd62f105d, T[22] = 0x02441453, T[23] = 0xd8a1e681, T[24] = 0xe7d3fbc8
T[25] = 0x21e1cde6, T[26] = 0xc33707d6, T[27] = 0xf4d50d87, T[28] = 0x455a14ed
T[29] = 0xa9e3e905, T[30] = 0xfcefa3f8, T[31] = 0x676f02d9, T[32] = 0x8d2a4c8a
T[33] = 0xfffa3942, T[34] = 0x8771f681, T[35] = 0x6d9d6122, T[36] = 0xfde5380c
T[37] = 0xa4beea44, T[38] = 0x4bdecfa9, T[39] = 0xf6bb4b60, T[40] = 0xbebfbc70
T[41] = 0x289b7ec6, T[42] = 0xeaa127fa, T[43] = 0xd4ef3085, T[44] = 0x04881d05
T[45] = 0xd9d4d039, T[46] = 0xe6db99e5, T[47] = 0x1fa27cf8, T[48] = 0xc4ac5665
T[49] = 0xf4292244, T[50] = 0x432aff97, T[51] = 0xab9423a7, T[52] = 0xfc93a039
T[53] = 0x655b59c3, T[54] = 0x8f0ccc92, T[55] = 0xffeff47d, T[56] = 0x85845dd1
T[57] = 0x6fa87e4f, T[58] = 0xfe2ce6e0, T[59] = 0xa3014314, T[60] = 0x4e0811a1
T[61] = 0xf7537e82, T[62] = 0xbd3af235, T[63] = 0x2ad7d2bb, T[64] = 0xeb86d391