概述

仿射密码（Affine Cipher）是一种基于模运算的单表替换密码。其加密函数为线性变换加偏移，解密依赖模逆元。在 CTF 中常以"已知部分明文（如 flag 头）→ 爆破参数 a、b → 还原完整明文"的形式出现。

加密:  y = (a·x + b) mod m
解密:  x = a⁻¹·(y - b) mod m

x = 明文字母序号 (0~25)
y = 密文字母序号 (0~25)
m = 字母表大小 (26)
a, b = 密钥 (a 必须与 m 互质)

数学原理

为什么 a 必须与 m 互质

如果要解密唯一，加密必须是双射（一一对应）。加密函数 $E(x) = (ax + b) \bmod m$ 是双射的充分必要条件是 $\gcd(a, m) = 1$。

证明：

若 $\gcd(a, m) = d > 1$，则存在 $x_1 \neq x_2$ 使得：

$$ ax_1 \equiv ax_2 \pmod{m} $$

即 $a(x_1 - x_2) \equiv 0 \pmod{m}$。由于 $d \mid a$ 且 $d \mid m$，可取 $x_1 - x_2 = m/d < m$，使得 $a \cdot (m/d) \equiv 0 \pmod{m}$。此时 $E(x_1) = E(x_2)$，加密不再是一对一。

模逆元与解密

解密需要求 $a$ 在模 $m$ 下的逆元 $a^{-1}$，满足：

$$ a \cdot a^{-1} \equiv 1 \pmod{m} $$

对于 $m=26$，各有效 $a$ 的逆元：

| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
| :-------: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |

