c++实现ElGamal

ElGamal算法是一种公钥密码体制，可以用于加密和数字签名。下面是C++实现ElGamal算法的示例代码：

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

using namespace std;

//计算a的b次方取模p的结果
int modpow(int a, int b, int p) {
    int ans = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        b /= 2;
    }
    return ans;
}

//计算a的逆元
int modinv(int a, int p) {
    return modpow(a, p - 2, p);
}

int main() {
    //选取一个大素数p
    int p = 2147483647;

    //选取一个原根g
    int g = 2;

    //选取一个私钥x
    int x = rand() % (p - 2) + 1;

    //计算公钥y
    int y = modpow(g, x, p);

    //加密明文m
    int m = 100;
    int k = rand() % (p - 2) + 1;
    int a = modpow(g, k, p);
    int b = (modpow(y, k, p) * m) % p;

    //解密密文c
    int c = modpow(a, p - 1 - x, p);
    int dm = (b * c) % p;

    cout << "p = " << p << endl;
    cout << "g = " << g << endl;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
    cout << "m = " << m << endl;
    cout << "k = " << k << endl;
    cout << "a = " << a << endl;
    cout << "b = " << b << endl;
    cout << "c = " << c << endl;
    cout << "decrypt m = " << dm << endl;

    return 0;
}

在这个示例代码中，我们选取了一个大素数p和一个原根g作为ElGamal算法的参数。首先，我们选取一个私钥x，并计算出公钥y。然后，我们选取一个随机数k，并将明文m加密成密文a和b。最后，我们解密密文c，得到明文dm。

需要注意的是，ElGamal算法的安全性依赖于离散对数问题的困难性，因此选取p和g的时候需要特别小心，以确保算法的安全性。