c++实现EIGamal算法

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

#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;
    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;
    cout << "Enter the message m (0 < m < p-1): ";
    cin >> m;
    r = modExp(g, k, p);
    s = (m - x*r) * pow(k, -1) % (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)。最后，我们验证签名是否有效。

需要注意的是，这里的modExp函数是用来计算模幂的。同时，为了简化代码，我们假设k有一个逆元，因此可以直接使用pow(k, -1)来计算k的逆元。在实际应用中，需要注意不要使用没有逆元的k值。