在不使用其他库的前提下，C++实现ELGAMAL签名和验证，代码详细 给出

以下是C++实现ELGAMAL签名和验证的示例代码，不使用其他库实现：

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

using namespace std;

// 求a^b mod p的值
int power(int a, int b, int p) {
    int res = 1;
    a %= p;
    while (b) {
        if (b & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// 求ax ≡ 1 (mod p)的x值
int inv(int a, int p) {
    int b = p, u = 1, v = 0;
    while (b) {
        int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    return (u + p) % p;
}

// 生成随机质数
int gen_prime(int l, int r) {
    int p;
    while (1) {
        p = rand() % (r - l + 1) + l;
        int flag = 1;
        for (int i = 2; i <= sqrt(p); ++i) {
            if (p % i == 0) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            return p;
        }
    }
}

// 生成大素数p和原根g
void gen_params(int& p, int& g) {
    int l = 100, r = 200;
    p = gen_prime(l, r);
    while (1) {
        int phi = p - 1;
        int cnt = 0;
        for (int i = 2; i <= sqrt(phi); ++i) {
            if (phi % i == 0) {
                if (power(2, phi / i, p) == 1) {
                    cnt = 1;
                    break;
                }
                if (power(2, i, p) == 1) {
                    cnt = 1;
                    break;
                }
            }
        }
        if (cnt) {
            p = gen_prime(l, r);
        } else {
            break;
        }
    }
    g = 2;
    while (1) {
        int flag = 1;
        for (int i = 2; i <= sqrt(p); ++i) {
            if (p % i == 0) {
                if (power(g, p / i, p) == 1) {
                    flag = 0;
                    break;
                }
            }
        }
        if (flag) {
            break;
        } else {
            ++g;
        }
    }
}

// 签名
void sign(int p, int g, int x, int& r, int& s, int m) {
    int k = rand() % (p - 2) + 1;
    r = power(g, k, p);
    int k_inv = inv(k, p - 1);
    s = ((m - x * r) % (p - 1) * k_inv % (p - 1) + p - 1) % (p - 1);
}

// 验证
bool verify(int p, int g, int y, int r, int s, int m) {
    int a = (power(y, r, p) * power(r, s, p)) % p;
    int b = power(g, m, p);
    return a == b;
}

int main() {
    srand(time(NULL));

    int p, g;
    gen_params(p, g);
    cout << "p: " << p << endl;
    cout << "g: " << g << endl;

    int x = rand() % (p - 2) + 1;
    cout << "x: " << x << endl;

    int y = power(g, x, p);
    cout << "y: " << y << endl;

    int m = rand() % 100;
    cout << "m: " << m << endl;

    int r, s;
    sign(p, g, x, r, s, m);
    cout << "r: " << r << endl;
    cout << "s: " << s << endl;

    bool flag = verify(p, g, y, r, s, m);
    if (flag) {
        cout << "验证成功" << endl;
    } else {
        cout << "验证失败" << endl;
    }

    return 0;
}

代码中实现了ELGAMAL签名和验证的基本操作，并且生成了随机的参数进行测试。在实际应用中，需要保证生成的参数足够安全，并且需要对签名和验证的消息进行合适的编码处理。需要注意的是，本代码中求逆元的方法使用的是扩展欧几里得算法。