c++实现ElGamal算法

ElGamal算法是一种非对称加密算法，可以用于数据加密和数字签名。下面是使用C++实现ElGamal算法的示例代码：

#include <iostream>
#include <cmath>

using namespace std;

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

int modExp(int base, int exponent, int modulus) {
    int result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

int main() {
    int p, g, x, y, k, m, r, s, inverseK;
    cout << "Enter the value of p: ";
    cin >> p;
    cout << "Enter the value of g: ";
    cin >> g;
    cout << "Enter the value of x: ";
    cin >> x;
    y = modExp(g, x, p);
    cout << "Public key (p, g, y): (" << p << ", " << g << ", " << y << ")" << endl;
    cout << "Enter the value of k (0 < k < p-1): ";
    cin >> k;
    inverseK = 0;
    while (inverseK < 1 || inverseK > p - 2) {
        cout << "Enter the value of inverse k (1 < k < p-1): ";
        cin >> inverseK;
    }
    cout << "Enter the message m (0 < m < p-1): ";
    cin >> m;
    r = modExp(g, k, p);
    s = (m - x*r) * inverseK % (p - 1);
    if (s < 0) {
        s += p - 1;
    }
    cout << "Signature (r, s): (" << r << ", " << s << ")" << endl;
    int v1 = modExp(y, r, p) * modExp(r, s, p) % p;
    int v2 = modExp(g, m, p);
    if (v1 == v2) {
        cout << "Signature is valid" << endl;
    } else {
        cout << "Signature is invalid" << endl;
    }
    return 0;
}

在这个示例中，我们输入了p、g和x，然后计算出公钥(y)。我们还要求输入k和m，然后计算出签名(r, s)。与EIGamal算法不同的是，我们还需要输入k的逆元(inverseK)。最后，我们验证签名是否有效。

需要注意的是，这里的modExp函数是用来计算模幂的。同时，我们在输入inverseK时，需要确保它在1到p-2之间，以确保它有一个逆元。在实际应用中，还需要注意选择合适的p、g和k值。