レインボーテーブル (rainbow table) は、ハッシュから平文を得るために使われるテクニックの一つである。特殊なテーブルを使用して表引きを行うことで、時間と空間のトレードオフを実現している。以降では、このテクニックの元となっているアイディアについて説明する。まず、このテクニックの発端は「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用できないか」という点にある。例えば、ある平文 "P" と、それをハッシュ化した値 "C" をテーブルに格納しておき、このテーブルを逆引きすればハッシュ値から対応する平文が得られる。ただし、この方法では、得られた平文とハッシュ値とのペアを全て記録しておく必要があり、実現には莫大な記憶領域を必要とする。使用する記憶域の量を削減するために、平文とハッシュ値とのペアを「チェイン化」することを考える。ここで、あるハッシュ値 "C" を種として、次のターゲットとなる平文を適当に選ぶ関数 "R" を考える。ここで、関数 "R" には、出力が平文の候補として正当であること(例えば、パスワードが英数字しか受け付けないのであれば、常に英数字のみからなる文字列を出力すること)と、副作用がないという条件を満たせばどんな関数を使用してもよい。この関数 "R" を「還元関数」(reduction function) と呼ぶ。ハッシュ関数を "H" とすると、適当に選んだ最初の平文 "P" から、"P" をハッシュ関数に通した値 "C" 、次のターゲットとなる平文 "P" を得るという処理の流れは次のようになる。formula_1 この処理を何度か繰り返すと、平文1、ハッシュ値1、平文2、ハッシュ値2、……という、平文とハッシュ値のペアの「チェイン」ができあがる。続いて、このようなチェインを大量に作成する。作成したチェインの集まりをテーブルと呼ぶ。各チェインの長さを "m" とすると、テーブルの内容は次のようになる。formula_2 ここで、各チェインの先頭になる平文 "P
出典:wikipedia
LINEスタンプ制作に興味がある場合は、
下記よりスタンプファクトリーのホームページをご覧ください。