このページをはてなブックマークに追加このページを含むはてなブックマーク このページを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};は異なる値になります。しかし、ブロック暗号では、ストリーム暗号とは異なり、通常ある一定の期間同一の鍵が使用されます。


*ブロック暗号の安全性 [#b132affa]

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

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

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

**鍵長 [#yd5eea3e]

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

**ブロック長 [#xaa95587]

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

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

-[[暗号文一致攻撃]](cipertext matching attack)
-[[誕生日攻撃]]

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

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


*ブロック暗号の代表的な解読法 [#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の研究者は差分解読法は想定していたが、線形解読法は予想外であったといいます。


*参考文献 [#c00fa9b0]

-『最新 暗号技術』