elgamal签名算法代码C语言

以下是 C 语言实现的 ElGamal 签名算法代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <openssl/bn.h>

// 生成公钥和私钥
void generate_keys(BIGNUM *p, BIGNUM *g, BIGNUM *x, BIGNUM *y) {
    BIGNUM *one = BN_new();
    BN_one(one);
    // 生成私钥
    BN_rand_range(x, p);
    // 生成公钥
    BN_mod_exp(y, g, x, p, NULL);
    BN_free(one);
}

// 签名
void sign(unsigned char *m, int m_len, BIGNUM *p, BIGNUM *g, BIGNUM *x, BIGNUM *r, BIGNUM *s) {
    BIGNUM *k = BN_new();
    BIGNUM *m_int = BN_new();
    BN_bin2bn(m, m_len, m_int);
    // 生成 k
    BN_rand_range(k, p);
    // 计算 r = g^k mod p
    BN_mod_exp(r, g, k, p, NULL);
    // 计算 s = (m - x*r) * k^-1 mod (p-1)
    BIGNUM *temp1 = BN_new();
    BIGNUM *temp2 = BN_new();
    BN_mod_mul(temp1, x, r, p, NULL);
    BN_mod_sub(temp2, m_int, temp1, p, NULL);
    BN_mod_inverse(temp1, k, p-1, NULL);
    BN_mod_mul(s, temp2, temp1, p-1, NULL);
    BN_free(k);
    BN_free(m_int);
    BN_free(temp1);
    BN_free(temp2);
}

// 验证签名
int verify(unsigned char *m, int m_len, BIGNUM *p, BIGNUM *g, BIGNUM *y, BIGNUM *r, BIGNUM *s) {
    int valid = 0;
    BIGNUM *v1 = BN_new();
    BIGNUM *v2 = BN_new();
    BIGNUM *m_int = BN_new();
    BN_bin2bn(m, m_len, m_int);
    // 计算 v1 = g^m mod p
    BN_mod_exp(v1, g, m_int, p, NULL);
    // 计算 v2 = (y^r * r^s) mod p
    BIGNUM *temp1 = BN_new();
    BIGNUM *temp2 = BN_new();
    BN_mod_exp(temp1, y, r, p, NULL);
    BN_mod_exp(temp2, r, s, p, NULL);
    BN_mod_mul(temp1, temp1, temp2, p, NULL);
    // 验证 v1 == v2
    valid = BN_cmp(v1, temp1) == 0;
    BN_free(v1);
    BN_free(v2);
    BN_free(m_int);
    BN_free(temp1);
    BN_free(temp2);
    return valid;
}

// 示例
int main() {
    // 初始化 OpenSSL 大数库
    BN_CTX *ctx = BN_CTX_new();
    BIGNUM *p = BN_new();
    BIGNUM *g = BN_new();
    BIGNUM *x = BN_new();
    BIGNUM *y = BN_new();
    BIGNUM *r = BN_new();
    BIGNUM *s = BN_new();
    BN_hex2bn(&p, "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
                    "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
                    "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
                    "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF");
    BN_set_word(g, 2);
    unsigned char message[] = "Hello, world!";
    int message_len = strlen((char*)message);
    generate_keys(p, g, x, y);
    sign(message, message_len, p, g, x, r, s);
    printf("Signature: (r=");
    BN_print_fp(stdout, r);
    printf(", s=");
    BN_print_fp(stdout, s);
    printf(")\n");
    if (verify(message, message_len, p, g, y, r, s)) {
        printf("Signature is valid.\n");
    } else {
        printf("Signature is invalid.\n");
    }
    // 释放资源
    BN_free(p);
    BN_free(g);
    BN_free(x);
    BN_free(y);
    BN_free(r);
    BN_free(s);
    BN_CTX_free(ctx);
    return 0;
}

在示例中，我们使用了 OpenSSL 的大数库来进行精确计算，使用了一个 1024 位的质数 `p`，基于 `g=2` 的 ElGamal 签名算法进行了签名，并验证了签名的有效性。