# 共通鍵暗号

暗号化・復号で同一の鍵を用いる暗号化方式

# シナリオ

• Aliceが秘密鍵$key$を作成し，Bobに安全に共有
• Aliceがメッセージ$m$を$key$で暗号化$c = Enc(m, key)$し，Bobに送信
• Bobが受け取った暗号文$c$を$key$で復号$m = Dec(c, key)$して平文$m$を得る

# 共通鍵暗号の満たすべき性質

• 正当性
  • $m = Dec(Enc(m, key), key)$が成立すること
• 秘匿性
  • 暗号文$c$から平文$m$に関連する情報が得られないこと

# 共通鍵暗号に対する攻撃モデル

# 暗号文単独攻撃：Ciphertext Only Attack

攻撃者が「解読対象の暗号文$c^*$」と「盗聴した暗号文$c_1$，$c_2$，$c_3$…$c_k$」を手元に持っている状況での攻撃．通信路の盗聴という攻撃に相当．

# 既知平文攻撃：Known Plaintext Attack

攻撃者が「解読対象の暗号文$c^*$」と「（同一の鍵で暗号化された）ランダムな平文と暗号文の対$(m_1, c_1)$，$(m_2, c_2)$，$(m_3, c_3)$…$(m_k, c_k)$」を手元に持っている状況での攻撃．過去の平文が特定済みであるような状況での攻撃に相当．

# 選択平文攻撃：Chosen Plaintext Attack

攻撃者が「解読対象の暗号文$c^*$」を持ち，「攻撃者が選んだ任意の平文に対応する暗号文を自由に入手できる」ような状況での攻撃．

# 選択暗号文攻撃：Chosen Ciphertext Attack

攻撃者が「解読対象の暗号文$c^$」を持ち，「攻撃対象の暗号文$c^$を入手する前の時点で，攻撃者が自分の選んだ暗号文に対応する平文を入手することができる」ような状況での攻撃．

# 適応的選択暗号文攻撃：Adaptive Chosen Ciphertext Attack

攻撃者が「解読対象の暗号文$c^*$」を持ち，「攻撃者が選んだ任意の暗号文に対応する平文を自由に入手できる」ような状況での攻撃．

# 鍵全数探索攻撃に対する共通鍵暗号の安全性

秘密鍵が$k$bitであるような共通鍵暗号では，$2^k$個の鍵を全部試せば必ず秘密鍵を得ることができる．共通鍵暗号では「鍵全数探索攻撃よりも効率的に秘密鍵を求めるアルゴリズムが存在しないこと」が安全性に対する条件である．

# さまざまな共通鍵暗号

• ストリーム暗号
  • 平文を小さい単位で順次処理していく方式
  • アルゴリズムを実行する回数が1回
• ブロック暗号
  • 平文を一定の大きさの単位で処理していく方式
  • アルゴリズムを実行する回数がブロックの個数分

# バーナム暗号

• 👍
  • 情報理論的安全性を持つ
    • たとえ，鍵全数探索を実行できる無限の計算能力を持っている攻撃者であっても解読できない（どれが本当の平文なのかがわからない）
  • 処理が「平文と鍵でxor」と単純なので非常に高速
• 👎
  • 少なくとも平文と同じ長さの秘密鍵が必要になるし，基本的に鍵は使い捨てなのでいくら鍵を用意しても足りないし，そもそもこの秘密鍵を安全に共有できるなら暗号化する必要がない
  • 鍵の生成に「真性乱数」を用意しなければならず，長い鍵を作るには手間がかかる

# ストリーム暗号

• 👍
  • バーナム暗号と比べて（安全性をやや犠牲にしながらも）効率性を向上
• 👎
  • 擬似乱数生成器の安全性がストリーム暗号の安全性に直結する
    • 過去の系列を見て未来の系列が予測できてしまえば解読されてしまう
    • 擬似乱数生成器の初期化に用いる秘密鍵を特定されてしまうと解読されてしまう