algorithm - SHA256 レインボー テーブルの縮小アルゴリズム

Question

レインボー テーブルを使用して sha256 をクラッキングするプロジェクトを行っています。8 桁の英数字シーケンスを攻撃しようとしています。レインボーテーブルがどのように機能し、チェーンがどのように形成され、保存されることになっているのかを正確に理解しています. ただし、チェーンを形成するための還元関数を取得する方法がわかりません。私はググって何時間も自分で考えましたが、結果はありませんでした. では、チェーンの適切な縮小関数とは何ですか? また、8 桁の英数字シーケンスすべてをカバーしていることをどのように証明できますか?

Answer 1

8 桁の異なるシーケンスが 10^9 あります。SHA256 ハッシュ値の最初の 30 ビットには、1073741824 の可能な値があります。したがって、1 つの合理的なアプローチは、これらの 30 ビットを抽出し、その数値モジュロ 10^9 をリダクション関数として使用することです。

R(hash) = hash[0:30] % 10^9

これが実際にすべての 8 桁のシーケンスをカバーすることはほとんどありませんが、実際には、SHA256 の想定される「ランダム性」特性により、十分に十分なはずです。ただし、係数が原因で、数値 <= 2^30 - 10^9 への小さな偏りがあります。