仿射密码

什么是仿射密码？

仿射密码是一种替换密码（Substitution Cipher），它是凯撒密码的扩展，引入了更为复杂的数学运算。与凯撒密码仅仅通过加法进行位移不同，仿射密码结合了乘法和加法的线性变换。其核心在于将字母表中的每个字母映射到一个数值（通常A=0，B=1，…，Z=25），然后通过一个仿射函数进行变换，最后再将变换后的数值映射回字母。

仿射密码的数学表示

仿射密码的加密和解密过程都可以用数学语言精确地描述。我们将字母表中的每个字母映射为一个数字（例如，A=0, B=1, …, Z=25）。

加密函数

仿射密码的加密函数定义为：

$$E(x) = (ax + b) \pmod{m}$$

其中：

x 代表明文字母对应的数值（0到 m-1）。
a 和 b 是密钥，其中 a 必须与 m 互质（即它们的最大公约数为1）。
m 是字母表中的字母数量，对于英文字母表，m 通常取26。
E(x) 代表密文字母对应的数值。

互质条件的重要性： a 与 m 互质是仿射密码能够成功解密的必要条件。如果 a 和 m 不互质，那么在加密过程中可能会出现不同的明文字母加密后得到相同的密文字母的情况，导致解密时无法唯一确定原始明文，从而无法正确解密。

解密函数

解密是加密的逆过程。为了从密文 y 恢复明文 x，我们需要找到加密函数 E(x) = (ax + b) mod m 的逆函数。从加密函数可以推导出：

$$y \equiv ax + b \pmod{m}$$ $$y - b \equiv ax \pmod{m}$$

为了解出 x，我们需要找到 a 在模 m 意义下的乘法逆元 a^-1，即满足 (a * a^-1) mod m = 1 的 a^-1。只有当 a 与 m 互质时，a^-1 才存在。

解密函数定义为：

$$D(y) = a^{-1}(y - b) \pmod{m}$$

其中：

y 代表密文字母对应的数值。
a^-1 是 a 在模 m 意义下的乘法逆元。
b 是加密时使用的密钥 b。
D(y) 代表解密后明文字母对应的数值。

寻找乘法逆元： 乘法逆元 a^-1 可以通过扩展欧几里得算法或穷举法（对于较小的 m 值，如26）来找到。例如，当 m=26 时，与26互质的 a 值有1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25。每个 a 值都有其对应的唯一乘法逆元。

示例

假设我们使用英文字母表（m=26），密钥 a=5，b=8。由于5和26互质，这是一个有效的密钥对。

加密“HELLO”：

将明文字母转换为数值： H -> 7 E -> 4 L -> 11 L -> 11 O -> 14
应用加密函数 E(x) = (5x + 8) mod 26： H: E(7) = (57 + 8) mod 26 = (35 + 8) mod 26 = 43 mod 26 = 17 -> R E: E(4) = (54 + 8) mod 26 = (20 + 8) mod 26 = 28 mod 26 = 2 -> C L: E(11) = (511 + 8) mod 26 = (55 + 8) mod 26 = 63 mod 26 = 11 -> L L: E(11) = (511 + 8) mod 26 = (55 + 8) mod 26 = 63 mod 26 = 11 -> L O: E(14) = (5*14 + 8) mod 26 = (70 + 8) mod 26 = 78 mod 26 = 0 -> A
加密后的密文是 RCLLA。

解密“RCLLA”：

首先找到 a=5 在模26下的乘法逆元 a^-1。我们需要找到一个数 x 使得 5x mod 26 = 1。通过计算可知 5 * 21 = 105，105 mod 26 = 1，所以 a^-1 = 21。
将密文字母转换为数值： R -> 17 C -> 2 L -> 11 L -> 11 A -> 0
应用解密函数 D(y) = 21(y - 8) mod 26： R: D(17) = 21(17 - 8) mod 26 = 21 * 9 mod 26 = 189 mod 26 = 7 -> H C: D(2) = 21(2 - 8) mod 26 = 21 * (-6) mod 26 = -126 mod 26 = 10 * 26 - 126 mod 26 = 4 -> E L: D(11) = 21(11 - 8) mod 26 = 21 * 3 mod 26 = 63 mod 26 = 11 -> L L: D(11) = 21(11 - 8) mod 26 = 21 * 3 mod 26 = 63 mod 26 = 11 -> L A: D(0) = 21(0 - 8) mod 26 = 21 * (-8) mod 26 = -168 mod 26 = 10 * 26 - 168 mod 26 = 260 - 168 mod 26 = 92 mod 26 = 14 -> O
解密后的明文是 HELLO。

C++ 代码实现

#include <iostream>
#include <string>
#include <cctype>
#include <numeric>

int modInverse(int a, int m) {
    a = a % m;
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1) {
            return x;
        }
    }
    return -1;
}

bool isCoprime(int a) {
    return std::gcd(a, 26) == 1;
}

std::string encryptAffine(const std::string& text, int a, int b) {
    std::string result = "";
    for (char c : text) {
        if (isalpha(c)) {
            char base = islower(c) ? 'a' : 'A';
            int x = c - base;
            result += static_cast<char>(((a * x + b) % 26) + base);
        } else {
            result += c;
        }
    }
    return result;
}

