如果您知道函式並且知道它對另一個已知函式的輸出，需要多少次計算才能計算出輸入？
我沒有密碼學背景，所以如果這個問題有點基本或定義不明確，請原諒。我正在嘗試使用微控制器建構一個電路，該微控制器實現使用者輸入的任意數字的雜湊函式。我想讓這個人能夠從電路能夠容納的一小部分雜湊函式中進行選擇，例如 SHA-2、MD5 等。
我想知道的是，如果某人確切地知道他們使用什麼雜湊算法並且他們知道輸出，那麼弄清楚他們的輸入是多麼“容易”，其中“容易”是指計算的數量將如何用輸入的位來計算輸入的比例？線性？成指數的？是否有一些通用方程或指南來計算不依賴於雜湊函式本身的最大計算次數（基於輸入的數量），還是總是如此？我假設通過無限計算這是可能的，但如果我錯了，請糾正我。
對於上面的問題，我假設您不知道輸入的位數，但是如果您知道輸入的位數，那麼在同樣的意義上，計算它是否會“更容易”？
最後，如果您還假設您知道當輸入的位數小於雜湊函式可以容納的位數時，這些位前面有前導零，這會改變什麼嗎？
如果有任何我遺漏的細節，請告訴我，我會嘗試重新制定。謝謝！
假設您的散列函式沒有表現出原像攻擊，也就是說，我們在這裡討論的是一個通用散列函式，它在反轉它時沒有結構上的弱點。
讓 $ F:{0,1}^*\to{0,1}^n $ 被稱為散列函式 $ n $ 位輸出。例如 $ n=128 $ 對於 MD5 和 $ n=256 $ 對於 SHA-256。此外讓 $ \mathcal M $ 將您對輸入的（部分）知識表示為隨機變數，並讓 $ d $ 是給你的輸出。
現在你需要大約
$$ \min{2^{H(\mathcal M)},2^n} $$雜湊函式的評估以找到一個 $ m $ 這樣 $ F(m)=d $ . 請注意，您無法輕易確定是否 $ m $ 您發現與最初用於生產的相同 $ d $ （畢竟我們要求的唯一財產 $ d $ 現在很滿意）。您最多可以做的是檢查 $ \Pr[\mathcal M=m]\neq 0 $ ，即你使用你預先獲得的知識來驗證找到的 $ m $ 實際上是可能的。 我還沒有介紹的是什麼 $ H(\cdot) $ 上述表達中的意思。它表示資訊論熵。基本上它是隨機變數不確定性的對數，因此也考慮了各個可能值的可能性。
那麼最後為什麼上面的表達是正確的呢？好吧，您希望在之後找到雜湊函式輸出的匹配項 $ 2^n $ 評估，因為每個輸出位匹配相應位的機率 $ d $ 是 $ \frac12 $ 並乘以這個 $ n $ -times，因為所有位都需要匹配。現在換個學期，如果你知道很多 $ m $ 你可以利用這個結構，只需要嘗試所有你不確定的東西。
現在您提到的兩個範例屬性可以很容易地融入上述框架：您現在知道了 $ \mathcal M $ 的“輸出”最多 $ m $ 位長，因此 $ H(\mathcal M)\leq m $ . 現在，如果您不知道這一點，您仍然可以對上限做出一些合理的估計，並且在實際的、完全猜測的攻擊中，您可能會從最短到最長進行攻擊。現在對於另一個屬性，它排除了許多不同的可能輸入，即 $ 2^l $ 在哪裡 $ l $ 是前導零的數量，因為你知道第一個 $ l $ -bits 將是 $ l $ ，它們現在已完全確定，因此您實際上只是將熵除以 $ l $ .
您在這裡描述的是攻擊密碼。加密散列函式的定義包括對原像的抵抗。如果給定 hash(x)，則應該不可能恢復 x。因此，您在此處陳述的資訊並不能幫助您恢復原像。
但是，您所涉及的是蠻力攻擊。在這種情況下，您將獲取原像 X 並執行 hash(X) 以確定 hash(X)==ExpectedHash。您對 X 可能的每個可能組合執行此操作，直到它們實際上相等。然後對每個雜湊執行此操作。
至於需要多少計算。那是熵的函式。例如，所需資訊：
- 需要多少位$$ min-max $$
- 每個字節的最大可能組合是多少
- 有沒有已知空間
是的，這個問題會成倍增加。假設我的密碼只能由 0 或 1 組成。這意味著我的密碼的任何位置都有 2 種可能的組合。然而，在密碼中添加一個額外的字元意味著現在有 4 種可能的組合，00、01、10、11。對於每個額外的字元，我添加更多的組合，形式為 2^n。對於非常大的位數，這個問題變得極端（這確實是重點）。計算的最終結果將是：
- $$ # of computations per hash function of one preimage and compare $$*$$ 2^n $$=$$ # of computations required $$
其中 n 是密碼的長度。如果您不知道密碼的長度，這個問題會更加嚴重。
你可以做的一些事情：
如果您了解有關原像的某些資訊，則可以減少所需的計算次數。在您的範例中，您提到了每個附加的 0。好吧，這可能會有所幫助，但前提是您始終知道原像的長度。在這種情況下，它沒有其他幫助（你不能確定圖像中有多少個 0，以及它們在哪裡）。您所做的只是說“位數不少於這個，而且不多”將問題減少到每個原像的一定位數。否則，您還必須嘗試從
$$ 0 $$一直到$$ 111111111…n $$. 你唯一能做的就是說，我知道原像中有這麼多位。所以只有 2^n 組合。現在從 0 開始，並從最後一位預附加 0 到第一位。這將是最好的方法。但仍最多需要前面列出的計算次數。因為您根本不知道是否預先附加了任何 0。 總而言之，是的，它可以提供幫助，但實際上只是將問題減少到一個指數。如果沒有真正聰明的東西，我認為你不能比這更低。希望這可以幫助！