密码散列函数的时间复杂度是多少？
问题描述：
让我们说MD5或SHA-1？这两者的时间复杂度是多少？我试图在互联网上找到它，但它非常有限，我得到的是它们都是O（n）。任何人都可以进一步启发我吗？也许给我一个最坏的情况和最好的情况下？密码散列函数的时间复杂度是多少？
答
的MD5和SHA-1算法 - 这两者都是不加密安全，绝不应该用更多的 - 是基于Merkle-Damgard construction。这意味着它们是由
- 开头的块加密这需要称为比特的输入固定宽度块，并输出相同的尺寸的位的固定宽度的块内置，
- 填充所述输入了使用cryptographically secure padding scheme，然后
- 将块密码迭代地应用于输入的一些位数的组合，加上初始化值或前一个块密码的输出，将其分配给块大小的几倍。
由于分组密码在固定大小的位块上工作，因此运行它的时间复杂度为O（1）。该块密码总共有Θ（n）个应用程序（输入被拆分成固定大小的块，因此这些块有Θ（n）），并且计算填充位的代价可能是O（ 1）但可能是O（n）。总的来说，这意味着计算这些散列函数的运行时间是Θ（n），这是有意义的，因为每个位至少被访问一次，并且每位完成的工作是恒定的。
分组密码通常以一种方式实现，使得它们可以在任何输入组合的位上运行完全相同的时间量，或者至少非常接近相同的时间量来尝试创建它们抵抗timing attacks，其中计算分组密码所需的时间量用于窃取一些比特。因此，如果这些哈希函数花费不同的时间在不同的相同大小的输入上完成，那将是非常罕见的。因此，独立于运行时间为Θ（n）的事实，您不应该期望在挂钟运行时看到很多变化。