security - 密码哈希函数的时间复杂度是多少？

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)，这是有道理的，因为每个位都至少被访问一次，并且每个位所做的工作是恒定的。

分组密码通常以一种方式实现，使它们在任何输入位组合上运行完全相同的时间 - 或者至少，非常接近相同的时间 - 试图使它们抵抗时序使用计算分组密码所需的时间来窃取一些位的攻击。因此，如果这些哈希函数在相同大小的不同输入上花费不同的时间来完成，那将是非常不寻常的。因此，与运行时间为 Θ(n) 的事实无关，您不应期望在挂钟运行时间中看到太多变化。