未知密钥下Affine密码暴力破解解密问题求助

我明白你现在的困扰——暴力破解Affine密码时，因为没搞懂a_inverse（a的乘法逆元）怎么实现，导致解密出来全是无意义内容。其实核心问题就出在你没用到正确的解密公式，咱们一步步拆解解决：

首先搞懂Affine的正确解密逻辑 #

Affine加密公式是：
c = (a * p + b) mod 26
其中c是密文，p是明文，a和26必须互质（即gcd(a,26)=1，合法的a值只有：1,3,5,7,9,11,15,17,19,21,23,25），b是0-25的整数。

对应的解密公式必须用到a的乘法逆元a_inverse，也就是满足(a * a_inverse) mod 26 = 1的数，解密公式是：
p = (a_inverse * (c - b)) mod 26

注意：这里的模运算要处理负数情况，比如(c - b)可能为负，需要加26再取模保证结果在0-25之间。

暴力破解场景下怎么计算a的逆元 #

因为模26的范围很小，完全可以用两种简单方式实现：

• 提前预存合法a的逆元：直接把所有合法a对应的逆元存成数组，比如：

  a	a_inverse
  1	1
  3	9
  5	21
  7	15
  9	3
  11	19
  15	7
  17	23
  19	11
  21	5
  23	17
  25	25

• 实时暴力计算逆元：对每个合法的a，遍历x从1到25，找到满足(a * x) % 26 == 1的x，就是它的逆元。这种方式更灵活，不需要硬编码数组。

修改后的C++代码示例 #

下面是调整后的代码，加入逆元计算和正确的解密逻辑：

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

using namespace std;

// 计算a在模26下的逆元
int findInverse(int a) {
    for (int x = 1; x < 26; x++) {
        if ((a * x) % 26 == 1) {
            return x;
        }
    }
    return -1; // 不合法的a（和26不互质），返回-1
}

// 用给定的a和b解密密文
string affineDecrypt(string ciphertext, int a, int b) {
    string plaintext = "";
    int a_inv = findInverse(a);
    if (a_inv == -1) {
        return ""; // a不合法，返回空
    }
    for (char c : ciphertext) {
        // 处理大写字母，转成0-25的数值
        if (isupper(c)) {
            int c_val = c - 'A';
            // 应用解密公式，处理负数情况
            int p_val = (a_inv * (c_val - b)) % 26;
            if (p_val < 0) {
                p_val += 26;
            }
            plaintext += (char)(p_val + 'A');
        } else {
            // 非字母直接保留
            plaintext += c;
        }
    }
    return plaintext;
}

int main() {
    string ciphertext;
    cout << "输入密文（大写字母）：";
    cin >> ciphertext;

    // 遍历所有合法的a值（和26互质）
    int valid_a[] = {1,3,5,7,9,11,15,17,19,21,23,25};
    int num_valid_a = sizeof(valid_a)/sizeof(valid_a[0]);

    cout << "\n所有可能的解密结果：\n";
    for (int i = 0; i < num_valid_a; i++) {
        int a = valid_a[i];
        for (int b = 0; b < 26; b++) {
            string plaintext = affineDecrypt(ciphertext, a, b);
            cout << "a=" << a << ", b=" << b << ": " << plaintext << endl;
        }
    }

    return 0;
}

为什么你的原代码会失败 #

大概率是你没有使用逆元，而是尝试直接用(c - b)/a这种错误的方式解密——模运算里没有普通的除法，必须用乘法逆元来替代，否则计算出来的数值完全不对，自然解密出乱码。

现在运行上面的代码，遍历所有合法的密钥组合后，你只需要找输出里有意义的明文（比如通顺的英文句子），那就是正确的解密结果了。

内容的提问来源于stack exchange，提问作者JHk1821