用c语言实现elgamal签名，设p=11,g=2,x=8,实现：alice对消息m=5的签名，bob对以上签名进行验证

以下是使用C语言实现ElGamal签名的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 模重复平方算法
int mod_pow(int base, int exponent, int mod) {
    int res = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return res;
}

// 求解逆元
int mod_inv(int a, int mod) {
    int b = mod, x = 0, y = 1;
    while (a > 0) {
        int q = b / a;
        int t = a; a = b % a; b = t;
        t = x; x = y - q * x; y = t;
    }
    if (b == 1) {
        return (y + mod) % mod;
    } else {
        return -1; // 不存在逆元
    }
}

// ElGamal签名
void elgamal_sign(int p, int g, int x, int m, int *r, int *s) {
    int k = rand() % (p - 2) + 1; // 随机选择k
    *r = mod_pow(g, k, p);
    int k_inv = mod_inv(k, p - 1);
    *s = ((m - x * (*r)) * k_inv) % (p - 1);
}

// ElGamal验证
int elgamal_verify(int p, int g, int y, int m, int r, int s) {
    int v1 = mod_pow(y, r, p) * mod_pow(r, s, p) % p;
    int v2 = mod_pow(g, m, p);
    return v1 == v2;
}

int main() {
    srand(time(NULL)); // 初始化随机数种子

    int p = 11, g = 2, x = 8, m = 5;
    int y = mod_pow(g, x, p); // 计算公钥y

    // Alice对消息m进行签名
    int r, s;
    elgamal_sign(p, g, x, m, &r, &s);
    printf("Alice's signature: (%d, %d)\n", r, s);

    // Bob验证Alice的签名
    int is_valid = elgamal_verify(p, g, y, m, r, s);
    if (is_valid) {
        printf("Bob verifies Alice's signature successfully!\n");
    } else {
        printf("Bob fails to verify Alice's signature!\n");
    }

    return 0;
}

上述代码中，`mod_pow`函数实现了模重复平方算法，`mod_inv`函数实现了求解逆元的扩展欧几里得算法。`elgamal_sign`函数用于进行ElGamal签名，其中随机选择了一个私钥`k`，并计算出签名中的`r`和`s`。`elgamal_verify`函数用于验证签名的正确性。

在主函数中，首先计算出公钥`y`，然后Alice对消息`m`进行签名，Bob通过公钥`y`和签名中的`r`和`s`来验证签名的正确性。