Overview

Definition of Cipher

暗号 Cipher は、メッセージを暗号文に変換する「暗号関数」と、暗号文を元メッセージに復元する「復号関数」のペアで成り立つ。

  • E (Encrypt): 暗号関数
  • D (Decrypt): 復号関数
  • K (Key): 暗号キー
  • M (Message): メッセージ
  • C (Cipher): 暗号文

を定義すると、以下の式がなりたつ。

Perfect Secrecy

  • Shannon, Claude E. (October 1949). “Communication Theory of Secrecy Systems”

暗号文から平文の違いを区別できなければ、解読不能な暗号である。

ランダムに生成されるあらゆる暗号キーから、同じ長さの二つの異なるメッセージが、同じ暗号文となる確率が等しければ、どの平文であるかを判別できない。この条件を満たす暗号アルゴリズムは Perfect secrecy を持つと定義される。

One Time Pad (OTP)

一回限りの暗号キーを使って暗号化する方法を One Time Pad (OTP) と呼ぶ。

コンピュータ向けには、メッセージと暗号キーの XOR 演算による暗号化が用いられる。

m: 01001000 01000101 01001100 01001100 01001111: HELLO
k: 00100100 01001011 01000101 01011001 00100001: $KEY!
c: 01101100 00001110 00001001 00010101 01101110: l...n

以下の式により XOR 演算により暗号の定義を満たすことが証明できる。

  • メッセージよりも大きい暗号キーを持たなければならない欠点がある。
  • 同じ暗号文を生成できる暗号キーの数は 1 である。一回限りのキーであれば、同じ暗号文となる確率は 1/K であり Perfect secrecy を持つ。