このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

ハッシュ関数

 任意の長いメッセージをある一定の短いκビット(例えば160ビット)に圧縮する関数をハッシュ関数(hash fucntion)という。圧縮した後の値をハッシュ値(ダイジェスト、メッセージダイジェスト)といい、その値のビット長のことをハッシュサイズ(ハッシュ長)という。

 単に圧縮するだけならば長い分を単に切ればよいが、それでは暗号学的に意味がない。そのためハッシュ関数は単に圧縮するだけでなく、SR/PR/CRなどの性質を満たす必要がある。

ハッシュ関数の性質

 (鍵付き)ハッシュ関数にはいくつかの安全性がある。ここで、H={hk}k∈Nをハッシュ関数族、hkをハッシュ関数とする。

h_k:\bigl{0,1\bigr}^a~\to~\bigl{0,1\bigr}^b~\,~,~\,a~>~b

 衝突は、弱い意味での衝突強い意味での衝突に分けられる。

 弱い意味での衝突なしとは、同じハッシュ値が出現しやすい、もしくはハッシュ値を予測しやすい(周期性がある)などの特徴がないことである。つまり、入力値が1ビットでも変われば、出力値は大きく変動することがいえる。

 また、強い意味での衝突なしとは、逆演算がNP完全問題に帰着されることである。つまり、一方向性を満たし、逆計算は非効率ということである。

PR

 PR(Preimage Resistance:原像計算困難性)とは、ランダムに与えられた出力yについて、hk(x)=yを満たす入力xを計算することが困難という性質である。

 通常の一方向性と同じである。

SR

 SR(Second-preimage Resistance:第2原像計算困難性)とは、ランダムに与えられたxとkが入力されたときに、h_k(x)=h_k(x')~\wedge~x~\not{=}~x'を満たす入力x'を計算するのが困難という性質である。2ndPRとも呼ばれる。

CR

 CR(Collision Resistance:衝突困難)とは、ランダムに与えられたkについて、h_k(x)=h_k(x')~\wedge~x~\not{=}~x'を満たす(x,x')を計算するのが困難であるという性質である。

[補講]CRを計算量理論に基づいて扱うときは、関数の集合で考える。

UOW

 UOW(Universal One-Way:汎用性一方向性)とは、敵Aが入力xを選び、ランダムに選ばれたkについて、h_k(x)=h_k(x')~\wedge~x~\not{=}~x'を満たすx'を計算するのが困難であるという性質である[Naor, Young 89]。

各性質の強弱

 単純なアタック(目的の結果が得られるまで、入力を選択して出力の計算を繰り返す方法。ハッシュ関数の内部構造を利用しない攻撃)の場合、各性質の問題を解くためには次の計算量が必要になる。ただし、lはハッシュ関数の出力長である。

PRO(2^l)
SRO(2^l)
CRO(2^{\frac{l}{2}})

例:MD4の場合、出力長は128ビットなので、PRとSRを解くためにはO(2^{128})、CRを解くためにはO(2^{64})の計算量が必要になる。 ◇

 よって、各性質は「PR>SR>CR」の関係にある(不等号は問題の強さの大小を意味する)。直観的には、SRはAが指定された値に対して生じる衝突ペアのもう片方の値を求めることであり、CRはAが何でもよい衝突ペアを求めることである。明らかにAにとってはCRの方が計算が簡単なので、SRはCRより難しい問題である。

 また、「UOW>CR」の関係にある。直観的に考えると、CRではハッシュの衝突のあるようなペアをひとつでも出力できればよいだけである。一方、UOWの場合はAが最初にチャレンジャーにxを投げる。その後でチャレンジャーがAにkを投げている。つまり、CRよりチャレンジャーにとって有利な状況である。よって、UOWはCRより難しい問題である。

各性質・問題・仮定

 PR/SR/CR/UOWの各性質を問題として捉えると次のようになる(チャレンジャーが与える情報から、敵Aが問題の解を求めるという構図)。

 簡単な問題が解けないという仮定は、難しい問題が解けないという仮定より、仮定が強い。つまり、Aにとって容易な問題に対して、耐性を持つようなハッシュ関数の存在を仮定するということは、仮定が強いことになる。よって、CRHFの存在仮定とUOWHFの存在仮定を比較した場合、UOWHFの存在仮定の方が弱い仮定になる。

 以上の考察より、仮定の強弱は次のようになる(不等号は仮定の大きさを意味する)。

PRHFの存在仮定<SRHFの存在仮定<CRHFの存在仮定、UOWHFの存在仮定<CRHFの存在仮定

 実際に最初にCRHFの存在仮定で安全性証明が付けられてから、後でより弱い仮定であるUOWHFの存在仮定で安全性証明を付けられる例が多い。

[補講]例えば、「CRHFの存在仮定」を「CR仮定」などと省略されることも多い。 ◇

ブロック暗号とハッシュ関数の比較

ブロック暗号Feistel構造繰り返し回数が決まっている
ハッシュ関数MD変換入力の長さに依存

 ブロック暗号の場合は鍵をXORすると、出力値をでたらめにできる。一方、ハッシュ関数の場合は入力を鍵とすると出力値をでたらめにできるわけだ。

参考文献