凯撒密码

本文最后更新于 2022年10月23日上午

凯撒密码

经典的移位密码。
定义 \(ord()\) 和 \(chr()\)，\(ord('a') = 97\), \(chr(97) = 'a'\)。秘钥 \(K \in \{0, 25\}\) 。

def encryption(S, K):
  res = ''
  for c in S:
    res += (ord(c) + K) % 26
  return res

def decryption(S, K):
  res = ''
  for c in S:
    res += (ord(c) - K) % 26
  return res

破解方法

暴力

因为 \(|K| = 26\)，所以枚举 26 次就能得到有意义的明文。

统计

因为凯撒密码不是概率加密，即同一个字符每一次加密的结果都是一样的，所以密文和明文的字母概率分布是相同的，所以对于有意义的文本，可以通过统计字母出现的频率，如下图，猜测出秘钥 K。英文文本中字母的平均频率[1] 不难算出 \[ \sum_{i=0}^{25} p_i^2 \approx 0.065 \] 令 \(q_i\) 表示第 \(i\) 个字符在密文中出现的频率（A 是第 \(0\) 个字符）。对于秘钥 \(k \in {0, .., 25}\)， \[ I_k = \sum_{i=0}^{25} p_i * q_{(i+k) \mod 26} \approx 0.065 \] 核心代码如下。

p = {
  0: 0.082,
  1: 0.015,
  2: 0.028,
  3: 0.042,
  4: 0.127,
  5: 0.022,
  6: 0.020,
  7: 0.061,
  8: 0.070,
  9: 0.001,
  10: 0.008,
  11: 0.040,
  12: 0.024,
  13: 0.067,
  14: 0.075,
  15: 0.019,
  16: 0.001,
  17: 0.060,
  18: 0.063,
  19: 0.090,
  20: 0.028,
  21: 0.010,
  22: 0.024,
  23: 0.020,
  24: 0.001,
  25: 0.001
}


def attack(ciphertext):
  n = len(ciphertext)
  I = [0 for i in range(26)]
  freq = [0 for i in range(26)]
  for char in ciphertext:
    freq[getIndex(char)] += 1
  for i in range(26):
    freq[i] /= n

  eps = 0.005
  res = -1
  for key in range(0, 26):
    for i in range(26):
      I[key] += p[i] * freq[(i + key) % 26]
    if abs(I[key] - 0.065) < eps:
      res = key
      eps = abs(I[key] - 0.065)
  return res