バックアップTweet追加された行はこの色です。削除された行はこの色です。当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。興味がある方は[[宣伝サイト:http://s-akademeia.sakura.ne.jp/main/books/cipher/]]を参照してください。[[Amazon:https://www.amazon.co.jp/dp/4798148814/securityakade-22]]でも発売中です。短いメッセージを入力とする衝突困難な固定長圧縮関数を基に任意の長いメッセージを作ることができる。ここでは、κ+nビットのメッセージをκビットのハッシュ値に圧縮する衝突困難な固定長圧縮関数fから、任意の長いメッセージをκビットのハッシュ値に圧縮する衝突困難なハッシュ関数Hを構成する方法がある。これを''MD変換''という。メッセージの長さがnの整数倍である場合を考える。このとき、次のような仕組みで求められる。#img(http://s-akademeia.sakura.ne.jp/main/image9/md1.jpg)#img(,clear)1:まず、メッセージxをnビットごとの小ブロックに分割する。x=xSUB{1};||xSUB{2};||...||xSUB{t};ただし、|xSUB{1};|=|xSUB{2};|=...=|xSUB{t};|=nである。ここで、「||」の記号は連結、|x|はxの長さ(ビット列)を表している。2:hSUB{1}=f(0SUP{κ};||xSUB{1};)とする。ここで、0SUP{κ};は入力のビット数を調整するためのものである。3:i=2,...,tまで、次を計算する。hSUB{i}=f(hSUB{i-1};||xSUB{i};)4:hSUB{t};をHのハッシュ値とする。[#ta7b632f][定理]~fが衝突困難で、かつf(z)=0SUP{κ};となるzを求めることが困難であれば、Hは衝突困難である。[証明]#img(http://s-akademeia.sakura.ne.jp/main/image9/md2.jpg)#img(,clear)H(x)=H(x')となる衝突ペアx≠x'が見つかったと仮定する。以下、x'に関係する変数は「'」を付けて表すことにする。[1]|x|=|x'|、即ちxとx'のビット列が同じ場合H(x)=H(x')より、hSUB{t};=h'SUB{t'};また、xとx'は長さが等しいので、t=t'よって、hSUB{t};=h'SUB{t};が成り立つ。xSUB{t};=x'SUB{t};前者は前提に反するので除外。そこで、後者について考える。xSUB{t};=x'SUB{t};であると仮定する。すると、hSUB{t-1};=h'SUB{t-1};が成り立つ。xSUB{t-1};=x'SUB{t-1};また、前者は前提に反するので除外。この手続きを最後まで続ける。すると、最後はf(0SUP{κ};||xSUB{1};)=f(0SUP{κ};||x'SUB{1};)となる。xSUB{1};=x'SUB{1};ならば、fの衝突ペアが求まったことになってしまう。そこで、xSUB{1};≠x'SUB{1};と仮定する。すると、全体的にx=x'になってしまう。[2]|x|≠|x'|、即ちxとx'のビット列が違う場合ここで、|x|<|x'|と仮定しても一般性は失われない。f(0SUP{κ};||xSUB{1};)=f(h'SUB{u-1};||x'SUB{u};」というステートメントが成り立つ。(i)h'SUB{u-1};≠0SUP{κ};の場合、fの衝突ペアが見つかったことになってしまう。f(z)=0SUP{κ};0SUP{κ};の逆像の定義により、f(z)=0SUP{κ};となるzは求まらないので矛盾。よって、(i)(ii)のいずれにしてもfの衝突ペアが見つかってしまう。ゆえに、仮定が矛盾であることが示せた。したがって、H(x)=H(x')となる衝突ペアx≠x'は見つからない。[考察][2](ii)において、矛盾が発生したが、これを取り除くために、次の一般形が考え出された。[#l098202e]#img(http://s-akademeia.sakura.ne.jp/main/image9/md3.jpg)#img(,clear)[1]予備変換1:まず、メッセージxをn-1ビットごとの小ブロックに分割する。x=xSUB{1};||xSUB{2};||...||xSUB{t};とおく。ySUB{t};=xSUB{t};||0SUP{d};(パディング)とおく。3:ySUB{t+1};をdの2進表現とする。[2]主変換1:hSUB{1};=f(0SUP{κ+1};||ySUB{1};)とする。2:i=2,...,t+1まで、次の計算をする。hSUB{i};=f(hSUB{i-1};||1||ySUB{i};)3:hSUB{t+1};をHのハッシュ値とする。[#ffa12fda][定理]~HはMD変換の一般形とする。~このとき、fが衝突困難(CR)⇒Hも衝突困難(CR)である。[証明]H(x)=H(x')となる衝突ペアx≠x'が見つかったと仮定する。以下、x'に関係する変数は、「'」を付けて表すことにする。xを予備変換して得られる系列を、y=ySUB{1};||ySUB{2};||...||ySUB{t+1};とおく。同様に、x'を予備変換して得られる系列をy'とおく。予備変換の性質より、明らかにx≠x'のときy≠y'である。ここで、[[MD変換の基本形の定理:http://akademeia.info/indexx.php?MD%CA%D1%B4%B9#ta7b632f]]の[1]の証明をy,y'に適用する。すると、途中でfの衝突ペアが見つかるか、または最後に次のステートメントが成り立つ。f(0SUP{κ};||0||ySUB{1};)=f(h'SUB{u-1};||1||y'SUB{u};)しかし、入力値の真中の0と1は不一致なので、入力値の全体も不一致となる。「0SUP{κ};||0||ySUB{1};≠h'SUB{u-1};||1||y'SUB{u};」よって、fの衝突ペアが見つかったことになる。いずれにしても矛盾が生じてしまった。ゆえに、H(x)=H(x')となる衝突ペアx≠x'が見つからないことが示された。[系]~ハッシュ関数Hに衝突が見つかれば、圧縮関数fにも衝突が見つかる。[証明]上記の定理の対偶を取ればよい。[#cb620ab5]-『現代暗号の基礎数理』-ゼミ。