std::string decryptAffine(const std::string& text, int a, int b) {
    std::string result = "";
    int a_inv = modInverse(a, 26);
    if (a_inv == -1) {
        // This case should ideally be handled before calling decrypt
        return "Error: Modular inverse does not exist. 'a' must be coprime to 26.";
    }

    for (char c : text) {
        if (isalpha(c)) {
            char base = islower(c) ? 'a' : 'A';
            int y = c - base;
            // (y - b) might be negative, add 26 to make it positive before modulo
            result += static_cast<char>(((a_inv * (y - b + 26)) % 26) + base);
        } else {
            result += c;
        }
    }
    return result;
}

int main() {
    std::string text;
    int a, b;

    std::cout << "请输入要加密的文本: ";
    std::getline(std::cin, text);

    std::cout << "请输入参数 a (必须与 26 互质，例如 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25): ";
    std::cin >> a;

    // Validate 'a'
    while (!isCoprime(a % 26)) {
        std::cout << "参数 a 必须与 26 互质。请重新输入: ";
        std::cin >> a;
    }
    a = a % 26;

    std::cout << "请输入参数 b (0-25): ";
    std::cin >> b;
    b = b % 26;

    std::string encrypted_text = encryptAffine(text, a, b);
    std::cout << "加密后的文本: " << encrypted_text << std::endl;

    std::string decrypted_text = decryptAffine(encrypted_text, a, b);
    std::cout << "解密后的文本: " << decrypted_text << std::endl;

    return 0;
}

如何破解仿射密码？

仿射密码的安全性非常低，因为它存在致命的弱点。主要有两种破解方法：

1. 暴力破解 (Brute-force Attack)

仿射密码的密钥由两个部分组成：a 和 b。对于26个英文字母的字母表（m=26），a 必须与26互质。与26互质的数有12个（1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25）。b 可以是0到25之间的任意整数，有26种可能。因此，仿射密码的总密钥空间大小为 12 * 26 = 312。相较于现代密码学中动辄上百位的密钥长度，312种密钥组合是一个非常小的数字，这使得仿射密码极易受到暴力破解攻击。

攻击者可以简单地将所有可能的密钥组合全部尝试一遍，直到解密出的文本有意义为止。这个过程对于计算机来说是瞬时完成的。

2. 频率分析 (Frequency Analysis)

仿射密码属于单表替换密码的范畴，这意味着明文中的每一个特定字母，在加密过程中都会被唯一地替换为密文中的一个特定字母。在任何一种自然语言中，不同字母的出现频率是有统计规律的。例如，在英语中，字母 E 的出现频率最高，其次是 T, A, O 等。

攻击者可以统计密文中每个字母的出现频率，找到出现次数最多的那个密文字母。它有极大的概率对应明文中的 E。一旦确定了这一对映射关系，就可以结合数学原理推算出密钥 a 和 b，从而破解整个密码。

仿射密码的特点与应用

仿射密码作为古典密码的一种，具有其独特的特点，这些特点也决定了其在现代密码学中的地位和应用场景。

特点

单表替换密码： 仿射密码属于单表替换密码的范畴，明文中的每一个特定字母，在加密过程中都会被唯一地替换为密文中的一个特定字母。这种一对一的映射关系是单表替换密码的显著特征。
与凯撒密码的关系： 凯撒密码可以看作是仿射密码的一种特殊情况。当仿射密码的密钥 a=1 时，加密函数变为 E(x) = (1 * x + b) mod m = (x + b) mod m，这正是凯撒密码的加密函数。因此，凯撒密码是仿射密码的一个子集。

应用

尽管仿射密码在现代通信中不再用于保护敏感信息，但它在密码学教育和入门领域仍有其价值：

密码学教学： 仿射密码是理解古典密码原理、加密解密过程以及密钥概念的优秀教学工具。通过学习仿射密码，学生可以直观地了解替换密码的工作方式，以及模运算在密码学中的应用。
频率分析演示： 仿射密码是演示频率分析攻击原理的理想示例。教师可以通过仿射密码的加密和解密过程，向学生展示如何利用语言的统计特性来破解简单的替换密码。
编程实践： 实现仿射密码的加密和解密算法是初学者进行密码学编程实践的良好起点。这有助于培养编程技能，并加深对密码学算法的理解。
历史研究： 作为古典密码的一部分，仿射密码在密码学发展史上占有一席之地。研究仿射密码有助于了解密码学从简单替换到复杂算法的演变过程。

总而言之，仿射密码虽然在实际应用中已不再具备安全性，但其在密码学教育和历史研究中仍然发挥着重要的作用，为我们理解更复杂的加密技术提供了基础。

总结

仿射密码作为古典密码学中的一个重要组成部分，以其简洁的数学原理和直观的加密过程，为我们理解密码学的基本概念提供了宝贵的视角。它通过线性函数 E(x) = (ax + b) mod m 将明文转换为密文，并通过其逆函数 D(y) = a^-1(y - b) mod m 进行解密。其中，密钥 a 与字母表大小 m 互质是确保可逆性的关键条件。

尽管仿射密码在现代密码学中因其极小的密钥空间和易受频率分析攻击的弱点而不再具备实际的安全性，但它在密码学教育、历史研究以及编程实践中仍然扮演着不可或缺的角色。通过学习和实现仿射密码，我们不仅能够掌握古典密码的基本原理，还能为理解更复杂的加密算法和现代密码学奠定坚实的基础。

从凯撒密码到仿射密码，再到更复杂的加密技术，密码学的发展史是一部不断演进的攻防史。每一次加密技术的进步都伴随着破解技术的突破，反之亦然。仿射密码正是这一演进过程中的一个重要里程碑，它以其独特的数学美感和历史意义，继续在密码学领域中闪耀着光芒。