Circom 中的 MD5 哈希
- RareSkills
- 发布于 2025-04-16 10:06
- 阅读 613
本文详细介绍了如何在 Circom 中实现 MD5 哈希算法，包括计算哈希值和约束其正确性。文章首先介绍了 MD5 哈希的原理和步骤，然后展示了如何在 Circom 中构建实现 MD5 哈希所需的各种组件，如位运算、循环左移、32 位加法以及初始填充。并通过一个python的例子，展示了MD5哈希的计算过程。
在本教程中，我们将使用 Circom 实现 MD5 哈希，既可以计算哈希值，也可以在 Circom 中约束其正确计算。
尽管 MD5 哈希函数在密码学上并不安全（因为已经发现了冲突），但其机制与密码学上安全的哈希函数类似。
重要的是，MD5 哈希函数可以快速学习。以下 14 分钟的视频解释了 MD5 哈希的工作原理。我们建议先观看它：
<https://www.youtube.com/watch?v=5MiMK45gkTY>
为了创建一个证明，证明我们知道 MD5 哈希的 preimage 但不泄露它，我们需要证明我们正确执行了哈希的每一步并产生了一定的结果。本教程展示了如何为每个状态转换设计约束。
具体来说，MD5 哈希具有以下子程序：
- 按位 AND、OR、NOT 和 XOR
- LeftRotate
- 加 32 位数字并在 $2^{32}$ 处溢出
- 函数
Func，它使用按位运算符将寄存器B、C和D组合在一起 - 开始时的填充步骤，在输入后添加 1 位并放入输入的长度（以位为单位）
此外，MD5 的输出通常以 big-endian 形式的 128 位数字书写。假设我们有一个 128 位的值 0x1234567890ABCDEF1122334455667788
在 big-endian 中，它将被写成：
0x12 0x34 0x56 0x78 0x90 0xAB 0xCD 0xEF 0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88在 little-endian 中，它将被写成：
0x88 0x77 0x66 0x55 0x44 0x33 0x22 0x11 0xEF 0xCD 0xAB 0x90 0x78 0x56 0x34 0x12我们将需要一个单独的例程来反转字节的顺序，从 little endian 到 big endian。大多数哈希实现都输出 big endian，因此为了轻松地将我们的结果与已建立的库进行比较，我们希望我们的实现以 big endian 格式输出。我们稍后将为此创建一个 ToBytes 组件。
虽然有大量的数组索引，但我们使用的索引是基于哈希的迭代确定的，因此哈希约束中不需要任何 Quin 选择器——我们可以硬编码数组索引。
在 Python 中构建 MD5 原型
在构建像哈希函数这样复杂的东西时，最好用一种更熟悉且更易于调试的语言（如 Python）构建参考实现，然后将 Python 代码转换为 Circom。
这是 MD5 的 Python 实现（为简单起见，仅支持 448 位的输入）。这在很大程度上受到了 Utkarsh87 的另一个实现 的启发。我们试图使函数的行为“像组件一样”，因此转换为 Circom 更加简单。
一些实现说明：
- 加法模 $2^{32}$ 通过添加数字然后调用函数
Overflow32()来完成。 - 我们接受输入作为字节数组，而不是作为位数组。
- 字节
0x80在二进制中看起来像10000000。这允许我们在输入的末尾用单个位填充输入。 - 输出为 big-endian 格式。
s = [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]
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]
iter_to_index = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9]
def Overflow32(x):
return x & 0xFFFFFFFF
def leftRotate(x, amount):
#x &= 0xFFFFFFFF
xo = Overflow32(x)
return Overflow32((xo << amount | xo >> (32 -amount)))
def func(B, C, D, i):
out = None
# note that i will be 1..64 inclusive
# 请注意，i 将是 1..64（含）
if i <= 16:
out = (B & C) | (~B & D)
elif i > 16 and i <= 32:
out = (D & B) | (~D & C)
elif i > 32 and i <= 48:
out = B ^ C ^ D
elif i > 48 and i <= 64:
out = C ^ (B | ~D)
else:
assert False, "1) What"
return out
## concatenates four bytes to become 32 bits
# 连接四个字节以变为 32 位
def To32BitWord(byte1, byte2, byte3, byte4):
return byte1 + byte2 * 2**8 + byte3 * 2**16 + byte4 * 2**24
## length is the byte where the data stops
# length 是数据停止的字节
## so if we have zero bytes, we write 0x80
# 因此，如果我们有零字节，我们写入 0x80
## to byte 0
# 到字节 0
def md5(bytes, length):
data = bytearray(64)
msg = bytearray(bytes, 'ascii')
# 56 bytes, 64 is the max
# 56 字节，64 是最大值
assert length < 56, "too long"
if length < 56:
data[length] = 0x80
data[56] = (length * 8).to_bytes(1, byteorder='little')[0]
for i in range(57,64):
data[i] = 0x00
for i in range(0, length):
data[i] = msg[i]
# data is a len 64 array of bytes. However, it will be much easier to work
# data 是一个长度为 64 的字节数组。但是，如果我们将其转换为长度为 16 的 32 位单词数组，则更容易处理
# on if we turn it into a len 16 array of 32 bit words
data_32 = [0] * 16
for i in range(0, 16):
data_32[i] = To32BitWord(data[4*i], data[4*i + 1], data[4*i + 2], data[4*i + 3])
# algo runs for 64 iterations with 4 registers, each using 32 bits
# 算法运行 64 次迭代，使用 4 个寄存器，每个寄存器使用 32 位
# we allocate 65, because the 0th will be the default starting value
# 我们分配 65，因为第 0 个将是默认起始值
buffer = [[0]*4 for _ in range(65)]
buffer[0][0] = 0x67452301
buffer[0][1] = 0xefcdab89
buffer[0][2] = 0x98badcfe
buffer[0][3] = 0x10325476
A = 0
B = 1
C = 2
D = 3
for i in range(1, 65):
F = func(buffer[i - 1][B], buffer[i - 1][C], buffer[i - 1][D], i)
G = iter_to_index[i - 1]
to_rotate = buffer[i-1][A] + F + K[i - 1] + data_32[iter_to_index[i - 1]]
rotated = leftRotate(to_rotate, s[i - 1])
new_B = Overflow32(buffer[i-1][B] + rotated)
buffer[i][A] = buffer[i - 1][D]
buffer[i][B] = new_B
buffer[i][C] = buffer[i - 1][B]
buffer[i][D] = buffer[i - 1][C]
final = [0,0,0,0]
for i, b in enumerate(buffer[64]):
final[i] = Overflow32((b + buffer[0][i]))
digest = final[0] + final[1] * 2**32 + final[2] * 2**64 + final[3] * 2**96
raw = digest.to_bytes(16, byteorder='little')
return int.from_bytes(raw, byteorder='big')
print(hex(md5("RareSkills", 10)))
先决条件组件
Overflow32
Overflow32 模拟 VM 中在 $2^{32}$ 发生的 32 位溢出：
template Overflow32() {
signal input in;
signal output out;
component n2b = Num2Bits(252);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
n2b.out[i] ==> b2n.in[i];
}
b2n.out ==> out;
}LeftRotate
LeftRotate 旋转位，就好像它们在一个循环缓冲区中一样：
template LeftRotate(s) {
signal input in;
signal output out;
component n2b = Num2Bits(32);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
b2n.in[(i + s) % 32] <== n2b.out[i];
}
out <== b2n.out;
}按位 AND、OR、XOR 和 NOT
以下模板是在我们的 32 位仿真教程中构建的：
template BitwiseAnd32() {
signal input in[2];
signal output out;
// range check
// 范围检查
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ands[32];
for (var i = 0; i < 32; i++) {
Ands[i] = AND();
Ands[i].a <== n2ba.out[i];
Ands[i].b <== n2bb.out[i];
Ands[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseOr32() {
signal input in[2];
signal output out;
// range check
// 范围检查
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ors[32];
for (var i = 0; i < 32; i++) {
Ors[i] = OR();
Ors[i].a <== n2ba.out[i];
Ors[i].b <== n2bb.out[i];
Ors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseXor32() {
signal input in[2];
signal output out;
// range check
// 范围检查
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Xors[32];
for (var i = 0; i < 32; i++) {
Xors[i] = XOR();
Xors[i].a <== n2ba.out[i];
Xors[i].b <== n2bb.out[i];
Xors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseNot32() {
signal input in;
signal output out;
// range check
// 范围检查
component n2ba = Num2Bits(32);
n2ba.in <== in;
component b2n = Bits2Num(32);
component Nots[32];
for (var i = 0; i < 32; i++) {
Nots[i] = NOT();
Nots[i].in <== n2ba.out[i];
Nots[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}Func
Func 接受寄存器 B、C 和 D 并将它们组合成一个输出——并且该组合取决于我们正在进行的迭代：
template Func(i) {
assert(i <= 64);
signal input b;
signal input c;
signal input d;
signal output out;
if (i <= 16) {
signal bAndc;
component a1 = BitwiseAnd32();
a1.in[0] <== b;
a1.in[1] <== c;
component a2 = BitwiseAnd32();
component n1 = BitwiseNot32();
n1.in <== b;
a2.in[0] <== n1.out;
a2.in[1] <== d;
component o1 = BitwiseOr32();
o1.in[0] <==...
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
