Source

Block Ciphers

Overview

ブロック暗号 Block cipher は、メッセージを固定長ブロックに分けて、ブロック毎にキーを切り替えて暗号化を行なう。

Pseudo Random Function (PRF)

Pseudo Random Function (PRF) は、以下の二つの関数集合から成り立つ。

  1. 入力 X から出力 Y に変換する関数 (Deterministic function) の集合 Funs[X,Y]
  2. Funs[X,Y] の関数集合のうち、キー K により導かれる関数集合 S = { F(k,.), k in K }

キーによりどの関数が決まり、その関数は決定的であるので、復号が可能になる。言い換えると、入力 x から、どの関数が使われたかを区別できなければ、セキュアな PRF である。

Pseudo Random Permutation (PRP)

DES

Data Encryption Standard (DES) は、IBM により開発され、1976 年に U.S. の連邦規格として採用された共通鍵暗号方式である。

ブロックサイズは 64bits で以下の手順で暗号化する。

Key Schedule

DES のキー長は 64bits で、実際には 56bits が使われる。48bits のラウンド鍵が生成される。

Feistel Network

DES では、Lucifer 暗号の発明者の Horst Feistel に由来する Feistel network と呼ばれる構造で、各ブロックを暗号化する。

64bits のブロックを、半分 32bits の L/R 二つに分けて、以下の処理を 16 回繰り返す。

  • L(i) ブロックを、Feistel 関数を通し R(i) との XOR を、次の R(i+1) とする。
  • R(i) ブロックを、次の L(i+1) とする。

復号は逆順に行なうだけでよい。

Feistel Function

Feistel network では、Feistel 関数により各ブロックが撹拌される。

AES

Advanced Encryption Standard (AES) は、DES の後継として、新たに U.S. の暗号規格として採用された共通鍵暗号方式である。

ブロックサイズは 128bits で、Feistel 構造ではなく、Substitution-permutation Network (SPN) 構造を用いる。入力を 4x4 = 16 bytes の行列として扱い、ビットの撹拌と 128bits のラウンド鍵との XOR を繰り返して暗号化する。

Key Schedule

AES のキーサイズは、128/192/256 bits を選択できる。サイズに応じて SPN 構造での撹拌サイクル数が異なる。

  • AES-128: 128bits keys / 10 cycles
  • AES-192: 192bits keys / 12 cycles
  • AES-256: 256bits keys / 14 cycles

撹拌サイクル数 + 1 回の 128bits(16bytes) のラウンド鍵が生成される。AES-128 の場合、合計で 16 x 11 = 176 bytes の鍵が生成される。

Substitution Permutation Network