# 计算模逆元（扩展欧几里得算法）
def mod_inverse(a: int, m: int = 26) -> int:
    """返回 a 在模 m 下的逆元，若不互质则返回 None"""
    def egcd(a, b):
        if b == 0:
            return a, 1, 0
        g, x1, y1 = egcd(b, a % b)
        return g, y1, x1 - (a // b) * y1

    g, x, _ = egcd(a, m)
    if g != 1:
        return None
    return x % m

# 示例
print(mod_inverse(5, 26))   # 输出: 21
print(mod_inverse(20, 26))  # 输出: None (gcd(20,26)=2)

加密/解密示意

以 a=5, b=8 加密 "HELLO" 为例

明文  H → 7   E → 4   L → 11  L → 11  O → 14
      ↓        ↓        ↓        ↓        ↓
加密  y=(5·7+8)%26  (5·4+8)%26  (5·11+8)%26  (5·11+8)%26  (5·14+8)%26
      =43%26=17     =28%26=2    =63%26=11    =63%26=11    =78%26=0
      ↓        ↓        ↓        ↓        ↓
密文  R → 17  C → 2   L → 11  L → 11  A → 0
      结果: "RCLLA"

Python 完整实现

加密类

import math

class AffineCipher:
    def __init__(self, a: int, b: int, m: int = 26):
        if math.gcd(a, m) != 1:
            raise ValueError(
                f'a={a} 与 m={m} 不互质 (gcd={math.gcd(a,m)})，'
                f'解密不唯一，请使用以下合法值之一: '
                f'{[x for x in range(1,m) if math.gcd(x,m)==1]}'
            )
        self.a = a
        self.b = b
        self.m = m
        self.a_inv = self._mod_inverse(a, m)

    @staticmethod
    def _mod_inverse(a: int, m: int) -> int:
        def egcd(a, b):
            if b == 0:
                return a, 1, 0
            g, x1, y1 = egcd(b, a % b)
            return g, y1, x1 - (a // b) * y1
        g, x, _ = egcd(a, m)
        return x % m

    def encrypt(self, plain: str) -> str:
        """加密 (仅处理 a-z，其他字符原样保留)"""
        result = []
        for ch in plain:
            if 'a' <= ch <= 'z':
                x = ord(ch) - ord('a')
                y = (self.a * x + self.b) % self.m
                result.append(chr(y + ord('a')))
            elif 'A' <= ch <= 'Z':
                x = ord(ch) - ord('A')
                y = (self.a * x + self.b) % self.m
                result.append(chr(y + ord('A')))
            else:
                result.append(ch)
        return ''.join(result)

    def decrypt(self, cipher: str) -> str:
        """解密: D(y) = a⁻¹·(y - b) mod m"""
        result = []
        for ch in cipher:
            if 'a' <= ch <= 'z':
                y = ord(ch) - ord('a')
                x = (self.a_inv * (y - self.b)) % self.m
                result.append(chr(x + ord('a')))
            elif 'A' <= ch <= 'Z':
                y = ord(ch) - ord('A')
                x = (self.a_inv * (y - self.b)) % self.m
                result.append(chr(x + ord('A')))
            else:
                result.append(ch)
        return ''.join(result)


# 使用示例
cipher = AffineCipher(a=5, b=8)
enc = cipher.encrypt('HELLO')
print(enc)                     # RCLLA
print(cipher.decrypt(enc))     # HELLO

已知明文爆破

CTF 中最常见的场景：已知密文 + 部分明文（如 flag 头 flag{），爆破参数 $(a, b)$。

def crack_affine(ciphertext: str, known_plain: str) -> list:
    """
    已知明文攻击：用已知的明文-密文对应关系爆破 a, b

    返回: [(a, b, 解密结果), ...]
    """
    results = []
    c_part = ciphertext[:len(known_plain)]

    for a in range(1, 26):
        if math.gcd(a, 26) != 1:     # 跳过不互质的 a
            continue
        for b in range(0, 26):
            match = True
            for cp, kp in zip(c_part, known_plain):
                if not ('a' <= cp <= 'z' and 'a' <= kp <= 'z'):
                    continue
                y = ord(cp) - ord('a')
                x = ord(kp) - ord('a')
                if y != (a * x + b) % 26:
                    match = False
                    break
            if match:
                cipher = AffineCipher(a, b)
                results.append((a, b, cipher.decrypt(ciphertext)))
    return results


# 示例
c  = 'siwm{ewk3ys28-10ks-11ye-80e5-8k1645499qee}'
res = crack_affine(c, 'flag')
for a, b, flag in res:
    print(f'a={a}, b={b} → {flag}')

爆破过程说明：

密文:       s  i  w  m  { ...
               ↓  ↓  ↓
已知明文:    f  l  a  g  { (flag 的格式已知)
               ↓  ↓  ↓
方程组:    18=(a·5 +b)%26   8=(a·11+b)%26   22=(a·0+b)%26
               ↓              ↓              ↓
           (s=18,f=5)     (i=8,l=11)     (w=22,a=0)

由第三式: b ≡ 22 (mod 26) → b = 22
代入第一式: 5a + 22 ≡ 18 (mod 26) → 5a ≡ 22 (mod 26)
5⁻¹ ≡ 21 (mod 26) → a ≡ 22×21 ≡ 20 (mod 26)
验证第二式: 11×20+22 = 242 ≡ 8 (mod 26) ✓

结论: a=20, b=22
⚠ a=20 与 26 不互质 → 解密存在二义性 → 需用枚举方式逐字解密

逐字枚举解密（当 a 不互质时）

仿射密码理论要求 $\gcd(a, m)=1$，但 CTF 出题时可能使用不互质的 $a$。此时解密不唯一，需逐字枚举：

def decrypt_bruteforce(ciphertext: str, a: int, b: int) -> str:
    """逐字爆破解密：对每个密文字母尝试所有 26 种明文映射"""
    result = []
    for ch in ciphertext:
        if 'a' <= ch <= 'z':
            y = ord(ch) - ord('a')
            for x in range(26):
                if (a * x + b) % 26 == y:
                    result.append(chr(x + ord('a')))
                    break     # 取第一个匹配（可能不唯一）
        else:
            result.append(ch)
    return ''.join(result)


print(decrypt_bruteforce(c, a=20, b=22))

CTF 实战

常见题型

频率分析法

当密文足够长且未知密钥时，可利用英文字母频率分布推断参数：

from collections import Counter

def freq_attack(ciphertext: str) -> list:
    """基于频率分析的仿射密码破解"""
    # 统计密文字母频率
    counts = Counter(ch for ch in ciphertext if 'a' <= ch <= 'z')
    most_common = counts.most_common(2)

    results = []
    for a in [x for x in range(1, 26) if math.gcd(x, 26) == 1]:
        y1 = ord(most_common[0][0]) - ord('a')  # 最高频密文 → E(4)
        y2 = ord(most_common[1][0]) - ord('a')  # 次高频密文 → T(19)
        # 解方程组: y1 = a·4 + b,  y2 = a·19 + b
        # → b = y1 - 4a,  代入 → y2 - y1 = 15a  → a = (y2-y1)·15⁻¹
        inv15 = mod_inverse(15, 26)
        if inv15 is None:
            continue
        a_candidate = ((y2 - y1) * inv15) % 26
        if a_candidate != a:
            continue
        b_candidate = (y1 - a * 4) % 26
        cipher = AffineCipher(a_candidate, b_candidate)
        results.append((a_candidate, b_candidate, cipher.decrypt(ciphertext)))
    return results

与其他古典密码对比

仿射密码的密钥空间仅 312，可在毫秒级完成爆破。比凯撒密码（25）略好，但远不足以对抗现代攻击。

参考文献

1. Wikipedia. Affine cipher [EB/OL]. https://en.wikipedia.org/wiki/Affine_cipher
2. Trappe W, Washington L C. Introduction to Cryptography with Coding Theory [M]. Pearson, 2006.
3. Stinson D R. Cryptography: Theory and Practice [M]. CRC Press, 2005.
4. Python Software Foundation. math — Mathematical functions [EB/OL]. https://docs.python.org/3/library/math.html