algorithm - SHA-2 的空间和时间复杂度

Question

我想知道 SHA-2 的空间和时间复杂度是多少。我试着环顾四周，并没有真正得到直接的答案。谁能帮我吗？非常感谢！

Answer 1

例如，让我们考虑SHA-256。

根据此处给出的算法描述，主要步骤是：

1. 初始化h1,..,h8（第一个素数32平方根的小数部分的第一位）。82..19
2. 初始化k1,...,k64（第一个素数32的立方根的小数部分的第一位）。642..311

由于它们的数量是固定的，因此初始化所需的时间复杂度和空间复杂度是恒定的。

3. 将消息分成512位部分，对每个512位部分执行以下操作：

   3.1通过使用恒定数量的按位和算术运算来计算迭代中的位数1536。48可以在两者之间使用几个临时变量。

   3.2 设置附加8变量a1,...,a8等于h1,...,h8

   3.3通过使用固定数量的变量并执行固定数量的按位和算术运算，a1,...,a8在循环时间内保持更新。64

   3.4 添加a1,...,a8到h1,...,h8

4. 连接h1,...,h8。

如上所见，1) 和 2) 的时间和空间复杂度为 O(1)。然后，对于从 4.1) 到 4.4) 的每个独立步骤，它们也是固定的。唯一不恒定的是输入消息的大小，因此 4) 作为一个整体的时间复杂度是 O(n)。空间复杂度为 O(1)，因为总是使用固定数量的临时变量，并且15363) 中使用的一个位变量可以在每次迭代中重复使用。

其他基于SHA-2的算法（如SHA-512或SHA-384）具有相同的复杂性，因为它们的不同主要在于 3.3 中的迭代次数或字长。

其中，时间复杂度为O(n)，空间复杂度为O(1)。