Kasiski测试法的代码

以下是基于C++编写的Kasiski测试法代码，用于破解维吉尼亚密码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

// 计算两个字符串的最长公共子串
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算两个字符串的最长公共子串
int gcd(string a, string b) {
    int len1 = a.length();
    int len2 = b.length();
    int len = min(len1, len2);
    for (int i = 0; i < len; i++) {
        if (a[i] != b[i]) {
            return gcd(i, len1 - (i + 1)) + 1;
        }
    }
    return gcd(len, abs(len1 - len2));
}

// 计算字符串中所有可能的重复序列和距离
vector<pair<string, int>> get_repeating_sequences(string text, int min_len) {
    vector<pair<string, int>> sequences;
    for (int len = min_len; len < text.length(); len++) {
        for (int i = 0; i <= text.length() - len; i++) {
            string seq = text.substr(i, len);
            for (int j = i + len; j <= text.length() - len; j++) {
                if (text.substr(j, len) == seq) {
                    sequences.push_back(make_pair(seq, j - i));
                }
            }
        }
    }
    return sequences;
}

// 计算可能的秘钥长度
vector<int> get_key_lengths(string text, int min_len, int max_len) {
    vector<pair<string, int>> sequences = get_repeating_sequences(text, min_len);
    map<int, int> distances;
    for (auto seq : sequences) {
        distances[seq.second] += 1;
    }
    vector<int> key_lengths;
    for (auto dist : distances) {
        if (dist.second > 1) {
            key_lengths.push_back(dist.first);
        }
    }
    sort(key_lengths.begin(), key_lengths.end());
    vector<int> factors;
    for (auto len : key_lengths) {
        for (int i = min_len; i <= max_len; i++) {
            if (len % i == 0) {
                factors.push_back(i);
            }
        }
    }
    sort(factors.begin(), factors.end());
    auto last = unique(factors.begin(), factors.end());
    factors.erase(last, factors.end());
    return factors;
}

// 使用频率分析法破解维吉尼亚密码
string decrypt_vigenere(string text, string key) {
    string decrypted = "";
    for (int i = 0; i < text.length(); i++) {
        int ki = key[i % key.length()] - 'A';
        int ci = text[i] - 'A';
        int pi = (ci - ki + 26) % 26;
        decrypted += 'A' + pi;
    }
    return decrypted;
}

int main() {
    string ciphertext = "QOPXKMCOXZLPPVXDOHDJTFKZAZWSZJYRFDJYGVYRJQ";
    int min_len = 3;
    int max_len = 10;
    vector<int> key_lengths = get_key_lengths(ciphertext, min_len, max_len);
    for (auto len : key_lengths) {
        cout << "Possible key length: " << len << endl;
        string key = "";
        for (int i = 0; i < len; i++) {
            string column = "";
            for (int j = i; j < ciphertext.length(); j += len) {
                column += ciphertext[j];
            }
            map<char, int> freq;
            for (auto c : column) {
                freq[c] += 1;
            }
            char most_common = 'A';
            for (auto f : freq) {
                if (f.second > freq[most_common]) {
                    most_common = f.first;
                }
            }
            int ki = (most_common - 'A' + 26 - 4) % 26;
            key += 'A' + ki;
        }
        cout << "Decrypted text: " << decrypt_vigenere(ciphertext, key) << endl;
    }
    return 0;
}

在这个代码中，我们首先定义了三个函数。函数 `gcd` 用于计算两个字符串的最长公共子串，函数 `get_repeating_sequences` 用于计算字符串中所有可能的重复序列和距离，函数 `get_key_lengths` 用于计算可能的秘钥长度。

在 `main` 函数中，我们使用 `get_key_lengths` 函数计算可能的秘钥长度，对于每个秘钥长度，我们使用频率分析法破解密码并输出解密后的明文。