elgamal签名算法c++

以下是C++实现的ElGamal签名算法：

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

using namespace std;

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

int power(int x, unsigned int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

void generate_keypair(int& p, int& g, int& x, int& y) {
    srand(time(nullptr));
    while (true) {
        p = rand() % 100 + 1; // 生成一个100以内的质数
        bool is_prime = true;
        for (int i = 2; i <= sqrt(p); i++) {
            if (p % i == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime)
            break;
    }

    // 生成一个1到p-1之间的随机数作为g
    g = rand() % (p - 1) + 1;
    while (power(g, p - 1, p) != 1)
        g = rand() % (p - 1) + 1;

    // 生成一个1到p-2之间的随机数作为x
    x = rand() % (p - 2) + 1;

    y = power(g, x, p);
}

vector<int> sign(string message, int p, int g, int x) {
    vector<int> signature(2);
    srand(time(nullptr));
    int k = rand() % (p - 2) + 1;
    int r = power(g, k, p);
    int m = stoi(message);
    int inv_k = 0;
    while (true) {
        inv_k = gcd(k, p - 1);
        if (inv_k != 1) {
            k = rand() % (p - 2) + 1;
            r = power(g, k, p);
        } else
            break;
    }
    int s = ((m - x * r) * power(k, p - 2, p - 1)) % (p - 1);
    signature[0] = r;
    signature[1] = s;
    return signature;
}

bool verify(string message, vector<int> signature, int p, int g, int y) {
    int r = signature[0];
    int s = signature[1];
    int m = stoi(message);
    if (r < 1 || r > p - 1 || s < 1 || s > p - 2)
        return false;
    int w = power(s, p - 2, p - 1);
    int u1 = (m * w) % (p - 1);
    int u2 = (r * w) % (p - 1);
    int v1 = power(g, u1, p);
    int v2 = power(y, u2, p);
    int v = ((v1 * v2) % p) % (p - 1);
    return v == r;
}

int main() {
    int p, g, x, y;
    generate_keypair(p, g, x, y);
    cout << "p: " << p << endl;
    cout << "g: " << g << endl;
    cout << "x: " << x << endl;
    cout << "y: " << y << endl;

    string message;
    cout << "Enter a message: ";
    cin >> message;

    vector<int> signature = sign(message, p, g, x);
    cout << "Signature: (" << signature[0] << ", " << signature[1] << ")" << endl;

    bool is_valid = verify(message, signature, p, g, y);
    if (is_valid)
        cout << "Valid signature" << endl;
    else
        cout << "Invalid signature" << endl;

    return 0;
}

注：此代码仅供学习和参考使用，不能用于任何商业用途。