加密散列函数的时间复杂度是多少

Question

比方说MD5还是SHA-1？这两者的时间复杂性是多少？我试着在互联网上找到它，但它非常有限，我得到的只是它们都是O(n)。有人能进一步启发我吗？也许给我一个最坏的情况和最好的情况？

Answer 1

MD5和SHA-1算法都基于Merkle-Damgard构造，这两种算法在密码方面都不安全，永远不应该再使用。这意味着它们是由构建的

1. 从分组密码开始，该分组密码将固定宽度的比特块作为输入并输出相同大小的固定宽度的块
2. 使用加密安全填充方案将输入填充到块大小的某个倍数，然后
3. 迭代地将分组密码应用于输入的某个比特数加上初始化值或先前分组密码的输出的组合

因为分组密码在固定大小的比特块上工作，所以运行它的时间复杂度是O(1)。总共有Θ(n) 该分组密码的应用程序(输入被划分为固定大小的块，因此存在这些块的Θ(n))，并且计算填充比特的成本可能是O(1)，但可能是O。总的来说，这意味着计算这些哈希函数的运行时是Θ(n) ，这是有道理的，因为每个比特至少被访问一次，并且每个比特所做的工作是恒定的。

块密码的实现方式通常会使它们在任何比特的输入组合上运行所需的时间完全相同，或者至少需要非常接近相同的时间，以试图使它们抵抗定时攻击，在定时攻击中，计算块密码所需的时间被用来窃取一些比特。因此，如果这些散列函数在相同大小的不同输入上花费不同的时间来完成，那将是非常不寻常的。因此，独立于运行时是Θ(n) ，您不应该期望在挂钟运行时看到太多变化。