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

目次

宣伝

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

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

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

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

ブロック暗号

 平文のビット列をブロック長と呼ばれるある一種の長さnごとに分割し、そのブロック単位で暗号化を行う。この長さnは多くの場合、n=64やn=128であることが多い。それはコンピュータが扱いやすい数にしたほうが便利だからである。これこそがブロック暗号のモチベーションである。ストリーム暗号と比べれば、鍵サイズを減らすことできる。なぜならばブロック単位だと置換は多くなるから、鍵を使いまわしても大丈夫だからだ。ストリーム暗号ではビット単位なので鍵の使いまわしはできなかった。

[定義]
ブロック長と呼ばれる長さnビットの平文mをまとめて暗号化する共通鍵暗号系をブロック暗号という。

 暗号化アルゴリズムをEK、復号アルゴリズムをDKと表すことにする。Kという添え字が付いているのは、Kを入力とされるということを明示するためである。

 ストリーム暗号では同一の平文miが続けて入力されたとしても、鍵kiが次々変化していくために、暗号文ciは異なる値になる。しかし、ブロック暗号では、ストリーム暗号とは異なり、通常ある一定の期間同一の鍵が使用される。

[定義]
ブロック長nのブロック暗号において、鍵kをひとつ決めたとき、暗号化アルゴリズムEKは平文空間{0,1}nから暗号文空間{0,1}nへの置換であり、復号アルゴリズムDKはその逆置換である。

理想的なブロック暗号

 擬似ランダム関数と擬似ランダム置換を見てもらうとわかると思うが、次にnビットの集合からnビットの集合への関数・置換の関係式と、総数の値を列挙する。

  • ランダム関数の総数:|~R_n~|~=~2^{n~\cdot~2^{n}}
  • ランダム置換の総数:|~P_n~|~=~\(~2^n~\)~!
  • 擬似ランダム関数の総数:|~F_n~|
  • 擬似ランダム置換の総数:|~ENC_n~|
  • R_n~\supset~F_n
  • P_n~\supset~ENC_n
  • R_n~\supset~P_n

 多項式時間内では関数と置換を効率的に識別しようとするのは難しい(入出力のビット長をnとする)。  もし100%の確率で識別しようとしたらすべての入力xとすべての出力yが一対一となることを調べる必要がある。出力結果が重複するものが1つもなければ置換、1つでもあれば関数と判定できる。  もし50%の確率で識別したければ山勘で十分である。何の計算も必要もしない。  また、関数であればバースディパラドックスより約1.17~\times~2^{\frac{n}{2}}回の計算で50%の確率で重複する出力値が見つかる。山勘でも50%の確率で識別できるため、バースディパラドックスで50%を有意な確率で重複する出力値を見つけるための計算回数が知りたい。例えば、60%であれば約1.354~\times~2^{\frac{n}{2}}回、90%であれば約2.146~\times~2^{\frac{n}{2}}回計算すればよい。  よって、50%よりも大きい確率で識別するには、約1.17~\times~2^{\frac{n}{2}}~+~\alpha回の計算回数が必要で、オーダーはnなので多項式時間ではできないことがわかる。

 そのため、本来はランダム関数族Rnを使ったほうが安全だが、アドバーサリー指数時間の計算ができないという条件が付くなら、代わりにランダム置換族Pnで代用しても問題ないことになる。つまり、理想的なブロック暗号とは、ENCnが長さnの疑似ランダム置換族となるような暗号となる。

ブロック暗号の安全性

 どのようなブロック暗号であっても鍵を全数探索攻撃すればいつかは必ず正しい鍵を見つけることができる。つまり鍵全数探索攻撃に対する耐性がブロック暗号の安全性の上限となる。

 そこでブロック暗号の安全性評価では、アタッカーがデータ攪拌部の構造が統計的に解析可能であり、多数の平文と暗号文のペアを入手できると前提を置いて、様々な暗号攻撃を行う。このとき秘密鍵あるいは副鍵を求めるために必要となる計算量が鍵全数探索攻撃で必要な計算量を下回ることがないとき(鍵全数探索攻撃が一番効率がよい)に、そのブロック暗号を(学術的に)安全なブロック暗号という。反対に鍵全数探索攻撃よりも効率のよい攻撃方法がひとつでも発見されれば、そのブロック暗号は(学術的に)破られたという。

 例えばAES、Camellia、MISTY1などは鍵全数探索がもっとも効率のよい攻撃方法が証明されている。つまり安全なブロック暗号である。

鍵長

 鍵長は鍵全数探索攻撃に対する安全性を決めるパラメータである。鍵全数探索攻撃に対する十分な耐性を持たせるために、現在では鍵長として128ビット以上を指定することが一般的になっている。

