在 O(n) 的复杂性内反转 SHA-256 sigma0 函数？
Reverse SHA-256 sigma0 function within complexity of O(n)?
简介
作为 SHA-256 散列算法的一部分，有一个函数通常被称为 σ1，或为方便起见 sigma0。基本上，它以 X 作为输入，其中 X 是 32 位无符号值。然后像这样转换它：
ROTATE_RIGHT(X, 7) ^ ROTATE_RIGHT(X, 18) ^ SHIFT_RIGHT(X, 3)
一点解释，如果你需要的话：
- ROTATE_RIGHT(X, Y) - 将 X 的位向右旋转 Y
- SHIFT_RIGHT(X, Y) - 将 X 的位向右移动 Y，因此结果的前 Y 位始终为 0
此外，如果您需要代码，这里是 Python 中的完整版本：
def rotate_right(x, y):
return (((x & 0xffffffff) >> (y & 31)) | (x << (32 - (y & 31)))) & 0xffffffff
def shift_right(x, n):
return (x & 0xffffffff) >> n
def sigma0(x):
return rotate_right(x, 7) ^ rotate_right(x, 18) ^ shift_right(x, 3)
反转函数
我开始怀疑那个东西是否是可逆的，令我惊讶的是，没多久就写了一个函数，通过给定 sigma0 的输出， returns 输入该函数，或者简单地说，反转 sigma0 函数。我不会把代码放在这里，因为它是用 Node.js 编写的，并且根据通过掩码搜索特定 sigma0 输入的更复杂的需求进行了很多修改，但我想给你一个基本的想法我是如何解决它的，所以也许你可以给我一些关于如何实现我需要的新想法。
我的解决方案很简单，但也是递归的。我们知道每个输出的位都是两个或三个输入位异或运算的结果。所以我做了一个依赖 table 这样我就可以看到输出的位是如何受到输入的影响的：
I: 00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
R7 25,26,27,28,29,30,31,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24
R18 14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,00,01,02,03,04,05,06,07,08,09,10,11,12,13
S3 zz,zz,zz,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28
---------------------------------------------------------------------------------------------------
O: 00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
这是关于什么的？比如说，在输出的第 1 位中我们有 1。为了方便，我将其写为 O[0]、O[1]、... O[31]，所以 O[x] 是 (x +1) 位的输出。输入相同，标记为I.
所以，O[0] == 1。在上面的table中我们看到O[0]是I[25]和I[14]异或运算的结果。这意味着这些输入的一位且只有一位必须为 1。因此此时我们可以说我们可以为输入创建两个 suitable 掩码：
##############0#########1#######
##############1#########0#######
那些面具是解决方案的关键，至少对我来说是这样。 # 表示任何值（0 或 1）。当我们创建掩码时，我们为下一位调用递归函数，但保留掩码。如果我们没有适合之前掩码的可能掩码，之前的掩码没有解决方案，如果我们达到第 32 位，我们保证掩码中没有尖锐，这将是答案。
首先，我需要告诉你这个东西是有效的。但是在 Node.js 它计算每个值大约 100 毫秒，我不知道我的递归算法最复杂的是什么，因为它很难测量。它不能满足我，我为了解决这个 O(n) 而绞尽脑汁。
问题
我想知道是否有可能在 O(n) 的复杂度内编写一个反转 sigma0 的函数，其中 n 是 input/output 中的位数并且它等于32，没有递归，掩码和树，简单快速。
我还没有为我的陈述得出任何数学证明，但我测试了很多不同的值，我可以自信地断言输入值的数量等于该函数的输出值的数量，并且两者都是等于 2^32 - 1。换句话说，对于每个输出，sigma0 函数只有一个可能的输入。
这让我想到 sigma0 原始函数产生复杂度为 O(n) 的结果，这意味着反向函数必须有一个也适用于 O(n) 的解。
如果你在数学上证明我这是不可能的，我也会接受这个答案，但我还没有发现任何表明这个任务不可能的东西。
消耗资源的解决方法
如果我有 16gb 的空闲 ram，我将能够预先计算所有可能的值到文件中，然后将它作为一个巨大的数组加载到 ram 中。但这不是解决方案，因为还有其他 3 个类似的功能，要为所有这些功能做到这一点，我需要 64gb 的 ram，这对于这个简单的任务来说太昂贵和过多了。
UPD：高斯消元法
感谢 Artjom B. 的评论，我找到了一种通过高斯消元法求解异或方程的好方法。目前我正在尝试解决这样的矩阵：
Input: 00000000100110101000111011101001
Output: 01110001101010000010010011100110
0: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 1
3: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 1
4: 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
5: 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 | 0
6: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 | 0
7: 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
8: 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
9: 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 | 0
10: 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 | 1
11: 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
12: 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
13: 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 0
14: 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 0
15: 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
16: 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0
17: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0
18: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
19: 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
20: 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
21: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
22: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 | 0
23: 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 | 0
24: 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
25: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
26: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 | 1
27: 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 | 0
28: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 | 0
29: 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 | 1
30: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 | 1
31: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 | 0
发布了矩阵，这样您就可以看到它的外观，而不是浪费时间自己创建它。无论我是否解决了问题，我都会更新我的问题。
如果我们将 sigma0 视为 GF(2)32 向量上的函数，您会注意到它是线性的。 GF(2)32 中的加法只是二进制 XOR:
>>> sigma0(235 ^ 352124)
2045075788
>>> sigma0(235) ^ sigma0(352124)
2045075788
这意味着如果我们可以找到 sigma0(x0) = 0b1、sigma0(x1) = 0b10 等，我们就可以轻松地逐位反转任何内容。我们可以很容易地用 z3:
找到这些逆
import z3
def z3_sigma0(x):
return z3.RotateRight(x, 7) ^ z3.RotateRight(x, 18) ^ z3.LShR(x, 3)
s = z3.Solver()
xs = [z3.BitVec(f"x{i}", 32) for i in range(32)]
for i in range(32):
s.add(z3_sigma0(xs[i]) == (1 << i))
print(s.check())
m = s.model()
for i in range(32):
print("x{:02} = 0x{:08x}".format(i, m[xs[i]].as_long()))
这立即输出：
sat
x00 = 0x185744e9
x01 = 0x30ae89d2
x02 = 0x615d13a4
x03 = 0xdaed63a1
x04 = 0x9cd03a8e
x05 = 0x08fdcc39
x06 = 0x11fb9872
x07 = 0x23f730e4
x08 = 0x5fb92521
x09 = 0xbf724a42
x10 = 0x57ee6948
x11 = 0xafdcd290
x12 = 0x76b358ec
x13 = 0xf531f531
x14 = 0xc36917ae
x15 = 0xb78f9679
x16 = 0x4615d13e
x17 = 0x947ce695
x18 = 0x19a4740f
x19 = 0x2b1facf7
x20 = 0x4e681d07
x21 = 0x84877ee7
x22 = 0x385344eb
x23 = 0x70a689d6
x24 = 0xf91a5745
x25 = 0xc36917af
x26 = 0xb78f967b
x27 = 0x4615d13a
x28 = 0x8c2ba274
x29 = 0x290afdcd
x30 = 0x4a42bf73
x31 = 0x94857ee6
因此我们可以使用它来制作我们的反函数：
sigma0_singleton_inverses = [
0x185744e9, 0x30ae89d2, 0x615d13a4, 0xdaed63a1, 0x9cd03a8e, 0x08fdcc39,
0x11fb9872, 0x23f730e4, 0x5fb92521, 0xbf724a42, 0x57ee6948, 0xafdcd290,
0x76b358ec, 0xf531f531, 0xc36917ae, 0xb78f9679, 0x4615d13e, 0x947ce695,
0x19a4740f, 0x2b1facf7, 0x4e681d07, 0x84877ee7, 0x385344eb, 0x70a689d6,
0xf91a5745, 0xc36917af, 0xb78f967b, 0x4615d13a, 0x8c2ba274, 0x290afdcd,
0x4a42bf73, 0x94857ee6
]
def inv_sigma0(x):
r = 0
for i in range(32):
if x & (1 << i):
r ^= sigma0_singleton_inverses[i]
return r
确实：
>>> def test_inv_once():
... r = random.randrange(2**32)
... return inv_sigma0(sigma0(r)) == r
>>> all(test_inv_once() for _ in range(10**6))
True
上面可以完全无环无分支地写成：
def inv_sigma0(x):
xn = ~x
r = (((xn >> 0) & 1) - 1) & 0x185744e9
r ^= (((xn >> 1) & 1) - 1) & 0x30ae89d2
r ^= (((xn >> 2) & 1) - 1) & 0x615d13a4
r ^= (((xn >> 3) & 1) - 1) & 0xdaed63a1
r ^= (((xn >> 4) & 1) - 1) & 0x9cd03a8e
r ^= (((xn >> 5) & 1) - 1) & 0x08fdcc39
r ^= (((xn >> 6) & 1) - 1) & 0x11fb9872
r ^= (((xn >> 7) & 1) - 1) & 0x23f730e4
r ^= (((xn >> 8) & 1) - 1) & 0x5fb92521
r ^= (((xn >> 9) & 1) - 1) & 0xbf724a42
r ^= (((xn >> 10) & 1) - 1) & 0x57ee6948
r ^= (((xn >> 11) & 1) - 1) & 0xafdcd290
r ^= (((xn >> 12) & 1) - 1) & 0x76b358ec
r ^= (((xn >> 13) & 1) - 1) & 0xf531f531
r ^= (((xn >> 14) & 1) - 1) & 0xc36917ae
r ^= (((xn >> 15) & 1) - 1) & 0xb78f9679
r ^= (((xn >> 16) & 1) - 1) & 0x4615d13e
r ^= (((xn >> 17) & 1) - 1) & 0x947ce695
r ^= (((xn >> 18) & 1) - 1) & 0x19a4740f
r ^= (((xn >> 19) & 1) - 1) & 0x2b1facf7
r ^= (((xn >> 20) & 1) - 1) & 0x4e681d07
r ^= (((xn >> 21) & 1) - 1) & 0x84877ee7
r ^= (((xn >> 22) & 1) - 1) & 0x385344eb
r ^= (((xn >> 23) & 1) - 1) & 0x70a689d6
r ^= (((xn >> 24) & 1) - 1) & 0xf91a5745
r ^= (((xn >> 25) & 1) - 1) & 0xc36917af
r ^= (((xn >> 26) & 1) - 1) & 0xb78f967b
r ^= (((xn >> 27) & 1) - 1) & 0x4615d13a
r ^= (((xn >> 28) & 1) - 1) & 0x8c2ba274
r ^= (((xn >> 29) & 1) - 1) & 0x290afdcd
r ^= (((xn >> 30) & 1) - 1) & 0x4a42bf73
r ^= (((xn >> 31) & 1) - 1) & 0x94857ee6
return r
最快的版本可能是这个版本，一次按 16 位分组，使用 2 × 216 大小查找 table（或类似地四次查找到一个 4 × 28 大小 table).
sigma0_16bit_inverse_lo = [inv_sigma0(x) for x in range(2**16)]
sigma0_16bit_inverse_hi = [inv_sigma0(x << 16) for x in range(2**16)]
def fast_inv_sigma0(x):
return (sigma0_16bit_inverse_lo[x & 0xffff] ^
sigma0_16bit_inverse_hi[(x >> 16) & 0xffff])
简介
作为 SHA-256 散列算法的一部分，有一个函数通常被称为 σ1，或为方便起见 sigma0。基本上，它以 X 作为输入，其中 X 是 32 位无符号值。然后像这样转换它：
ROTATE_RIGHT(X, 7) ^ ROTATE_RIGHT(X, 18) ^ SHIFT_RIGHT(X, 3)
一点解释，如果你需要的话：
- ROTATE_RIGHT(X, Y) - 将 X 的位向右旋转 Y
- SHIFT_RIGHT(X, Y) - 将 X 的位向右移动 Y，因此结果的前 Y 位始终为 0
此外，如果您需要代码，这里是 Python 中的完整版本：
def rotate_right(x, y):
return (((x & 0xffffffff) >> (y & 31)) | (x << (32 - (y & 31)))) & 0xffffffff
def shift_right(x, n):
return (x & 0xffffffff) >> n
def sigma0(x):
return rotate_right(x, 7) ^ rotate_right(x, 18) ^ shift_right(x, 3)
反转函数
我开始怀疑那个东西是否是可逆的，令我惊讶的是，没多久就写了一个函数，通过给定 sigma0 的输出， returns 输入该函数，或者简单地说，反转 sigma0 函数。我不会把代码放在这里，因为它是用 Node.js 编写的，并且根据通过掩码搜索特定 sigma0 输入的更复杂的需求进行了很多修改，但我想给你一个基本的想法我是如何解决它的，所以也许你可以给我一些关于如何实现我需要的新想法。
我的解决方案很简单，但也是递归的。我们知道每个输出的位都是两个或三个输入位异或运算的结果。所以我做了一个依赖 table 这样我就可以看到输出的位是如何受到输入的影响的：
I: 00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
R7 25,26,27,28,29,30,31,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24
R18 14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,00,01,02,03,04,05,06,07,08,09,10,11,12,13
S3 zz,zz,zz,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28
---------------------------------------------------------------------------------------------------
O: 00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
这是关于什么的？比如说，在输出的第 1 位中我们有 1。为了方便，我将其写为 O[0]、O[1]、... O[31]，所以 O[x] 是 (x +1) 位的输出。输入相同，标记为I.
所以，O[0] == 1。在上面的table中我们看到O[0]是I[25]和I[14]异或运算的结果。这意味着这些输入的一位且只有一位必须为 1。因此此时我们可以说我们可以为输入创建两个 suitable 掩码：
##############0#########1#######
##############1#########0#######
那些面具是解决方案的关键，至少对我来说是这样。 # 表示任何值（0 或 1）。当我们创建掩码时，我们为下一位调用递归函数，但保留掩码。如果我们没有适合之前掩码的可能掩码，之前的掩码没有解决方案，如果我们达到第 32 位，我们保证掩码中没有尖锐，这将是答案。
首先，我需要告诉你这个东西是有效的。但是在 Node.js 它计算每个值大约 100 毫秒，我不知道我的递归算法最复杂的是什么，因为它很难测量。它不能满足我，我为了解决这个 O(n) 而绞尽脑汁。
问题
我想知道是否有可能在 O(n) 的复杂度内编写一个反转 sigma0 的函数，其中 n 是 input/output 中的位数并且它等于32，没有递归，掩码和树，简单快速。
我还没有为我的陈述得出任何数学证明，但我测试了很多不同的值，我可以自信地断言输入值的数量等于该函数的输出值的数量，并且两者都是等于 2^32 - 1。换句话说，对于每个输出，sigma0 函数只有一个可能的输入。
这让我想到 sigma0 原始函数产生复杂度为 O(n) 的结果，这意味着反向函数必须有一个也适用于 O(n) 的解。
如果你在数学上证明我这是不可能的，我也会接受这个答案，但我还没有发现任何表明这个任务不可能的东西。
消耗资源的解决方法
如果我有 16gb 的空闲 ram，我将能够预先计算所有可能的值到文件中，然后将它作为一个巨大的数组加载到 ram 中。但这不是解决方案，因为还有其他 3 个类似的功能，要为所有这些功能做到这一点，我需要 64gb 的 ram，这对于这个简单的任务来说太昂贵和过多了。
UPD：高斯消元法
感谢 Artjom B. 的评论，我找到了一种通过高斯消元法求解异或方程的好方法。目前我正在尝试解决这样的矩阵：
Input: 00000000100110101000111011101001
Output: 01110001101010000010010011100110
0: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 1
3: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 1
4: 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
5: 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 | 0
6: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 | 0
7: 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
8: 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
9: 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 | 0
10: 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 | 1
11: 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
12: 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
13: 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 0
14: 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 0
15: 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
16: 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0
17: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0
18: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
19: 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
20: 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
21: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
22: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 | 0
23: 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 | 0
24: 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
25: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
26: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 | 1
27: 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 | 0
28: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 | 0
29: 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 | 1
30: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 | 1
31: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 | 0
发布了矩阵，这样您就可以看到它的外观，而不是浪费时间自己创建它。无论我是否解决了问题，我都会更新我的问题。
如果我们将 sigma0 视为 GF(2)32 向量上的函数，您会注意到它是线性的。 GF(2)32 中的加法只是二进制 XOR:
>>> sigma0(235 ^ 352124)
2045075788
>>> sigma0(235) ^ sigma0(352124)
2045075788
这意味着如果我们可以找到 sigma0(x0) = 0b1、sigma0(x1) = 0b10 等，我们就可以轻松地逐位反转任何内容。我们可以很容易地用 z3:
import z3
def z3_sigma0(x):
return z3.RotateRight(x, 7) ^ z3.RotateRight(x, 18) ^ z3.LShR(x, 3)
s = z3.Solver()
xs = [z3.BitVec(f"x{i}", 32) for i in range(32)]
for i in range(32):
s.add(z3_sigma0(xs[i]) == (1 << i))
print(s.check())
m = s.model()
for i in range(32):
print("x{:02} = 0x{:08x}".format(i, m[xs[i]].as_long()))
这立即输出：
sat
x00 = 0x185744e9
x01 = 0x30ae89d2
x02 = 0x615d13a4
x03 = 0xdaed63a1
x04 = 0x9cd03a8e
x05 = 0x08fdcc39
x06 = 0x11fb9872
x07 = 0x23f730e4
x08 = 0x5fb92521
x09 = 0xbf724a42
x10 = 0x57ee6948
x11 = 0xafdcd290
x12 = 0x76b358ec
x13 = 0xf531f531
x14 = 0xc36917ae
x15 = 0xb78f9679
x16 = 0x4615d13e
x17 = 0x947ce695
x18 = 0x19a4740f
x19 = 0x2b1facf7
x20 = 0x4e681d07
x21 = 0x84877ee7
x22 = 0x385344eb
x23 = 0x70a689d6
x24 = 0xf91a5745
x25 = 0xc36917af
x26 = 0xb78f967b
x27 = 0x4615d13a
x28 = 0x8c2ba274
x29 = 0x290afdcd
x30 = 0x4a42bf73
x31 = 0x94857ee6
因此我们可以使用它来制作我们的反函数：
sigma0_singleton_inverses = [
0x185744e9, 0x30ae89d2, 0x615d13a4, 0xdaed63a1, 0x9cd03a8e, 0x08fdcc39,
0x11fb9872, 0x23f730e4, 0x5fb92521, 0xbf724a42, 0x57ee6948, 0xafdcd290,
0x76b358ec, 0xf531f531, 0xc36917ae, 0xb78f9679, 0x4615d13e, 0x947ce695,
0x19a4740f, 0x2b1facf7, 0x4e681d07, 0x84877ee7, 0x385344eb, 0x70a689d6,
0xf91a5745, 0xc36917af, 0xb78f967b, 0x4615d13a, 0x8c2ba274, 0x290afdcd,
0x4a42bf73, 0x94857ee6
]
def inv_sigma0(x):
r = 0
for i in range(32):
if x & (1 << i):
r ^= sigma0_singleton_inverses[i]
return r
确实：
>>> def test_inv_once():
... r = random.randrange(2**32)
... return inv_sigma0(sigma0(r)) == r
>>> all(test_inv_once() for _ in range(10**6))
True
上面可以完全无环无分支地写成：
def inv_sigma0(x):
xn = ~x
r = (((xn >> 0) & 1) - 1) & 0x185744e9
r ^= (((xn >> 1) & 1) - 1) & 0x30ae89d2
r ^= (((xn >> 2) & 1) - 1) & 0x615d13a4
r ^= (((xn >> 3) & 1) - 1) & 0xdaed63a1
r ^= (((xn >> 4) & 1) - 1) & 0x9cd03a8e
r ^= (((xn >> 5) & 1) - 1) & 0x08fdcc39
r ^= (((xn >> 6) & 1) - 1) & 0x11fb9872
r ^= (((xn >> 7) & 1) - 1) & 0x23f730e4
r ^= (((xn >> 8) & 1) - 1) & 0x5fb92521
r ^= (((xn >> 9) & 1) - 1) & 0xbf724a42
r ^= (((xn >> 10) & 1) - 1) & 0x57ee6948
r ^= (((xn >> 11) & 1) - 1) & 0xafdcd290
r ^= (((xn >> 12) & 1) - 1) & 0x76b358ec
r ^= (((xn >> 13) & 1) - 1) & 0xf531f531
r ^= (((xn >> 14) & 1) - 1) & 0xc36917ae
r ^= (((xn >> 15) & 1) - 1) & 0xb78f9679
r ^= (((xn >> 16) & 1) - 1) & 0x4615d13e
r ^= (((xn >> 17) & 1) - 1) & 0x947ce695
r ^= (((xn >> 18) & 1) - 1) & 0x19a4740f
r ^= (((xn >> 19) & 1) - 1) & 0x2b1facf7
r ^= (((xn >> 20) & 1) - 1) & 0x4e681d07
r ^= (((xn >> 21) & 1) - 1) & 0x84877ee7
r ^= (((xn >> 22) & 1) - 1) & 0x385344eb
r ^= (((xn >> 23) & 1) - 1) & 0x70a689d6
r ^= (((xn >> 24) & 1) - 1) & 0xf91a5745
r ^= (((xn >> 25) & 1) - 1) & 0xc36917af
r ^= (((xn >> 26) & 1) - 1) & 0xb78f967b
r ^= (((xn >> 27) & 1) - 1) & 0x4615d13a
r ^= (((xn >> 28) & 1) - 1) & 0x8c2ba274
r ^= (((xn >> 29) & 1) - 1) & 0x290afdcd
r ^= (((xn >> 30) & 1) - 1) & 0x4a42bf73
r ^= (((xn >> 31) & 1) - 1) & 0x94857ee6
return r
最快的版本可能是这个版本，一次按 16 位分组，使用 2 × 216 大小查找 table（或类似地四次查找到一个 4 × 28 大小 table).
sigma0_16bit_inverse_lo = [inv_sigma0(x) for x in range(2**16)]
sigma0_16bit_inverse_hi = [inv_sigma0(x << 16) for x in range(2**16)]
def fast_inv_sigma0(x):
return (sigma0_16bit_inverse_lo[x & 0xffff] ^
sigma0_16bit_inverse_hi[(x >> 16) & 0xffff])