沙-3最大零点数(填充)

Question

在消息中的输入填充处附加的零的最大数量是多少？这方面的信息必须有多大？

Answer 1

让我们从顶部开始，以FIPS 202为参考，向下工作。请注意，KECCAK文件使用了一种稍微不同的符号(!)。

\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M | 01, 224)

\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M | 01, 256)

\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M | 01, 384)

\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024] (M | 01, 512)

对此的解释是：

在每种情况下，容量都是摘要长度(即c = 2 \cdot d )的两倍，因此对\operatorname{KECCAK}[c]的输入N是附加后缀的消息，即N = M | 01。

现在也给出了

\operatorname{KECCAK}[c] = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600 – c]。

其中\operatorname{SPONGE}被定义为\operatorname{SPONGE}[f, pad, r]。这意味着可以将r = 1600 - c重写为r = 1600 - 2d。

这是我们在第四章:海绵结构所需要的信息。

填充规则pad是生成填充的函数，即具有适当长度的字符串以附加到另一个字符串。通常，给定一个正整数x和一个非负整数m，输出\operatorname{pad}(x, m)是一个字符串，该字符串的属性是m + \operatorname{len}(\operatorname{pad}(x, m))是x的正倍数。在海绵结构中，x = r和m = \operatorname{len}(N)，这样就可以将填充的输入字符串划分为一个r-bit字符串序列。Sec的算法9。5.1为KECCAK函数以及SHA-3函数指定填充规则。

这里，N是Keccak / SHA3的输入字符串，因此m是输入字符串的长度(以位为单位)。

太棒了，我们现在终于可以看看\operatorname{pad10*1}的定义了：

在海绵结构中，x = r和m = \operatorname{len}(N)

1. 让j = (– m – 2) \bmod x。
2. 返回P = 1 | 0^j | 1。

负模计算可能有点混乱，但很明显，无论什么情况，j的最大值以及零的个数都是x - 1或r - 1作为x = r。这是因为输入长度m可以有任何非负值.对于海绵来说，这同样适用于\operatorname{KECCAK}[c]，因此也适用于SHA3。

现在是m = \operatorname{len}(N)但是N = M|01。换句话说，输入m是消息长度--比如l -+两位。这意味着j = (– m – 2) \bmod r = (– (l + 2) – 2) \bmod r = (–l - 2) – 2) \bmod r = -l - 4 \bmod r。对于l = N \cdot r - 3，将达到这个最大值。这是一种预期；如果填充的开销最小为4位，那么一条比r短三位的消息将需要最大的填充，因为填充将溢出到下一个块。

SHA3-224的意思是r = 1600 - 448 = 1152，所以对于N \cdot 1152 - 3，达到了最大的零个数，这将是r - 1 = 1151的。

让我们检查一下N = 1：\operatorname{len}(\{0,1\}^{1149}|01|1|0^{1151}|1) = 1149 + 1151 + 4 = 2304 = 2 \cdot 1152。因此，这确实导致了两倍于r的速度。

通常哈希算法的输入不是以位为单位，而是以8位字节为单位。在这种情况下，输入将是N \cdot r，其最大数目为零，当然，8 - 4 =4位更小。零字节的数量当然是r / 8 - 2字节。

让我们再次使用SHA3-224验证这一点。第一个r字节块就是消息，最后一个r字节块将由十六进制中的06 | 00^{142} | 80组成。这似乎很奇怪，但这是因为NIST使用的是小字节和翻转位顺序(填充区中最左边的低阶位，而字节中的最右位，即位b_7在右边)。