「暗号技術入門 秘密の国のアリス」 (1) 第3章 対称暗号

暗号技術の入門書として評判のよい結城浩さんの「暗号技術入門」を読んでいきます。歴史上の暗号に関する章は読むだけにして、ノート自体は「第3章 対象暗号(共通鍵暗号)」からにします。

暗号技術入門 第3版

暗号技術入門 第3版

第3章 対称暗号

暗号とは、(適切な方法を用いればもとに戻せるように)デジタルデータのビット列をぐちゃぐちゃにかき回すこと。ビット列で表現できるデータであればどんなデータでも暗号化できる。

  • ビット列の操作、XOR計算
  • 使い捨てパッド
  • 実際に使われている対称暗号(DES、トリプルDES、AES…)

ビット列の操作、XOR計算

データをビット列に対応付けることをを符号化(encoding)という。

そして、ビット列に適用可能なXOR(排他的論理和)という計算がある。

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

といった具合に、英語としての"or"のイメージ。(論理におけるORは"or"+“and"だよね)長いビット列同士のXORをとるには、同じ桁のビット列同士のXORを計算する。

(A XOR B) XOR B = A という性質がある。(暗号文は複合できなければ意味がない…)

使い捨てパッド(バーナム暗号)

使い捨てパッドは「平文とランダムなビット列とのXORをとる」だけの暗号。使い捨てパッドは無条件に安全で、理論的に解読不可能である。総当りをされたら、もとの平文が求まってしまうことはある。でも解読者はそれが本当にもとの平文なのかはわからない。(もとのビット列と同じ長さのすべてのパターンが得られる)

しかし、使い捨てパッドは肝心の「ランダムなビット列」をどうやって通信相手と共有し、他の人にはモレないようにするのかという問題があるため実際にはほとんど使われていない。

DES

!! 現在はコンピューターの計算能力が向上し、DESによる暗号はほんの数時間で解読できるようになっている。なのでこれから使うべきではない !!

DESは56ビットの鍵を用いて(64ビットの長さを持つが、7ビットお気にエラー検出用の情報が入るので実質56ビット)、64ビットの平文を64ビットの暗号文に暗号化する暗号化アルゴリズム。この「64ビット」のようにブロック単位で処理を行う暗号化アルゴリズムブロック暗号と呼ぶ。

DESでは、ラウンドと呼ばれる処理を何度も繰り返す。DES以外にもこのような仕組みは使われており、この仕組をファイステルネットワークという。

DESにおける1ラウンドは

  1. ラウンドへの入力を左(上位32ビット)と右(下位32ビット)にわける
  2. 右はそのまま新しい右として出力される
  3. 右をラウンド関数に送る
  4. ラウンド関数fは右とサブ鍵からビット列を生成
  5. 得られたビット列と左のXORを新しい左として出力
  6. ラウンドがまだ続く場合のみ、左と右を入れ替える

http://www.hummingheads.co.jp/reports/images/series01_encryption_history_08_01.gif

ファイステルネットワークの1ラウンドは、もう一度同じサブ鍵で実行するともとのビット列が得られる。ラウンドが繰り返されている場合は、サブ鍵を使う順番を逆にして同じファイステルネットワークにかけるだけでよい。

ファイステルネットワークの性質として、ラウンド関数f自体は非可逆でもよいという点がある。ラウンド関数を複雑にすれば、アルゴリズムを変えること無く暗号を強くできる!

ラウンド関数の詳細やサブ鍵の生成手法については下がくわしかった。

www.atmarkit.co.jp

DES暗号を解読するには差分解読法、線形解読法がある。

トリプルDES

トリプルDESはその名の通りDESを3回用いる方法。これにより鍵長は56*3=168ビットとなる。

http://www.w3ii.com/cryptography/encryption_scheme.jpg

ポイントとして、2回目は暗号化ではなく復号化しているところがあげられる。仮にすべての鍵を同一にすると単なるDESとなるため、過去にDESによって暗号化された暗号文の解読にも用いることができる。

DESもそうだが、強度のみならず処理が遅いという難点がある。

AES

AESは規格の名前であり、実際にAESとして採択されたアルゴリズムRijndaelという。

AES規格としてのRijndaelでは、ブロック長は128ビット、科技庁は128,192,256ビットのいずれかである。

RijndaelではファイステルネットワークではなくSPN構造が用いられている。これも複数のラウンドから構成されており、1ラウンドはSubBytes,ShiftRows, MixColumns, AddRoundKeyという4つの処理が続けて行われる。

  1. SubBytesでは入力値を1バイトごとにSボックスという換字表から1バイトの値を得る。(単一換字暗号)
  2. ShiftRowsでは4バイトごとにつくった行を左シフトする。
  3. MixColumnsでは4バイトの値をビット演算を用いて別の4バイトの値に変換する
  4. AddRoundKeyでMixColumnsの出力とラウンド鍵のXORをとる

復号化におけるラウンドはこれは逆の手順で行う。