基于Shamir算法的C++加解密程序解密结果不符问题求助

我用C++基于Shamir算法实现了消息加解密，但解密出的消息和输入不一致。有人觉得是编码问题，但我认为是代码里的bug，却找不到具体位置。我试过把加解密换成XOR，还加了数组排序，都没解决问题。下面是程序代码和示例输出：

#include <iostream>   
#include <cstdlib>   
#include <ctime>   
#include <vector>   
#include <string>   
#include <algorithm> // для функции sort 

using namespace std;

// Объявляем константы   
const int MAX = 1000;
const int PRIME = 31;

// Функция, вычисляющая степень числа по модулю   
int power(int x, unsigned int y, int p)
{
    int res = 1; // Инициализируем результат   
    x = x % p; // Берем остаток от деления x на p   

    while (y > 0) {
        // Если степень нечетная, умножаем результат на x   
        if (y & 1)
            res = (res * x) % p;

        // Уменьшаем степень вдвое и удваиваем x   
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

int main()
{
    string message; // Объявляем переменную для сообщения   
    cout << "Enter the message to be encrypted: ";
    getline(cin, message); // Получаем сообщение от пользователя   

    int n, k; // Объявляем переменные для количества ключей   
    cout << "Enter the number of keys (n): ";
    cin >> n;
    cout << "Enter the number of keys required for decryption (k): ";
    cin >> k;

    // Генерируем случайный секретный ключ и коэффициенты   
    int secretKey = rand() % PRIME;
    vector<int> coefficients(k - 1);
    for (int i = 0; i < k - 1; i++) {
        coefficients[i] = rand() % PRIME;
    }

    // Генерируем ключи   
    vector<int> keys(n);
    for (int i = 1; i <= n; i++) {
        keys[i - 1] = power(PRIME, i, MAX);
    }

    // Создаем части секретного сообщения   
    vector<int> shares(n);
    for (int i = 0; i < n; i++) {
        int sum = secretKey;
        for (int j = 0; j < k - 1; j++) {
            sum += coefficients[j] * power(keys[i], j + 1, MAX);
        }
        shares[i] = sum;
    }

    // Пользователь выбирает ключи для расшифровки   
    vector<int> selectedKeys(k);
    cout << "Enter the keys to be used for decryption: ";
    for (int i = 0; i < k; i++) {
        cin >> selectedKeys[i];
        if (selectedKeys[i] < 1 || selectedKeys[i] > n) { // проверка на правильность ввода ключей 
            cout << "Invalid key. Please try again: ";
            i--;
        }
    }
    sort(selectedKeys.begin(), selectedKeys.end()); // сортировка выбранных ключей 

    // Восстанавливаем секретное сообщение   
    int secretMessage = 0;
    for (int i = 0; i < k; i++) {
        int num = shares[selectedKeys[i] - 1];
        int denom = 1;
        for (int j = 0; j < k; j++) {
            if (i != j) {
                num *= keys[selectedKeys[j] - 1];
                denom *= keys[selectedKeys[j] - 1] - keys[selectedKeys[i] - 1];
            }
        }
        secretMessage += num / denom;
    }

    // Шифруем и расшифровываем сообщение   
    string encryptedMessage = "";
    string decryptedMessage = "";
    for (int i = 0; i < message.length(); i++) {
        int val = message[i];
        int encryptedVal = val ^ secretKey; // XOR-шифрование 
        encryptedMessage += char(encryptedVal);
        int decryptedVal = encryptedVal ^ secretMessage; // XOR-расшифрование 
        decryptedMessage += char(decryptedVal);
    }

    // Выводим результаты на экран   
    cout << "The secret key is: " << secretKey << endl;
    cout << "The shares are: ";
    for (int i = 0; i < n; i++) {
        cout << shares[i] << " ";
    }
    cout << endl;
    cout << "The decrypted message is: " << decryptedMessage << endl;
    cout << "The encrypted message is: " << encryptedMessage << endl;

    return 0;
}

示例输出 #

Enter the message to be encrypted: Hello World
Enter the number of keys (n): 6
Enter the number of keys required for decryption (k): 3
Enter the keys to be used for decryption: 3 2 1
The secret key is: 10
The shares are: 10302 26362 24222 15882 11342 22602
The decrypted message is: ┤ЩРРУ▄лУОРШ
The encrypted message is: Boffe*]exfn

核心错误点 #

• Shamir算法核心逻辑完全错误
  • 生成的keys是power(PRIME, i, MAX)，不符合Shamir要求：每个份额应为(x_i, f(x_i))，其中x_i是1到n的唯一整数，而非大幂次值。
  • 份额计算时用power(keys[i], j+1, MAX)作为多项式项，偏离了Shamir多项式f(x) = secretKey + a1*x + a2*x² + ... + a(k-1)*x^(k-1)的定义，且未做模PRIME运算，数值溢出严重。
• 拉格朗日插值实现错误
  • Shamir基于有限域（模素数）运算，不能直接用整数除法num / denom，必须用模逆元代替除法，直接做整数除法会导致精度丢失和结果错误。
  • 插值计算未取模，数值迅速超出int范围，导致结果完全失真。
• 未初始化随机种子
  • 使用rand()但未调用srand(time(0))，每次运行生成的密钥和系数固定，既不安全也不利于调试。
• 解密密钥混淆
  • 加密用secretKey，解密用secretMessage，但因算法错误，secretMessage无法正确恢复secretKey，导致XOR解密完全错误。

修复后的代码示例 #

#include <iostream>   
#include <cstdlib>   
#include <ctime>   
#include <vector>   
#include <string>   
#include <algorithm> 

using namespace std;

// 选择大于ASCII最大值(255)的素数，确保所有字符都能被正确处理
const int PRIME = 257;

// 模幂运算实现
int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// 费马小定理求模逆元（仅适用于素数模）
int modInverse(int a, int p)
{
    return power(a, p - 2, p);
}

// 拉格朗日插值恢复秘密密钥
int lagrangeInterpolation(const vector<pair<int, int>>& shares, int p)
{
    int k = shares.size();
    int secret = 0;
    for (int i = 0; i < k; i++) {
        int xi = shares[i].first;
        int yi = shares[i].second;
        int numerator = 1;
        int denominator = 1;
        for (int j = 0; j < k; j++) {
            if (i != j) {
                int xj = shares[j].first;
                // 计算分子：乘积(-xj)，模p处理
                numerator = (numerator * (-xj)) % p;
                // 计算分母：乘积(xi - xj)，模p处理
                denominator = (denominator * (xi - xj)) % p;
            }
        }
        // 求分母的模逆元
        int invDenominator = modInverse(denominator, p);
        // 计算当前项并累加到结果
        int term = (yi * numerator) % p;
        term = (term * invDenominator) % p;
        secret = (secret + term) % p;
    }
    // 确保结果为正整数
    if (secret < 0) secret += p;
    return secret;
}

int main()
{
    // 初始化随机种子，保证每次运行生成不同的密钥
    srand(time(0));

    string message;
    cout << "Enter the message to be encrypted: ";
    getline(cin, message);

    int n, k;
    cout << "Enter the number of keys (n): ";
    cin >> n;
    cout << "Enter the number of keys required for decryption (k): ";
    cin >> k;

    // 生成秘密密钥（对应Shamir多项式的常数项f(0)）
    int secretKey = rand() % (PRIME - 1) + 1; // 取1到PRIME-1的随机数
    vector<int> coefficients(k - 1);
    for (int i = 0; i < k - 1; i++) {
        coefficients[i] = rand() % (PRIME - 1) + 1;
    }

    // 生成n个份额：(x_i, f(x_i))，x_i从1到n
    vector<pair<int, int>> shares;
    cout << "Generated shares:" << endl;
    for (int x = 1; x <= n; x++) {
        int fx = secretKey;
        int currentPower = x;
        for (int coeff : coefficients) {
            fx = (fx + coeff * currentPower) % PRIME;
            currentPower = (currentPower * x) % PRIME;
        }
        shares.emplace_back(x, fx);
        cout << "Share " << x << ": (" << x << ", " << fx << ")" << endl;
    }

    // 用户选择k个份额用于解密
    vector<pair<int, int>> selectedShares;
    cout << "\nEnter the indices of shares to use (1-" << n << "): ";
    for (int i = 0; i < k; i++) {
        int idx;
        cin >> idx;
        if (idx < 1 || idx > n) {
            cout << "Invalid index, try again: ";
            i--;
            continue;
        }
        selectedShares.push_back(shares[idx - 1]);
    }

    // 恢复秘密密钥
    int recoveredSecret = lagrangeInterpolation(selectedShares, PRIME);
    cout << "\nOriginal secret key: " << secretKey << endl;
    cout << "Recovered secret key: " << recoveredSecret << endl;

    // 加密和解密消息（使用XOR，密钥在0-256之间，覆盖所有ASCII字符）
    string encryptedMessage, decryptedMessage;
    for (char c : message) {
        // 用unsigned char避免符号位问题
        int encryptedVal = (static_cast<unsigned char>(c) ^ secretKey) % PRIME;
        encryptedMessage += static_cast<char>(encryptedVal);
        int decryptedVal = (encryptedVal ^ recoveredSecret) % PRIME;
        decryptedMessage += static_cast<char>(decryptedVal);
    }

    cout << "\nEncrypted message: " << encryptedMessage << endl;
    cout << "Decrypted message: " << decryptedMessage << endl;

    return 0;
}

修复说明 #

1. 修正Shamir核心逻辑：使用1到n的整数作为每个份额的x值，严格按照多项式f(x) = secretKey + a1*x + a2*x² + ...生成份额，所有运算都在模PRIME下进行。
2. 正确实现拉格朗日插值：通过费马小定理计算模逆元代替整数除法，确保有限域内的运算正确性。
3. 初始化随机种子：调用srand(time(0))保证每次运行生成不同的密钥和系数。
4. 优化字符处理：使用unsigned char处理字符，避免符号位导致的错误，同时选择257作为素数，覆盖所有ASCII字符范围。

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