当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。関数とは、ある変数に依存して決まる値あるいはその対応を表す式のことである。簡単にいうと、何か数値を代入すると、その数値に対応した何らかの数値が出力される数式のことである。y=x+1という関数があった場合、xに3を代入(入力)すれば、yは4になる(出力)。このように入力と出力の関係を示す式のことを関数という。この辺りの話はプログラミングをやってる人ならすでに知っているだろう。数学をやっている人なら、写像といったほうがわかりやすいだろうか置換とは、あるものを別のものに置き換えることである。関数の場合は重複を許されるが、置換は重複を許されない。置換は一対一対応の写像である。m個の要素がある集合から、n個の要素がある集合への変換に関数を使うとする。このときの関数となりうる変換の数は、mn個になる。n個の要素がある集合から、n個の要素がある集合への変換に置換を使うとする(置換の場合は重複を許さないので、同数への写像でしかありえない)。このときの関数となりうる変換の数は、n!個になる。nビット列(n桁あるという意味)は2n通りある。(0,0,...,0,0),...,(0,1,...,0,1),...,(1,1,...,1,1)の総数が2n通りあるということである。{0,1}nという集合から{0,1}nという集合への関数fを考える。この関数の数は、2n通りから2n通りへの関数なので、次のように計算できる。{0,1}nという集合から{0,1}nという集合への置換πを考える。この関数の数は、2n通りから2n通りへの置換なので、次のように計算できる。次の図をじっくり見て、理解しておいて欲しい。置換の総数が(2n)!通りあるというところが最初はピンと来ないかもしれない。n個の集合からn個の集合への置換の総数はn!通りあるとすでに説明した。このnのところに2nを代入したと考えればよい。次のような選択平文攻撃を考える。敵(無限の能力は持たないが、実は選択平文攻撃以外にももっと色々な攻撃ができる)はENCnまたはPnからランダムに選ばれた置換πに平文miを送り、ci=π(mi)を受け取ることができる。このような敵が現実的な時間において、ENCnとPnを識別することが困難であるとき、ENCnを長さnの疑似ランダム置換族という。わかりやすく解説してみる。仮に、πがランダム置換から持ってきたものであれば、そのπで暗号化されたものはランダム値である。ENCnからπ'を持ってきたとする。これは上記の定義を満たすPnの部分集合である。このπ'を使ったとしても、敵にとってそのπ'がPnから持ってきたのかENCnから持ってきたのかわからななければ、即ちそれがランダム値に見えてしまえば、πは疑似ランダム置換で、ENCnは疑似ランダム置換族ということである。敵にランダム値を使っているように思わせることができれば(擬似ランダム値でもランダム値のように思う)、セーフということになる。逆に、ランダムではなくなんらかの偏りがあると敵が判断できてしまったら、ダメということになる。疑似ランダム置換を厳密に書くと次のようになる。置換のときと同様にしてランダム置換族と疑似ランダム置換族を定義できる。[定義]集合{0,1}nから集合{0,1}nへのすべての関数の集合を、Rn={{0,1}SUP{n}:上のすべての関数}と書き、長さnのランダム関数族と呼ぶ。[定義]FnをRnの部分集合とする。任意の敵(無限の能力はない)が、FnとRnを識別することが困難なとき、Fnを長さnの疑似ランダム関数族と呼ぶ。直観的に考えると、ランダム関数とは与えられた入力に対して、その出力が決定されるものの、その出力はどんな情報からも推測できないランダムな値であるような関数のことである。直観的にいうと、ランダム関数から出力された値は完全なランダム値になっていて、何を入力したかは推測できないということである。このような関数が現実に存在するかどうかは別として、そのような関数の振る舞いをブロック暗号の性質に見立ててて、利用モードの安全性を議論したりする。簡単にランダム(乱数)と言葉に出していますが、ランダム値を実現することは実際には非常に困難である。†[定義]キー関数の族l1,l2が与えられた。どちらが選ばれているかわからないとき、Fは擬似ランダム関数ということである。[定義]キーハッシュ関数の族l:整数、l>l1H:={Hk}k∈K[定義]εuhのとき、εuhという。Hはハッシュ関数のεuhユニバーサル族と仮定する。[定義]関数族F':={F'k,s}(k,s)∈K×Sハッシュ関数を使うと大きい定義域を持った擬似ランダム関数を作れる。l>l1だから、最初の擬似ランダム関数から比べて定義域が大きくなったことがわかる。その作った関数が本当に擬似ランダム関数かどうかを証明しなければならない。†[定理]PRF,UHの下で、「F:擬似ランダム関数」⇒「F':擬似ランダム関数」[方針]次の確率の差の絶対値がnegならば、証明できたことになる。前半の確率がGame0、後半の確率がGame3である。[証明]∀A:Adversary[1]Game0Aはオラクルに投げているつもり。Game1DOとは、オラクルOにアクセスできる識別子Dである。Game2Aはwを投げると、Hを使ってxが計算される。すると、xに対応するyがAに返される。Else文にあるように、すでに前に出たxと同じ値なら、巨大なテーブルからyを持ってくる。出ていないxなら、普通にランダムな値を持ってくる。Game3F:xi=xj(∃i≠∃j)のときのイベントとする。「S2∧¬F」⇔「S3∧¬F」より、|Pr[S2]-Pr[S3]|≦Pr[F]が成り立つ。(Q.E.D.)[考察]Fが起きないときのk,r,Y1,...,Yqを考える。(a)i=0のとき、自明(b)i=1のとき、成り立つと仮定。wi,x:同じ方法を決定Fが起きなければ、yiも同じつまり、b=A(r,Y1,...,Yq)は同じ。「P:PRP族」⇒「P:PRF族」を示したい。そこで、まずRF(ランダム関数)とRP(ランダム置換)を識別する問題を考える。Game0[2]Game1Aにとっての目的は、置換か普通の関数かを区別したい。そのためには値の衝突を見るしかない。ここで、オラクルが単にランダムにとってきてしまうとどこかでAにばれてしまう。Else文で前に出たランダム値が来たら別のものを取り直すようにしている。Game1Pr[S1]=Pr[S0][3]Game2オラクルはダイレクトに返しているだけ。Game2ここで、次のようにFを定義する。i≠jr,Y1,...,YqはGame1とGame2を同一視できる。同じランダムテープを使っている。各ランダムテープの値までもがぴったり一致している。これは、ランダム値の全体の集合が一致するということより強いことがいえているわけだ。∴|Pr[S1]-Pr[S2|≦Pr[F]後は、Pr[F]を細かく見ていけばよい。イベントFは、q個の要素から2つのペアを取り出して、それが一致していない組み合わせが起こるというのが前提である。これは、q個のボールを同時に2個取り出す組み合わせ、即ちqC2通りあると考えればよい。2-l;negとする。「P:PRP族」⇒「P:PRF族」[証明]Pに対する効率的なアドバーサリーAをfixして、PRF-advantageがnegであることを示す。このεprfがnegであることを示す。RPの議論より次が成り立つ。これは、Aにとって、πl、Γl,lから選ばれているかわからないということ。よって、ゆえに、negで押さえられる。†[定義]F:={Fs}s∈S:擬似ランダム関数の族Fs:{0,1}l→{0,1}l[定義]H:={Hk}k∈K:lビット長のハッシュ関数のεaxu-almost-XOR-universal族Hk:{0,1}l→{0,1}lとする。ここで、εaxuはnegと仮定する。†[定理]LRC⇒PRP[方針]「LRC⇒PRF」(示したいもの)「PRF⇒PRP」(ここで証明済み)を使う。Game1|Pr[S0-Pr[S1|=εprfオラクルマシンDOを次のように設定する。Game2|Pr[S1-Pr[S2|=ε'prfオラクルマシンD'Oを次のように設定する。オラクルマシン~DOを次のように設定する。「|Pr[S1-Pr[S2|=ε'prf;neg」を証明する。Game3、という2つのイベントを考える。∵まずlビットだからl列の0...0〜1...1を考える。その総数は2l通りある。最初にxiを決定する確率は1/2lとなる。その確率で、繰り返し数qからひとつ選択する。xjはひとつ減らしたq-1からひとつ選択することになる。結局合計で、q×(q-1)×2lとなる。q個から2個自由な組合わせで取り出す(重複はなし)総数はqC2通りある。このようにコンビネーションで考えてもよい。