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

  • 追加された行はこの色です。
  • 削除された行はこの色です。
*目次 [#l6dac4b3]

#contents


*ブロック暗号 [#ved888b4]

 平文のビット列をブロック長と呼ばれるある一種の長さnごとに分割し、そのブロック単位で暗号化を行います。この長さnは多くの場合、n=64やn=128であることが多いです。それはコンピュータが扱いやすい数にしたほうが便利だからです。

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

 暗号化アルゴリズムをESUB{K};、復号アルゴリズムをDSUB{K};と表すことにします。Kという添え字が付いているのは、Kを入力とされるということを明示するためです。

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


*ブロック暗号の代表的な解読法 [#td3a2686]

**差分解読法 [#u62803a2]

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

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

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

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

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

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

 同じものをXOR演算するわけなので、「0&mimetex("\oplus");0」または「1&mimetex("\oplus");1」のどちらかです。どちらの場合も結果は0になるわけなので、何かに0をXOR演算しても結果は変わりません。軽くまとめておきます。

-0&mimetex("\oplus");0=0
-1&mimetex("\oplus");1=1
-A&mimetex("\oplus");0=A
-XOR演算は並びに依存しない。普通の加法+のように扱える。

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

(X&mimetex("\oplus");K)&mimetex("\oplus");(Y&mimetex("\oplus");K)=(X&mimetex("\oplus");Y)&mimetex("\oplus");(K&mimetex("\oplus");K)=(X&mimetex("\oplus");Y)&mimetex("\oplus");0=X&mimetex("\oplus");Y

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


**線形解読法 [#m59f37fd]

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

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