4.1 暗号解読概要

(情報理論的に)安全な暗号とは攻撃者が暗号文をなんらかの方法で得た場合と, そうでない場合で攻撃者が得られる平文に関する情報量が等しいような暗号である．

例

平文mの候補が 0 or 1 のとき，いずれか1つを暗号化して封筒に入れる. このとき暗号文cは 0 or 1とする.

封筒を開ける前にmを当てる確率,
平文mがiである確率を Pr(m=i) とする.
m=0 である確率 Pr(m=0)
m=1 である確率 Pr(m=1)
mがランダムに選ばれているならば Pr(m=0)=Pr(m=1)=1/2であろう.
次に封筒を開けて暗号文cを見ることができ,c=jであったとする．

c=0 or c=1
このときm=iである条件付き確率をPr(m=i|c=j)とする.
c=0のとき,
m=0 である条件付き確率 Pr(m=0|c=0),
m=1 である条件付き確率 Pr(m=1|c=0).
c=1のとき,
m=0 である条件付き確率 Pr(m=0|c=1),
m=1 である条件付き確率 Pr(m=1|c=1).
もし
Pr(m=i|c=j)=Pr(m=i)
注)シャノンによる． 情報量で表現するとH(m=i|c=j)=H(m=i).

であれば,すなわちこの例の場合に
Pr(m=0|c=0)=Pr(m=0|c=1)=Pr(m=0)=1/2
Pr(m=1|c=0)=Pr(m=1|c=1)=Pr(m=1)=1/2

を満たすような暗号方式が存在するならば，この暗号方式は攻撃者が 暗号文cを傍受して, 知ったとしても平文mに関する情報を何ら得られていない． すなわち，このような条件を満たす暗号方式を攻撃する最良の方法は全数探索である. しかしながらこのような暗号方式は実用的ではないことが知られている． 平文より長い鍵を毎回使い捨てないといけないからである.

実際の暗号では
Pr(m=i)=Pr(m=i|c=j)+ε

であり,|ε|が小さいほど優秀な暗号であると言える． 攻撃者はこのような統計的偏り(ε)を利用して全数探索の範囲を 絞り込むことができる.

例

平文 m が32bitsであるとき, 暗号方式の統計的偏りなど,
なんらかの要因により平文の最上位桁が特定できるとする.

このとき, 全数探索の範囲が8bitsから7bitsに絞り込むことができた. たった1bitであるが,探索の回数が232回から231回に, 1/2になる. もし攻撃者がn bitsを知ることができたならば,探索の回数が1/(2n)になる.

一般に暗号解読とは全数探索の範囲を絞り込む方法である. 言い換えれば全数探索の計算量を削減することである. 実用的な意味で暗号が解読されたとは, 現実的なコストで 全数探索が可能になったということである.