MD5使用以下函数：
$ f_ {1}（ B，C，D）=（B \ wedge C）\ lor（D \ wedge \ lnot B）$
$ f_ {2}（B，C，D）=（B \ wedge D ）\ lor（C \ wedge \ lnot D）$
$ f_ {3}（B，C，D）= B \ oplus C \ oplus D $
$ f_ {4}（B，C，D）= C \ oplus（B \ lor \ lnot D）$
SHA-1使用以下功能：
$ f_ { 1}（B，C，D）=（B \ wedge C）\ lor（D \ wedge \ lnot B）$
$ f_ {2}（B，C，D）= B \ oplus C \ oplus D $
$ f_ {3}（B，C，D）=（B \ wedge C）\ lor（B \ wedge D）\ lor（C \ wedge D）$
$ f_ {4}（B，C，D）= B \ oplus C \ oplus D $
SHA-2使用以下功能：
$ f_ {1}（B，C，D）=（B \ wedge C）\ lor（D \ wedge \ lnot B）$
$ f_ {2}（B，C， D）=（B \ wedge C）\ oplus（B \ wedge D）\ oplus（C \ wedge D）$
我想知道如何选择这些功能。
我知道XOR在混合输入的各个位方面非常有效，但是我不知道为什么$（B \ wedge C）\ oplus（B \ wedge D）\ oplus（ C \ wedge D）$（SHA-2）比$（B \ wedge C）\ lor（B \ wedge D）\ lor（C \ wedge D）$（SHA-1）更有效。
有人可以澄清为什么某些功能会更好吗？以及如何选择特定功能。
#1 楼
所考虑的函数是3位至1位的二进制函数（扩展为位向量，即按位函数）。有$ 2 ^ {（（2 ^ 3）} = 256 $这样的函数。所有考虑的函数都是平衡的；也就是说，函数输出为0且函数输出为1的输入组合的数目相等。这将函数的数目减少为$ 8！/（4！）^ 2 = 70 $。
在$ 3！= 6 $订单内聚合相同的平衡函数，而$ 3 $输入的$ 2 ^ 3 = 8 $极性仅留下$ 6 $类（请参阅最后一节）；在每个类中都保留按字典顺序排列的第一个功能：
其中，
g0和g4被排除在外，因为它们的至少一个输入对输出没有影响。其他四个函数表现出倾向于扩散的特性：对于任何固定为任一极性的输入，当我们改变其他输入时，输出是非恒定的；
它们的任何输入都会影响其他输入的四个组合中的至少两个的输出。
这些尚存的功能是：
/>
g1多数，用于SHA-1的$ f_3 $和SHA-2的$ f_2 $（结果是相同的）g2选择项，用于$ f_1 $和$ f_2 $ MD5，SHA-1的$ f_1 $，SHA-2的$ f_1 $；此功能也称为“选择”或“数字多路复用器”（输入x为1或0选择输出是y或z中的哪一个）； g3，用于（在输入的顺序和取反中）用于$ f_4 MD5美元；如注释中所述，该函数$（x \ wedge y）\ oplus z $也是Toffoli门的第三个输出； g5奇偶校验，用于MD5的$ f_3 $，$ f_2 $和$ SHA-1的f_4 $。每个注释的补充：
g1和g2还具有以下特性：对于其他输入的四个组合中的至少三个，它们的任何输入都会影响输出。或者换句话说，不是完全线性的他们的任何投入。从某种意义上讲，这是可取的，因为太多的线性会导致某些差分攻击。这可能就是为什么SHA-2中的g1和g2优于g3和g5的原因。有一条评论要求将3位平衡函数的类推导到1和2内。输入的极性。我们将以8位值$ b_ {000} \，b_ {001} \，b_ {010} \，b_ {011} \，b_ {100} \，b_ {101} \，b_表示一个函数{110} \，b_ {111} $为3个输入$ z \，y \，x $的8种组合给出输出$ b_ {zyx} $。
平衡的函数具有$ b_ {000} + b_ {001} + b_ {010} + b_ {011} + b_ {100} + b_ {101} + b_ {110} + b_ {111} = 4 $。我们按照字典顺序（相当于使用big-endian约定时的数字顺序）对其进行扫描；如果不排除，则表示新类的功能，我们排除通过排列输入或更改输入极性可从中获得的功能。我们可以通过考虑是否应用以下6种转换中的任何一种来做到这一点（在应用64种组合时存在一定的冗余，并且多次排除了许多功能，但这并不有害）：
将输出转换为$ b_ {000} \，b_ {010} \，b_ {001} \，b_ {011} \，b_ {100} \，b_ {110} \，b_ {101} \，b_ { 111} $（交换$ x $和$ y $）
将输出转换为$ b_ {000} \，b_ {001} \，b_ {100} \，b_ {101} \，b_ {010} \ ，b_ {011} \，b_ {110} \，b_ {111} $（交换$ y $和$ z $）
将输出转换为$ b_ {000} \，b_ {100} \，b_ { 010} \，b_ {110} \，b_ {001} \，b_ {101} \，b_ {011} \，b_ {111} $（交换$ z $和$ x $）
将输出转换为$ b_ {001} \，b_ {000} \，b_ {011} \，b_ {010} \，b_ {101} \，b_ {100} \，b_ {111} \，b_ {110} $（互补$ x $）
将输出转换为$ b_ {010} \，b_ {011} \，b_ {000} \，b_ {001} \，b_ {110} \，b_ {111} \，b_ {100} \，b_ {101} $（与$ y $互补）
将输出转换为$ b_ {100} \，b_ {101} \，b_ {110} \，b_ {111} \，b_ {000} \，b_ {001} \ ，b_ {010} \，b_ {011} $（互补$ z $）
我们首先得到
00001111 = g0，并排除00110011，01010101，10101010，11001100，11110000;然后得到00010111 = g1，并排除00101011，01001101，01110001，10001110，10110010，11010100，11101000;等等。最终只有6个班级。
评论
$ \ begingroup $
谢谢！您是否知道源自或解释这四种可能功能的来源？我可以在这里找到奇偶校验功能，在这里可以找到多数功能，但是我找不到关于选择和最后一个功能的任何信息。并且“选择，用于...，$ f_ {2} $ SHA-1”不应该是“选择，用于...，$ f_ {1} $ SHA-1”吗？
$ \ endgroup $
–Cartman123
16年11月6日在19:06
$ \ begingroup $
您提到他们的任何输入都会影响其他输入的四个组合中至少两个的输出，但是我相信，任何一个输入最多会影响三个输入中的三个，这也是一个优势。其他输入的四个组合。否则，该功能可能会被重写为一个输入，而另外两个输入的不平衡或线性功能则被异或。 （我不确定，但是我想这就是为什么SHA-2不使用奇偶校验的原因）。
$ \ endgroup $
–卡巴斯德
16年11月6日在21:28
$ \ begingroup $
MD5的$ f_4 = C \ oplus（B \ lor \ lnot D）$与Toffoli门的第三输出$ C \ oplus（B \ land A）$类似
$ \ endgroup $
– Nayuki
16年11月7日在6:53
$ \ begingroup $
您能否详细说明如何聚合相同的函数，只剩下$ 6 $类？那是我不明白的最后一件事。
$ \ endgroup $
–Cartman123
16年11月8日在18:35