ブロック長

 ブロック長は暗号文を用いる暗号解読手法に対する安全性を左右するパラメータである。

 同じ鍵で暗号化された暗号文を2λ個(λ:ブロック長)をアタッカーが集めることができたとする。このとき次の攻撃が成功してしまう可能性がある。

 現在では128ビットのブロック長を使うブロック暗号が推奨されている。ブロック長が64ビットだと、同じ秘密鍵で暗号化された暗号文を232個(=約32Gバイト)をランダムに集めると、その中に1組は同じ暗号文が含まれている可能性が高く、この数学的事実を利用して暗号攻撃が成功してしまうことがある。現在のPCでは32GバイトなどのHD容量は簡単に確保できるので、AESプロジェクトが開始された1997年以降は64ビットブロック暗号は止めるようにいわれたわけだ。

 では128ビットブロック暗号を誕生日攻撃をしたとするとどうなるか考えてみよう。同じ秘密鍵で暗号化された暗号文を264個(=約228Tバイト)をランダムに集める必要がある。この容量を確保できる時代が来るのは相当後だと推測されるので(28Tバイトではなく、228Tバイト!であることに注意)、128ビットブロック暗号にすると圧倒的に安全性が高くなるということわかる。

ブロック暗号の代表的な解読法

差分解読法

 これは選択平文攻撃の一種である。1989年にイスラエルのEli BihamとAdi Shamirによって発見された。対応範囲が広く、多くのブロック暗号に有効です。NTTのFEAL暗号もこれで解読された。

 暗号鍵の全数探索法より高速な初めての解読法である。

 DESの暗号アルゴリズムは公開されていたが、「なぜそのような計算をするのか?」ということについて何も説明はなかった。後にIBMから1979年にDESが発表されるより前の1974年の時点で、すでに差分解読法があることに気付いており、その対策を施していたという逸話もある。

 解読者の目標は、うまく選んだ平文と暗号文のペア、および暗号化アルゴリズムについての完全な情報のもとで鍵Kを特定することである。または、現実的には鍵Kの可能性を、計算機で総当りに調べることが可能になる程度まで絞り込めればよいわけである。

 暗号化アルゴリズムがよほど簡単でない限り、ペアをたくさん集めても平文と暗号文の相関はなかなか得ることはできない。しかし、平文を少し変化させたときに、その暗号文がどのくらい変化するのかを見てみたらどうなるだろうか? このアプローチが差分解読法である。

 まず2つのペア(m0,c0),(m1,c1)があったとする。このときペアの選び方は特別の違いがあるようにする。すると、m0+m1=δ、c0+c1=δ'を求めることができる。このδ(∈{0,1}n)は差分です。この差分が相関関係を表す。分布に偏りがあれば、それを利用して鍵Kを求める。つまり、「c1+c2=EK(m1)+EK(m2)〜m1+m2」において、関係「〜」に何かあるかを調べるわけである。このような関係があるのは、統計的に確率は小さいかも知れない。しかし、期待できる理由はある。ブロック暗号の中では、鍵(の一部)が平文(の一部)とXOR演算を取る操作が含まれることが多いからだ。しかも、あらわに含まないとしても、結果的に暗号化アルゴリズムのある部分がそのような操作に対応してしまっているかもしれない。もしそうなら、暗号文2つの差分を取ることで、鍵の情報(の一部)がXOR演算を2回取ることによって、キャンセルされて消えてしまう。これはXOR演算の表を見てみればわかるはずだ。

 同じものをXOR演算するわけなので、「0\oplus0」または「1\oplus1」のどちらかである。どちらの場合も結果は0になるわけなので、何かに0をXOR演算しても結果は変わらない。軽くまとめておく。

  • 0\oplus0=0
  • 1\oplus1=1
  • A\oplus0=A
  • XOR演算は並びに依存しない。普通の加法+のように扱える。

 入力X,Y、鍵の部分Kとする。

(X\oplusK)\oplus(Y\oplusK)=(X\oplusY)\oplus(K\oplusK)=(X\oplusY)\oplus0=X\oplusY

 結果として、X\oplusYは鍵Kの影響を受けてないことがわかる。よって、入力差分がある値になるように平文たちを選択して、このキャンセルの原理を利用して鍵空間を狭めることができて、対応する暗号文たちをもとにして鍵を推定するのである。実際、DES暗号の場合は、ラウンドを通り抜けるにつれて、違いがどう発展するかを分析する。

線形解読法

 平文と暗号文の組(m,c)と鍵Kの間の何らかの線形関係式を考える。ここで、鍵Kを固定したとき、その線形関係式を成立させる(m,c)の個数がある程度以上に多い場合、の偏りの事実を利用して鍵を求める解読法である。

 1994年に12台のワークステーションを利用して、線形解読法を利用して50日間でDES暗号を解析した。これが世界初のDES暗号の解読となった。DESを設計したIBMの研究者は差分解読法は想定していたが、線形解読法は予想外であったという。

参考文献

  • ゼミノート
  • 『現代暗号の基礎数理』
  • 『最新 暗号技術』