c++编程实现Elgamal算法对文本进行加密并加上详细注释

Elgamal算法是一种公钥加密算法，它的安全性基于离散对数问题。下面是使用C++实现Elgamal算法对文本进行加密的示例代码，注释详细，希望对你有帮助。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int expmod(int a, int b, int n) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % n;
        a = (a * a) % n;
        b >>= 1;
    }
    return res;
}

int main() {
    srand(time(NULL));

    // 1. 选择p和g
    int p = 23, g = 5;
    cout << "p = " << p << ", g = " << g << endl;

    // 2. 随机选择私钥x
    int x = rand() % (p - 2) + 1;
    cout << "私钥x = " << x << endl;

    // 3. 计算公钥y
    int y = expmod(g, x, p);
    cout << "公钥y = " << y << endl;

    // 4. 加密过程
    string plain_text;
    cout << "请输入需要加密的明文: ";
    getline(cin, plain_text);
    int len = plain_text.length();
    int *cipher_text = new int[len];

    for (int i = 0; i < len; i++) {
        int k = rand() % (p - 2) + 1;
        int c1 = expmod(g, k, p);
        int c2 = (expmod(y, k, p) * (int)plain_text[i]) % p;
        cipher_text[i] = c2;
        cout << plain_text[i] << " -> (" << c1 << ", " << c2 << ")" << endl;
    }

    // 5. 解密过程
    string decrypted_text;
    for (int i = 0; i < len; i++) {
        int m = (cipher_text[i] * expmod(expmod(cipher_text[i], p - 1 - x, p), p - 2, p)) % p;
        decrypted_text.push_back((char)m);
    }
    cout << "解密后的明文: " << decrypted_text << endl;

    delete[] cipher_text;
    return 0;
}

注释解释：

1. 选择一个大质数p和一个原根g。

2. 随机选取一个私钥x。

3. 计算公钥y，y=g^x mod p。

4. 加密过程：对于明文中的每一个字符，随机选取一个整数k，计算密文c1=g^k mod p，c2=m*y^k mod p，其中m是明文字符的ASCII码值。密文为(c1, c2)。

5. 解密过程：对于密文(c1, c2)，计算m=c2*(c1^(-x)) mod p，其中x是私钥。还原出明文。