SHA-2的时空复杂度

Question

我想知道SHA-2的时空复杂性是什么。我试着环顾四周，没有得到一个直截了当的答案。有人能帮我吗？非常感谢！

Answer 1

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

根据给出的这里算法的描述，主要步骤如下：

1. 初始化h1,..,h8 (第一个8素数2..19的平方根的分数部分的第一个32位)。
2. 初始化k1,...,k64 (第一个64素数2..311的立方体根的分数部分的第一个32位)。

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

1. 将消息分解为512位部件，并对每个512位部件执行以下操作： 3.1在1536迭代中使用固定的位数和算术运算来计算48位数。在中间可以使用几个临时变量。 3.设置额外的8变量a1,...,a8等于h1,...,h8 3.通过使用固定数量的变量并执行固定数量的按位运算和算术操作，在循环a1,...,a8次数中继续更新64。 将a1,...,a8添加到h1,...,h8中
2. 级联h1,...,h8。

如上所述，1)和2)的时间和空间复杂性是O(1)。然后，对于每一个孤立的步骤，从4.1)到4.4)，它们都是固定的。唯一不是常量的东西是输入消息的大小，因此整个4)的时间复杂度是O(n)。空间复杂度是O(1)，因为总是有固定数量的临时变量使用，并且每次迭代都可以重复使用一个1536位变量。

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

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