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

目次

宣伝

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

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

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

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

情報理論的安全性

 暗号の安全性を語るときは次の2つの点に分けて考える。

  1. アタッカー(アドバーサリーとも呼ぶ)の能力
  2. どこまでの情報漏れを許容するか

 まずアタッカーの能力としては無限の能力、有限の能力などがある。後者 の有限の能力としては多項式時間・準指数的時間・指数的時間といったレベルがある。情報理論ではコンピュータは一般的にチューリングマシンとして考えられるので、アタッカーのコンピュータの能力は多項式時間の能力まで持っているとして議論される。

 次にどこまでの情報漏れまでを許容するかということは、情報が完全に漏れた らアウトなのか、情報の一部分(1ビットなど)さえも漏れたらアウトなのかとい ったことである。

 情報理論的安全性では、理想的である計算時間(無限の能力を持つCPUと考えて もらえればよい)と記憶領域(無限の領域を持つメモリと考えてもらえればよい) の能力を持つアタッカーを考える。こうしたアタッカーに対してさえも安全で ある暗号のことが証明されたものを情報理論的に安全と呼ぶ。つまり、 「情報理論的に安全」ということは暗号における一番強力な安全性である。

 それに対して、アタッカーに無限の能力を考えない場合は、計算量的安全性と 呼ばれ、前述したようにアタッカーのレベルと許容するレベルの段階がいくつか に分かれているので、それの組合わせ分だけ安全性が存在するということになる。

 それでは、共通鍵暗号系の情報理論的安全性を定義してみる。まず平文m、鍵kに対して、暗号文cが暗号化アルゴリズムであるEを用いて、次 のように表される共通鍵暗号系を考える。

c~=~E~\(~k,m~\) ←(1)

 また平文は集合M={m1,m2,…}から、ある確率分布によって生起すると仮定し、~M(エムチルダ)によってその確率変数を表すとする。ただし、任意のm∈Mは正の確率で生起すると仮定する。

 鍵は集合K={k1,k2,…}から、ある確率分布によって生起すると仮定し、~Kに よってその確率変数を表すとする。

 そして、暗号文は(1)によって定まる集合C={c1,c2,…}上のある確率分布によ って生起し、~Cによってその確率変数を表すとする。

 これで共通鍵暗号系の情報理論的安全性の定義の準備ができた。上記の記 号を使い、定義を表記することにする。

[定義]
\forall~c~\in~C~,~\forall~m~\in~M~;~Pr~\(~\tilde{M}=m~|~\tilde{C}=c~\)~=~Pr~\(~\tilde{M}=m~\)
が成り立つとき、暗号系(~K,~M,~C)は情報理論的に安全(完全秘匿)であると いう。

 数学記号ばかりになってしまうが直観的にいうと、アタッカーが盗聴に よって暗号文を入手したとするとき、平文を解読するための情報がなんら含まれ ておらず役に立たないことを意味する。ただし、暗号が少しわかる人に言及しておくとアタッカーはあくまで盗聴だ けでありランダムオラクルモデルは使えないという仮定をしている。

情報理論的安全性の例

 例えば、暗号化アルゴリズムD:c=m+kを考えてみる。また、M={0,…,9}とK={0,…,9}が各集合上でmとkが一様分布すると仮定する。

 このとき次が成り立つ。

Pr~\(~\tilde{M}=0~\)~=~Pr~\(~\tilde{M}=1~\)~=~\cdots~=Pr~\(~\tilde{M}=9~\)~=~\frac{1}{10}

 ここでアタッカーが何らかの方法でc=1を入手したとする。これをDの式に代 入すると、1=m+kとなり、(m,k)の組み合わせは次の2通りのみになる。ここで

  1. はXOR演算(排他的論理和)であることを忘れないように。

(m,k)=(1,0),(0,1)

 つまり、c=1のときはm=2となることはないから、次が成り立つ。

Pr~\(~\tilde{M}=2~|~\tilde{C}=1~\)~=~0

 このことから、次が成り立つ。

Pr~\(~\tilde{M}=2~|~\tilde{C}=1~\)~\not=~Pr~\(~\tilde{M}=2~\)

 ゆえに、このDの暗号系は情報理論的に安全でないことが示された(反例が ひとつ提示された)。

情報理論的に安全な暗号系の鍵長と平文長の関係

[定理]
「情報理論的に安全」⇔「|K|≧|M|」

 この絶対値は、長さを意味する。例えば、100ビットの平文を暗号化したい場 合は、鍵の長さは100ビット以上必要ということである。

[証明]背理法を用いる。

 |K|≧|M|でない、すなわち|K|<|M|と仮定する。すると、ある平文m∈Mと暗号文c∈Cが存在して、次がいえる。

Dk(c)≠m (∀k∈K)

 これは、Pr(~C=c|~M=m)=0であることを意味するが、これは定義に矛盾する。

 ゆえに、|K|≧|M|となる。 □

参考文献

  • 『現代暗号の基礎数理』