1000 個の SHA1 ダイジェストとそれに対応するパスワード (それぞれ 24 ビットまたは 6 桁の 16 進数) が与えられる割り当てを実装しています。ディスク上に<2MBのレインボーテーブルを構築する必要があり、Javaでは、チェーンの長さが192を超えると検索プロセスが遅くなりすぎることがわかります。
要件は、このレインボー テーブルが少なくとも 45% (または 450) のハッシュを解決し、パスワードを返す必要があることです。リダクション関数は単純です - ハッシュから最上位の 32 ビット (d0、d1、d2 としましょう) を取得し、チェーンの現在の長さ (i は 0 から 191 になります) を d0 のみに追加します (以下のように)。 :
d0 = (d0+i)%256 //8bits
d1 = d1%256 //8bits
d2 = d2%256 //8bits
コード (ハッシュとリデュース) 関数が正しいと確信しています。しかし、この方法では、対応するパスワードに対して約 250 個のハッシュ (25% の精度) しか解決できません。
チェーンの数を増やすと、解決されたハッシュの対応する数の利益が減少することがわかります。チェーンの数を 2 倍にしても精度は 2 倍にはなりませんが、レインボー テーブルのサイズは既に 2MB を超えています (8MB のようです)。
最初の単語については、0 から始めて (全範囲は 0 から 2^24 になります)、1 ずつ増やしてみました。または、この範囲の間でランダムにしようとしました。レインボー テーブルにはループがなく、リダクション関数でいくつかの衝突が発生したとしても (リダクション関数が上記のように異なるのと同じ深さで)、エンドポイントが既にテーブルにあるチェーンは受け入れません。
精度を 45% に上げるために私ができることについてアドバイスをいただければ幸いです。