计算ELGamal数字签名算法代码 c语言

根据提供的《ELG实验报告模板.docx》文档，以下是计算ELGamal数字签名算法的C语言代码示例：

### 计算ELGamal数字签名算法代码

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

// 快速幂取模函数
long long modExp(long long base, long long exp, long long modulus) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exp /= 2;
    }
    return result;
}

// 生成公钥和私钥
void generateKeys(long long p, long long a, long long x, long long *y) {
    *y = modExp(a, x, p);
}

// 签名算法
void signMessage(long long p, long long a, long long x, long long k, long long H_m, long long *r, long long *s) {
    *r = modExp(a, k, p);
    long long k_inv = modExp(k, p - 2, p); // k的逆元
    *s = (k_inv * (H_m + x * (*r))) % (p - 1);
}

// 验证算法
int verifySignature(long long p, long long y, long long r, long long s, long long H_m) {
    long long v1 = modExp(y, r, p);
    long long v2 = modExp(r, s, p);
    long long v = (v1 * v2) % p;
    return (v == modExp(a, H_m, p));
}

int main() {
    long long p, a, x, k, H_m, y, r, s;

    printf("请输入素数p: ");
    scanf("%lld", &p);
    printf("请输入原根a: ");
    scanf("%lld", &a);
    printf("请输入用户私钥x: ");
    scanf("%lld", &x);
    printf("请输入消息m的散列码H(m): ");
    scanf("%lld", &H_m);
    printf("请输入签名的随机数k: ");
    scanf("%lld", &k);

    // 生成公钥
    generateKeys(p, a, x, &y);
    printf("生成的公钥y: %lld\n", y);

    // 签名
    signMessage(p, a, x, k, H_m, &r, &s);
    printf("生成的签名(r, s): (%lld, %lld)\n", r, s);

    // 验证
    if (verifySignature(p, y, r, s, H_m)) {
        printf("签名验证通过！\n");
    } else {
        printf("签名验证失败！\n");
    }

    return 0;
}

### 说明
1. **快速幂取模函数 `modExp`**：用于计算 \( \text{base}^{\text{exp}} \mod \text{modulus} \)。
2. **生成公钥和私钥 `generateKeys`**：根据给定的参数生成公钥 \( y \)。
3. **签名算法 `signMessage`**：根据给定的参数生成签名 \( (r, s) \)。
4. **验证算法 `verifySignature`**：验证签名是否有效。
5. **主函数 `main`**：从用户输入获取必要参数，调用上述函数完成密钥生成、签名和验证，并输出结果。

希望这段代码对你有所帮助！如果有任何疑问，请随时提问。