在 O(n) 的复杂度内反转 SHA-256 sigma0 函数？

Question

介绍

作为 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 的完整版本：

ROTATE_RIGHT(X, 7) ^ ROTATE_RIGHT(X, 18) ^ SHIFT_RIGHT(X, 3)

反向功能

我开始怀疑那个东西是否可逆，令我惊讶的是，编写一个函数并没有花很长时间，该函数根据 givensigma0的输出返回该函数的输入，或者简单地说，反转sigma0函数。我不会把代码放在这里，因为它是用 Node.js 编写的，并且根据sigma0通过掩码搜索特定输入的更复杂的需求进行了大量修改，但我想给你一个我如何解决它的基本概念，所以也许你可以用一些关于如何实现我需要的新想法来启发我。

我的解决方案很简单，但它也是递归的。我们知道每个输出的位都是两个或三个输入位的异或运算的结果。所以我制作了一个依赖表，以便我可以看到输出位如何受到输入位的影响：

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。在上表中我们可以看到，O[0]是的XOR运算的结果I[25]和I[14]。这意味着这些输入的位中只有一个必须是 1。所以在这一点上，我们可以说我们可以为输入创建两个合适的掩码：

##############0#########1#######
##############1#########0#######

这些面具是解决方案的关键，至少对我来说是这样。#表示任何值（0 或 1）。当我们创建掩码时，我们为下一位调用递归函数，但保留掩码。如果我们没有适合以前的掩码的可能掩码，则先前的掩码没有解决方案，如果我们达到第 32 位，我们保证掩码中没有锐利，这将是答案。

首先，我需要告诉你这东西有效。但是在 Node.js 上，它计算每个值大约 100 毫秒，我不知道我的递归算法最糟糕的复杂性是什么，因为它很难衡量。它不满足我，我在试图解决这个 O(n) 的时候脑子坏掉了。

问题

我想知道是否有可能编写一个sigma0在 O(n) 复杂度内反转的函数，其中n输入/输出中的位数等于 32，没有递归、掩码或树，简单而快速。

我没有为我的陈述得出任何数学证明，但我测试了许多不同的值，我可以自信地声称输入值的数量等于这个函数的输出值的数量，并且两者都等于2^32 - 1。换句话说，对于每个输出，只有一个可能的sigma0函数输入。

这让我想到，sigma0原始函数产生复杂度为 O(n)的事实意味着反向函数必须有一个也适用于 O(n) 的解决方案。

如果您在数学上向我证明这是不可能的，我也会接受这个答案，但我没有发现任何表明此任务不可能的内容。

消耗资源的解决方法

如果我有 16gb 的空闲内存，我可以将所有可能的值预先计算到文件中，然后将它作为一个巨大的数组加载到内存中。但这不是解决方案，因为还有其他 3 个类似的功能，要为所有这些功能做到这一点，我需要 64gb 的内存，这对于这个简单的任务来说太昂贵和过多了。

UPD：高斯消元法

感谢 Artjom B. 的评论，我找到了一种通过高斯消元法求解 XOR 方程的好方法。目前我正在尝试解决这样的矩阵：

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

发布矩阵，这样您就可以看到它的外观，而不必浪费时间自己创建它。一旦我解决了它，我会更新我的问题。

Answer 1

如果我们将其sigma0视为 GF(2) ³²向量上的函数，您会注意到它是线性的。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

最快的版本可能是这个，使用 2 × 2 ¹⁶大小的查找表（或类似地对 4 × 2 ⁸大小的表进行四次查找）一次按 16 位分组。

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])