レインボーテーブル
使用する記憶域の量を削減するために、平文とハッシュ値とのペアを「チェイン化」することを考える。
ここで、あるハッシュ値 Ci を種として、次のターゲットとなる平文を適当に選ぶ関数 R を考える。ここで、関数 R には、出力が平文の候補として正当であること(例えば、パスワードが英数字しか受け付けないならば、常に英数字だけからなる文字列を出力すること)と、副作用がないという条件を満たせば、どんな関数を使用してもよい。このハッシュ値から平文候補となる値を生成する関数 R を「還元関数」(reduction function) と呼ぶ。
ハッシュ関数を H とすると、適当に選んだ最初の平文 Pi から、Pi をハッシュ関数に通した値 Ci 、次のターゲットとなる平文 Pi+1 を得るという処理の流れは次のようになる。
P i → H ( P i ) C i → R ( C i ) P i + 1 → H ( P i + 1 ) ⋯ {\displaystyle P_{i}~{\xrightarrow {H(P_{i})}}~C_{i}~{\xrightarrow {R(C_{i})}}~P_{i+1}~{\xrightarrow {H(P_{i+1})}}~\cdots }