密碼散列函數的時間複雜度是多少？

Question

讓我們說MD5或SHA-1？這兩者的時間複雜度是多少？我試圖在互聯網上找到它，但它非常有限，我得到的是它們都是O（n）。任何人都可以進一步啓發我嗎？也許給我一個最壞的情況和最好的情況下？

Answer 1

的MD5和SHA-1算法 - 這兩者都是不加密安全，絕不應該用更多的 - 是基於Merkle-Damgard construction。這意味着它們是由

1. 開頭的塊加密這需要稱爲比特的輸入固定寬度塊，並輸出相同的尺寸的位的固定寬度的塊內置，
2. 填充所述輸入了使用cryptographically secure padding scheme，然後
3. 將塊密碼迭代地應用於輸入的一些位數的組合，加上初始化值或前一個塊密碼的輸出，將其分配給塊大小的幾倍。

由於分組密碼在固定大小的位塊上工作，因此運行它的時間複雜度爲O（1）。該塊密碼總共有Θ（n）個應用程序（輸入被拆分成固定大小的塊，因此這些塊有Θ（n）），並且計算填充位的代價可能是O（ 1）但可能是O（n）。總的來說，這意味着計算這些散列函數的運行時間是Θ（n），這是有意義的，因爲每個位至少被訪問一次，並且每位完成的工作是恆定的。

分組密碼通常以一種方式實現，使得它們可以在任何輸入組合的位上運行完全相同的時間量，或者至少非常接近相同的時間量來嘗試創建它們抵抗timing attacks，其中計算分組密碼所需的時間量用於竊取一些比特。因此，如果這些哈希函數花費不同的時間在不同的相同大小的輸入上完成，那將是非常罕見的。因此，獨立於運行時間爲Θ（n）的事實，您不應該期望在掛鐘運行時看到很多變化。