ElGamal 数字签名方案：原理、C语言实现及验证

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

int is_prime(int n) { // 判断n是否为素数 if (n < 2) return 0; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return 0; } return 1; }

int gcd(int a, int b) { // 求a和b的最大公约数 if (b == 0) return a; return gcd(b, a % b); }

int pow_mod(int a, int b, int m) { // 求a的b次方对m取模 int res = 1; while (b > 0) { if (b & 1) res = (long long)res * a % m; a = (long long)a * a % m; b >>= 1; } return res; }

int inv(int a, int m) { // 求a在模m意义下的逆元 int x, y; int gcd_res = gcd(a, m, &x, &y); if (gcd_res != 1) return -1; // a和m不互质，不存在逆元 return (x % m + m) % m; }

int main() { // 输入p int p; printf("请输入大素数p："); scanf("%d", &p); if (!is_prime(p)) { printf("p不是素数！\n"); return 0; }

// 输入x
int x;
printf("请输入私钥x：");
scanf("%d", &x);

// 计算公钥y和生成元g
srand((unsigned)time(NULL));
int g;
while (1) {
    g = rand() % (p - 1) + 1;
    if (pow_mod(g, p - 1, p) == 1) continue; // 如果g不是p的原根，重新选择
    break;
}
int y = pow_mod(g, x, p);
printf("公钥为（%d，%d，%d），私钥为%d\n", y, g, p, x);

// 输入消息m
int m;
printf("请输入待签消息m：");
scanf("%d", &m);

// 选择随机数k
int k;
while (1) {
    k = rand() % (p - 1) + 1;
    if (gcd(k, p - 1) != 1) continue; // 如果k不和p-1互质，重新选择
    break;
}

// 计算签名
int r = pow_mod(g, k, p);
int s = (long long)(m - x * r) * inv(k, p - 1) % (p - 1);
printf("签名为（%d，%d）\n", r, s);

// 验证签名
int h = m; // 假设哈希函数为恒等映射
int lhs = pow_mod(y, r, p) * pow_mod(r, s, p) % p;
int rhs = pow_mod(g, h, p);
if (lhs == rhs) {
    printf("签名有效！\n");
} else {
    printf("签名无效！\n");
}

return 0;

}