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

Elgamal算法是一种非对称加密算法，其基于离散对数问题。该算法的安全性取决于大素数的难度和离散对数问题的难度。下面是使用C++实现Elgamal算法对文本进行加密的示例代码，附有详细的注释：

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

using namespace std;

// 欧拉函数，计算 φ(p)
int Euler(int p){
    int ans = p;
    for (int i = 2; i <= sqrt(p); i++) {
        if (p % i == 0) {
            ans = ans / i * (i - 1); // 根据欧拉函数的定义，计算每个质因子的贡献
            while (p % i == 0) p /= i;
        }
    }
    if (p > 1) ans = ans / p * (p - 1); // 处理最后一个质因子
    return ans;
}

// 快速幂算法
int QuickPow(int a, int b, int p){
    int ans = 1 % p;
    while (b) {
        if (b & 1) ans = (long long)ans * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    return ans;
}

// 扩展欧几里得算法，用于求解 ax + by = 1 的整数解
// 返回值为 gcd(a, b)，x 和 y 的值通过指针返回
int ExGCD(int a, int b, int &x, int &y){
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int gcd = ExGCD(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

// Elgamal算法加密函数
void Elgamal_Encrypt(int p, int a, int k, int y, const char *plaintext, int *ciphertext){
    // plaintext：明文，ciphertext：密文，p、a、k、y：公钥，k 为私钥
    // 计算 φ(p)
    int phi = Euler(p);
    int len = strlen(plaintext);
    for (int i = 0; i < len; i++) {
        // 对每个字符进行加密
        int m = plaintext[i];
        // 随机选择一个整数 r
        int r = rand() % (p - 2) + 2; // r 属于 [2, p-1)，即 r 取值范围为 2~p-2
        // 计算 c1 和 c2
        int c1 = QuickPow(a, r, p);
        int c2 = (long long)m * QuickPow(y, r, p) % p;
        ciphertext[i * 2] = c1;
        ciphertext[i * 2 + 1] = c2;
    }
}

// Elgamal算法解密函数
void Elgamal_Decrypt(int p, int a, int x, const int *ciphertext, int len, char *plaintext){
    // ciphertext：密文，plaintext：明文，p、a、x：私钥
    for (int i = 0; i < len; i++) {
        // 对每个密文块进行解密
        int c1 = ciphertext[i * 2];
        int c2 = ciphertext[i * 2 + 1];
        // 计算 m = c2 * c1^(-x) mod p
        int invc1 = ExGCD(c1, p, invc1, invc1);
        invc1 = (invc1 % p + p) % p;
        int m = (long long)c2 * QuickPow(invc1, x, p) % p;
        plaintext[i] = m;
    }
}

int main(){
    // 选择一个大素数 p 和原根 a
    int p = 9973, a = 5;
    // 计算 φ(p) 和随机选择一个整数 k 作为私钥
    int phi = Euler(p), k = 233;
    // 计算公钥 y
    int y = QuickPow(a, k, p);
    // 显示公钥和私钥
    cout << "公钥为 (" << p << ", " << a << ", " << y << ")" << endl;
    cout << "私钥为 " << k << endl;

    // 加密测试
    const char *plaintext = "Hello, world!";
    int len = strlen(plaintext);
    int *ciphertext = new int[len * 2];
    Elgamal_Encrypt(p, a, k, y, plaintext, ciphertext); // 加密
    cout << "加密后的密文为：";
    for (int i = 0; i < len * 2; i++) {
        cout << ciphertext[i] << " ";
    }
    cout << endl;

    // 解密测试
    char *decryptedtext = new char[len];
    Elgamal_Decrypt(p, a, k, ciphertext, len, decryptedtext); // 解密
    decryptedtext[len] = '\0';
    cout << "解密后的明文为：" << decryptedtext << endl;

    return 0;
}

以上是使用C++实现Elgamal算法对文本进行加密的示例代码。需要注意的是，该示例代码仅用于学习和研究目的，实际使用中还需要考虑到一些安全性问题，例如如何选择合适的参数、如何保护私钥等。