暗号技術入門03 対称暗号（共通鍵暗号）

担当:生田

目次

1. 対称暗号とは
2. ワンタイムパッド
3. 安全性
4. ブロック暗号
   1. DES
   2. 3DES
   3. AES

対称暗号とは

見方が異なる呼称が存在する

1. 同じ鍵を共有するから「共有鍵暗号」
2. 暗号化と復号で同じ鍵を使うから「対称暗号」
3. 共有する鍵を秘密にするから「秘密鍵暗号」

※公開鍵暗号との比較

様々な実現方式が存在する

暗号が根拠とする安全性

1. 情報理論的安全性
2. 計算量的安全性
3. 統計量的安全性

ワンタイムパッド

まず排他的論理和

排他的論理和の計算例1

排他的論理和の計算例2

GF(2):有限体

有限体(ガロア体)

四則演算(+,-,×,÷)が定義され閉じている有限集合

`XOR` は `GF(2)` の加法 (+)
1. 集合 F={0,1} 上に加法・乗法が定義されている。
2. 集合 F={0,1} に単位元が存在する。（加法の単位元を０、乗法の単位元を１）
3. 集合 F={0,1} の任意の要素 a に対して、
    a+b=0 を満たす加法の逆元: b = -a、
零元を除いて、
    a * c = 1 を満たす乗法の逆元: c = a-1 が存在する
4. GF(2)上で結合則、分配則、結合則を満たす
    4.1. A xor B = B xor A
    4.2. A xor B xor C = A xor (B xor C)
    4.3. A and (B xor C) = A and B xor A and C

同じビット列を2回xorすると元に戻る

A xor B xor B = A

乱数Rとxorをとる=>暗号

A xor R = E

暗号と乱数Rのxorをとる => 復号

E xor R = A

平文と同じサイズの鍵が必要…

鍵の保管、配送、同期、生成が困難

鍵の保管、配送、同期、生成が困難

解読の難しさは？

鍵長と安全性

1. 情報理論的安全性
   1. 平文候補の中から正しい平文を見つけるのと、鍵候補の中からその鍵を使って復号した平文候補が正しいとわかることの難しさが同じ
   2. |K| ≧|m|⇔Pr(m)=Pr(m|c)
   3. 「鍵にヒントがない」
2. 計算量的安全性
   1. 鍵候補から復号した平文候補の数より、平文候補の数の方が少ない
   2. |K|<|m|⇔Pr(m)<Pr(m|c)
   3. 「鍵をヒントとして使える」
   4. しかし鍵候補から正しい鍵を見つけることは現実的には難しい

実際の共通鍵暗号

1. 現実的な鍵長
   1. 保管、配送、同期、生成が容易なサイズ
   2. 計算量的安全性を確保
   3. 平文をブロック化して |k|と|m|の差が大きくならないようにする工夫
2. 共通規格化
3. オープン化

DES~Data Encryption Standard~

ブロック暗号

ブロック内は対称暗号

Feistel構造

暗号化の漸化式表現

復号の漸化式表現

DESまとめ

1. Feistel構造のまとめ
   1. ラウンド関数は式変形で消える
      1. どれだけ複雑にしても暗号化/復号可能
      2. ラウンド関数に逆関数が存在しなくてもよい
      3. 暗号化の困難さ=ラウンド関数の複雑さ
2. ハードでの実装が単純、etc
3. 安全性
   1. 鍵長|k|=56 。既に計算量的安全性がない
   2. 使用禁止

計算量的安全性の考察

DESを選択平文攻撃する場合の解読時間
* プロセッサの比較計算能力 10^10 個/秒
* 並列実行するプロセッサの数 10^5 個
* プロセッサの平均稼働時間 n 秒
* 全数探索の平均計算量 2^|k|/2 = 2^55

10^10 * n * 10^5 > 2^55
⇔ n > 2^55 / 10^15
⇔ n > 36.028797018963968

3DES~Tripple DES~

DES3段重ね

DESの上位互換

3DESのまとめ

• 計算量的安全性は満たされている
• DESとの互換性が必要な場合のみ使用
• ほとんどの場合AESを採用すべき

AES~Advanced Encryption Standard~

デファクトスタンダード

• 2000年に選定された対称暗号アルゴリズム
• 安全性、速度、実装のしやすさ、etc
• Rijndeal
• オープン。仕様書・ソースコード完全公開
• 「隠すことによるセキュリティ」はなし
• 対称暗号を使う場合は普通この暗号を採用すべき

ブロック暗号

ブロック内は対称暗号

SPN構造

SubBytes

ShiftRows

MixColumns

AddRoundKey

AESのまとめ

• 計算量的安全性は満たされている |k|=256 : 比較的マージンが高い
• 1回のラウンドで全てのビットがかく拌される
• 単純かつ高速
  • ラウンド内の全ての処理をビット演算で記述可能
  • 並列化可能

対称鍵暗号を使うときはAES256を使うこと

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第3章 対象暗号(p48-p79)