反轉 DJB2 雜湊
我有一些空閒時間，周圍有幾百個 DJB2 散列值。我想我會嘗試做一些“有用”的事情並反轉 DJB2，這樣我就可以計算雜湊的明文（它早就失去了，這是一個經常令人遺憾的事實）。
對於那些不知道的人，DJB2 是這樣實現的：（C#）
public int Djb2(string text) { int r = 5381; foreach (char c in text) { r = (r * 33) + (int)c; } return r; }文本是一串 ASCII 字元，所以 DJB2 有很多衝突，我對此非常了解。幸運的是，我擁有的明文具有允許我使用啟發式過濾的特性，因此誤報應該不是什麼大問題 :)
我的算法本質上是這樣的，加上一些遞歸控制（虛擬碼）：
reverse(hash): y = hash mod 33 for c in [65, 120]: if c mod 33 == y: print reverse((hash - c) / 33), c換句話說，找到雜湊 / 33 的餘數。然後，對於從 65 到 120 的所有 ASCII 值，檢查值 / 33 是否具有相同的餘數。如果是，則從散列中減去它，將散列除以 33，然後繼續算法。這樣，我們只研究有希望的路徑，因為我們知道 C 的減法必須留下一個可以被 33 整除的數。
例如，以下是用於解碼簡單雜湊的算法：
- $ h = 177676 $
- $ y = h\mod{33} = 4 $
- 的價值觀 $ c $ 在哪裡 $ 4\equiv c\mod{33} $ : $ 70 $ 和 $ 103 $
- 我現在只能追求這兩個價值觀 $ c $ . （在這種情況下， $ 103 $ 或“g”是正確的）
因此，我知道我的算法可以逆轉散列過程。不幸的是，我遇到了一個討厭的問題。Djb2 將迅速溢出 的邊界
int，通常使用小到四個字元的純文字。這種溢出本質上導致r被隱式修改 $ 2^{32} $ .正常除法是行不通的。在這種情況下，我問了一個關於除法程式 SE的問題，並被告知 33 的乘法逆。不幸的是，我不需要除法運算（還），我需要一個餘數運算！事實證明這要棘手得多，我什至不確定這是否可能。
這是一個說明性範例：
- $ h = 2090289493 $ <– h 實際上是 $ 6385256691\pmod2^{32} $ 因為溢出
- $ y = h\mod{33} = 28 $ <–不正確！應該是 32
這是使用操作的算法範例 $ \Omega $ 和 $ h $ 那已經溢出了。這是我想做的，但我不知道什麼操作 $ \Omega $ 代表。
- $ h = 2090289493 $
- $ y = h\ \Omega\ {33} = 32 $
- 的價值觀 $ c $ 在哪裡 $ 32\equiv c\mod{33} $ : $ 65 $ 和 $ 98 $
- 我現在只能追求這兩個價值觀 $ c $ .
我是否在反轉 DJB2 的正確軌道上（可以反轉嗎？）？是否有某種方法可以找到已被修改的大量數字的其餘部分 $ 2^{32} $ ?
我是否在反轉 DJB2 的正確軌道上（可以反轉嗎？）？有什麼方法可以找到已被 232 修改的大量數字的其餘部分？
您在正確的軌道上解釋了為什麼它不能輕易倒置。
給定一個任意 $ h_i $ ，字母表中的每一個字母都會給你另一種潛力 $ h_{i-1} $ 該值在連接該字母之前。減去字母的值，然後反轉乘法。這是某個字元串的可能散列。
只需六個或七個字母就可以建構大多數數字模 $ 2^{32} $ 作為雜湊值。對於比這更長的字元串，僅通過查看該字母之前的可能散列值就無法判斷最後一個字母可能是什麼。
除非您知道字元串非常短，否則嘗試反轉函式不太可能比詳盡搜尋（例如您需要執行加密強雜湊函式）給您帶來更好的性能。即猜測與您的預期模式匹配的字元串，看看它們是否給出相同的雜湊值。