多個彩虹表及其成功機率
我試圖了解使用彩虹表找到未知密鑰的成功機率的計算。
基本上，我有一個目標成功機率，一個已知大小的鍵空間 $ N $ 並想導出必要的建表參數：鏈數 $ m $ ，以及每條鏈的長度 $ t $ ，以及可能的表數 $ l $ （見下文）。
Oechslin的原始論文給出了單次的成功機率 $ m \times t $ 用於在鍵空間中查找鍵的表 $ N $ 鍵為
$$ P_{table} = 1 - \prod_{i=1}^{t}\left(1 - \frac{m_i}{N}\right) $$ 和 $ m_i $ 遞歸定義為 $ m_1 = m $ 和 $ m_{n+1} = N\left(1-e^{\frac{-m_n}{N}}\right) $ .
論文中的附錄給出了這個公式的解釋，我基本上可以遵循。然而，隨著 $ m_i $ 像上面定義的那樣，我看不出如何推導出參數 $ m, t $ 除了只評估函式，這在計算上是相當昂貴的。 這些 文章表明，一個只是修復 $ m $ 到可用記憶體量，然後擴展 $ t $ 達到目標成功機率。這篇文章連結到一篇討論這個問題的論文，但據我所知，假設是完美的表格，計算並沒有變得更簡單。
有人認為，彩虹表與多個 Hellmann 表（每個使用不同的歸約函式）具有相似的成功機率，總計與單個彩虹表相同的大小。但是，我在任何地方都找不到這種說法的證據。
此外，在 Oechslin 論文的第 4.3 節中，使用多個彩虹表來獲得比使用單個表更高的成功機率。
- 這些多個彩虹表有什麼不同？
- 使用多個表與僅建構一個更大的表有何不同？
- 使用多個彩虹表如何增加成功機率？
- 這些多個彩虹表有什麼不同？
它們使用不同的（組）歸約函式。
- 使用多個表與僅建構一個更大的表有何不同？
使用不同的歸約函式，在 $ i $ 兩個表之間的第列不會導致其餘鏈合併，而在單個表中會。缺點是您需要分別在每個表中查找，因此查找成本更高。
- 使用多個彩虹表如何增加成功機率？
假設你有 $ l $ 大小表 $ m \times t $ .
- 與單個大小的表相比 $ m \times t $ 你顯然會得到更多的報導。
- 與單個大小的表相比 $ lm \times t $ 你有更少的碰撞（由於上述避免鏈合併的點）。
- 與單個大小的表相比 $ m \times lt $ 你有更快的查找： $ \operatorname{O}(lt^2) $ 代替 $ \operatorname{O}(l^2t^2) $ ，加上更少的誤報。並且更少的合併。
如果您將其與單個無合併大小表進行比較 $ lm \times t $ 您需要花費更少的精力來計算它，因為您遇到的合併更少。對於高覆蓋率目標，可能無法生成單個無合併表，因為沒有足夠的非合併鏈來達到它（另見 Oechslin 論文的第 5 節）。