チェイン化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/11 06:11 UTC 版)
使用する記憶域の量を削減するために、平文とハッシュ値とのペアを「チェイン化」することを考える。 ここで、あるハッシュ値 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 } この処理を何度か繰り返すと、平文1、ハッシュ値1、平文2、ハッシュ値2、…… という、平文とハッシュ値のペアから成る「チェイン（鎖）」ができあがる。 続いて、このようなチェインを大量に作成する。作成したチェインの集まりをテーブルと呼ぶ。各チェインの長さを m とすると、テーブルの内容は次のようになる。 [ P i C i P i + 1 C i + 1 P i + 2 ⋯ C i + m − 1 P j C j P j + 1 C j + 1 P j + 2 ⋯ C j + m − 1 P k C k P k + 1 C k + 1 P k + 2 ⋯ C k + m − 1 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ] {\displaystyle \left[{\begin{array}{ccccccc}P_{i}&C_{i}&P_{i+1}&C_{i+1}&P_{i+2}&\cdots &C_{i+m-1}\\P_{j}&C_{j}&P_{j+1}&C_{j+1}&P_{j+2}&\cdots &C_{j+m-1}\\P_{k}&C_{k}&P_{k+1}&C_{k+1}&P_{k+2}&\cdots &C_{k+m-1}\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\\end{array}}\right]} ここで、各チェインの先頭になる平文 Pi, Pj, Pk, …… は、他のチェインの内容と重複しないように適当に選択する。チェインの長さは任意であり、また各チェインの長さが異なっていてもよい。ここでは説明のため、全てのチェインの長さが同じとして考える。 チェインを作成したら、チェインの先頭にある平文 Pi, Pj, Pk, …… と、チェインの末尾にあるハッシュ値 Ci+m-1, Cj+m-1, Ck+m-1, …… だけを結果として記録しておく（記憶域を削減する）。 ハッシュ値から平文を得るには、パスワードが知りたいハッシュ値 Cx を還元関数とハッシュ関数に次々に通していき、その都度 Ci+m-1, Cj+m-1, Ck+m-1, …… と比較を行えばよい。もし一致するものが見つかれば、対応する Pi, Pj, Pk, …… からチェインを復元する。 この方法を使うと、記録しておく平文とハッシュ値の個数は、チェインの長さを m とすれば、最初の方法の 1⁄m になる。
※この「チェイン化」の解説は、「レインボーテーブル」の解説の一部です。
「チェイン化」を含む「レインボーテーブル」の記事については、「レインボーテーブル」の概要を参照ください。
- チェイン化のページへのリンク
