ElGamal 数字签名方案 - C 语言实现

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

int isPrime(int n); // 判断n是否为素数 int powerMod(int a, int b, int n); // 模幂运算，计算a^b mod n int gcd(int a, int b); // 求a和b的最大公因数 int inverse(int a, int n); // 求a在模n下的逆元 int sign(int m, int p, int x, int k); // 数字签名 int verify(int m, int p, int y, int g, int r, int s); // 验证数字签名

int main() { int p, x, m, k; printf("请输入p,x,m,k的值：\n"); scanf("%d %d %d %d", &p, &x, &m, &k); if (!isPrime(p)) { printf("p不是素数\n"); return 0; } int g = 2; while (powerMod(g, (p - 1) / 2, p) == 1 || powerMod(g, 2, p) == 1) { // 寻找生成元g g++; } printf("生成元g=%d\n", g); int kInv = inverse(k, p - 1); // 求k的逆元 printf("k的逆元为%d\n", kInv); int y = powerMod(g, x, p); printf("公开密钥y=%d\n", y); int r = powerMod(g, k, p); int h = m; int xr = (long long)x * r % (p - 1); int s = (h - xr + (p - 1)) % (p - 1) * kInv % (p - 1); printf("数字签名为(%d,%d)\n", s, r); if (verify(m, p, y, g, r, s)) { printf("数字签名有效\n"); } else { printf("数字签名无效\n"); } return 0; }

int isPrime(int n) { if (n <= 1) { return 0; } int i; for (i = 2; i * i <= n; i++) { if (n % i == 0) { return 0; } } return 1; }

int powerMod(int a, int b, int n) { int res = 1; while (b) { if (b & 1) { res = (long long)res * a % n; } a = (long long)a * a % n; b >>= 1; } return res; }

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int inverse(int a, int n) { int t = 0, newT = 1; int r = n, newR = a; while (newR != 0) { int quotient = r / newR; int tmpT = newT; newT = t - quotient * newT; t = tmpT; int tmpR = newR; newR = r - quotient * newR; r = tmpR; } if (r > 1) { return -1; } if (t < 0) { t += n; } return t; }

int sign(int m, int p, int x, int k) { int g = 2; while (powerMod(g, (p - 1) / 2, p) == 1 || powerMod(g, 2, p) == 1) { g++; } int kInv = inverse(k, p - 1); int y = powerMod(g, x, p); int r = powerMod(g, k, p); int h = m; int xr = (long long)x * r % (p - 1); int s = (h - xr + (p - 1)) % (p - 1) * kInv % (p - 1); return s << 16 | r; // 将s和r合并为一个整数返回 }

int verify(int m, int p, int y, int g, int r, int s) { if (r <= 0 || r >= p || s <= 0 || s >= p - 1) { return 0; } int w = inverse(s, p - 1); int h = m; int u1 = (long long)h * w % (p - 1); int u2 = (long long)r * w % (p - 1); int v1 = powerMod(g, u1, p); int v2 = powerMod(y, u2, p); int vr = (long long)v1 * v2 % p; int vs = powerMod(g, h, p); return vr == vs;