信息论的诞生
克劳德·香农（Claude Shannon）在 1948 年发表了论文《通信的数学理论》，创立了信息论。1949 年他又发表了《保密系统的通信理论》，将信息论应用于密码学，奠定了现代密码学的理论基础。
信息量与熵
一个事件 x 发生的自信息（Self-information）：
I(x) = -log₂ P(x) （单位：比特/bit）
事件越不可能发生，包含的信息量越大。例如，抛硬币得到正面 I = 1 bit；掷骰子得到 6，I = log₂6 ≈ 2.58 bit。
香农熵
随机变量 X 的熵 H(X) 是自信息的期望值：
H(X) = -Σ P(x) log₂ P(x)
熵度量了随机变量的不确定性。
例子：
- 公平硬币：H = -0.5×log₂(0.5) - 0.5×log₂(0.5) = 1 bit
- 两面相同的硬币：H = 0 bit（无不确定性）
- 公平骰子：H = log₂6 ≈ 2.58 bit
最大熵：当所有结果等概率时熵最大。即均匀分布时不确定性最高。
联合熵与条件熵
联合熵：H(X, Y) = -ΣΣ P(x, y) log₂ P(x, y)，描述一对随机变量的总不确定性。
条件熵：H(Y|X) = H(X, Y) - H(X)，描述已知 X 后 Y 的剩余不确定性。
互信息
互信息 I(X; Y) = H(X) - H(X|Y)，度量 X 和 Y 之间共享的信息量。
在密码学中：I(M; C) 表示从密文 C 中能获得的关于明文 M 的信息量。理想情况下 I(M; C) = 0。
完善保密性（Perfect Secrecy）
香农定义了一个密码系统的最高安全标准：
P(M=m|C=c) = P(M=m) 对所有明文 m 和密文 c 成立
即观察密文不改变对明文的任何认识，密文和明文统计独立。
用互信息表述：I(M; C) = 0。
香农定理
完善保密性要求 H(K) ≥ H(M)，即密钥的熵至少等于明文的熵。这意味着密钥必须至少和明文一样长。
一次性密码本（OTP）
唯一被证明达到完善保密性的密码系统：
- 加密：c = m ⊕ k（明文与密钥逐比特异或）
- 解密：m = c ⊕ k
三个条件（缺一不可）：
- 密钥完全随机
- 密钥至少与明文等长
- 每个密钥只使用一次（绝不能重复使用）
为什么不能重复使用密钥：若 c₁ = m₁ ⊕ k 且 c₂ = m₂ ⊕ k，则 c₁ ⊕ c₂ = m₁ ⊕ m₂，密钥被消去，攻击者获得了两条明文的异或，从中可以推断出大量信息。
实际限制：密钥分发和存储问题使得 OTP 在大多数场景不实用，但它在军事和外交通信中有应用。
计算安全性 vs 信息论安全性
| 信息论安全 | 计算安全 | |
|---|---|---|
| 定义 | 即使攻击者有无限计算能力也无法破解 | 用当前最佳算法在现实时间内无法破解 |
| 代表 | OTP | AES、RSA |
| 限制 | 密钥至少与明文等长 | 依赖于数学难题的困难性假设 |
| 可证明 | 可以数学证明 | 只有条件性证明（归约到困难问题） |
现代密码学几乎全部建立在计算安全性之上。AES-256 不是信息论安全的（密钥远短于可能的明文空间），但被认为是计算安全的。