维吉尼亚密码

维吉尼亚密码

凯撒密码的升级版。 定义 \(CaesarEnc(p, k), CaesarDec(p, k)\) 为凯撒加密和解密。秘钥 K 为一个长为 d 的大写字母符串。

def getIndex(char):
    return ord(char) - ord('A')

def encryption(S, K):
  res = ''
  for i in range(len(S)):
    res += CaesarEnc(S[i], getIndex(K[i % d]))
  return res

def decryption(S, K):
  res = ''
  for i in range(len(S)):
    res += CaesarDec(S[i], getIndex(K[i % d]))
  return res

虽然维吉尼亚密码一度被认为不可能被破解，但事实上它不是完善保密加密。
令 \(\Pi = (Gen, Enc, Dec)\) 表示维吉尼亚密码，秘钥长度 \(d \in \{1, 2\}\)
1. 敌手 \(A\) 输出一对信息 \(m_0 = aa, m_1 = ab\)
2. 由 \(Gen\) 产生一个随机秘钥 \(k\)，在 \(m_0, m_1\) 中随机选择一个加密，得到挑战密文 \(c_1c_2 = Enc_k(m_b), b \in \{0, 1\}\)
3. 如果 \(c_1 = c_2\)，输出 0，否则输出 1

现在计算 \(Pr[PrivK_{A, \Pi}^{eav} = 1]\) \[ \begin{aligned} & Pr[PrivK_{A, \Pi}^{eav} = 1] \\ & = \frac{1}{2} \times Pr[PrivK_{A, \Pi}^{eav} = 1|b = 0] + \frac{1}{2} \times Pr[PrivK_{A, \Pi}^{eav} = 1|b = 1] \\ & = \frac{1}{2} \times Pr[A \ outputs \ 0|b = 0] + \frac{1}{2} \times Pr[A \ outputs \ 1|b = 1] \end{aligned} \] 1. 当 \(m_b = aa\) 时， \[ \begin{aligned} & Pr[A \ outputs \ 0|b = 0] \\ & = \frac{1}{2} \times Pr[c_1 = c_2|d = 1] + \frac{1}{2} \times Pr[c_1 = c_2|d = 2] \\ & = \frac{1}{2} + \frac{1}{2} \times \frac{1}{26} \approx 0.52 \end{aligned} \] 2. 当 \(m_b = ab\) 时， \[ \begin{aligned} & Pr[A \ outputs \ 1|b = 1] = 1 - Pr[A \ outputs \ 0|b = 1] \\ & = 1 - (\frac{1}{2} \times Pr[c_1 = c_2 - 1|d = 1] + \frac{1}{2} \times Pr[c_1 = c_2 - 1|d = 2]) \\ & = 1 - (0 + \frac{1}{2} \times \frac{1}{26}) \approx 0.98 \end{aligned} \] \(Pr[PrivK_{A, \Pi}^{eav} = 1] \approx \frac{1}{2} \times 0.52 + \frac{1}{2} \times 0.98 = 0.75 > \frac{1}{2}\)

破解方法

首先要知道秘钥的长度。

Kasiski 测试法

因为英文中有很多出现频繁的2字词或3字词，比如 the。虽然说不同位置的 the 会被加密成不通的字符串，但对于两个相距 d（秘钥长度）的倍数的 the，加密的结果是相同的。 在足够长的文本中不难发现这样的字符串。 假设 the 被加密成 ABC，并在密文中找到三处 ABC，第一第二处相距 5，第二第三处相距 20，那么 d 很可能是 5。

重合指数法

对于秘钥长度为 d 的维吉尼亚密码，将密文分割成 d 组，\(s_x[i] = s[(x + d * i) \mod |s|]\)（密文为 s ）
每一组可以看作是凯撒加密，因为第 x 组的字符都做了 d[x] 的偏移。

在有意义的英文文本中，两个字母相同的概率 \(I = \sum_{i=0}^{25}p_i^2 = 0.065\)
分别测试 \(d' = 1,2,3...\)，每次得到 \(d'\) 个 \(I\) 值，离 \(0.065\) 最近且最小的那组反映出秘钥的长度。 在这个过程中实际使用 \(I\) 的估计值 \(I = \sum_{i=0}^{25}\frac{f_i}{d'}\frac{f_i - 1}{d' - 1}\)。（原因未知，可能和方差的估计值之类的有关，先挖个坑）

核心代码如下。

def splitText(ciphertext, group_num):
    """
    将 ciphertext 分组
    :param ciphertext: 密文
    :param group_num: 组数
    :return: 分组后的列表 1 * group_num
    """
    groups = ['' for i in range(group_num)]
    for i in range(len(ciphertext)):
        for j in range(group_num):
            if i % group_num == j:
                groups[j] += ciphertext[i]
    return groups


def calFreq(string):
    """
    计算 string 各个字符的频数
    :param string:
    :return: 频数列表 1 * 26
    """
    freq = [0 for i in range(26)]
    for char in string:
        freq[getIndex(char)] += 1
    return freq


def calCI(freq, length):
    """
    计算 CI
    :param freq: 某个分组的频数列表
    :param length: 某个分组的长度
    :return: CI 列表
    """
    CI = 0
    for i in range(26):
        CI += freq[i] / length * (freq[i] - 1) / (length - 1)
    return CI


def printCIs(CIs):
    for d in range(1, len(CIs)):
        print(f'd={d}, CI: {CIs[d]}')


def attack(ciphertext, limit):
    """
    :param ciphertext:
    :param limit: 秘钥长度尝试的上限
    :return:
    """
    # 记录频数和CI
    freqs = [[[] for i in range(limit)] for i in range(limit)]  # d * d * 26
    CIs = [[] for i in range(limit)]

    # 破解秘钥长度
    for d in range(1, limit):
        groups = splitText(ciphertext, d)

        for i in range(d):
            freqs[d][i] = calFreq(groups[i])

        CI = []
        for i in range(d):
            CI.append(calCI(freqs[d][i], len(ciphertext) // d))
        CIs[d] = CI

    eps = 0.005
    key_len = 0
    for d in range(1, limit):
        avg = sum(CIs[d]) / d  # 这里选择用均值看 CI 和 0.065 的接近程度
        if abs(avg - 0.065) < eps:
            key_len = d
            eps = abs(avg - 0.065)
    print(f'key length = {key_len}')

    # 得知秘钥长度后，开始破解秘钥内容
    groups = splitText(ciphertext, key_len)
    for i in range(key_len):
        length = len(groups[i])
        for j in range(26):
            freqs[key_len][i][j] /= length  # 将频数变成频率

    result = [0 for i in range(key_len)]  # 存放秘钥结果
    for j in range(key_len):
        # 秘钥的每一位在对应的组中都和 Caesar 相同
        I = [0 for i in range(26)]
        eps = 0.005
        res = -1
        for key in range(0, 26):
            for i in range(26):
                I[key] += p[i] * freqs[key_len][j][(i + key) % 26] # p 为英文字母出现频率的统计表
            if abs(I[key] - 0.065) < eps:
                res = key
                eps = abs(I[key] - 0.065)
        # 所有的值偏差都超过 0.005 的话选最接近的那个
        if res == -1:
            res = I.index(min(I, key=lambda x: abs(x - 0.065)))
        result[j] = res

    # 把 result 数组转变成 秘钥字符串
    for i in range(key_len):
        result[i] = shift('A', int(result[i]))
    return ''.join(result)

完整代码

参考文献

1. Introduction To Modern Cryptography ↩︎
2. 维吉尼亚密码的原理及破解 ↩︎
3. 维吉尼亚密码破解 ↩︎