ElGamal 数字签名方案：实现与验证

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

// 判断素数函数 int is_prime(int n){ if(n<=1) return 0; if(n==2) return 1; if(n%2==0) return 0; int i; for(i=3;i<=sqrt(n);i+=2){ if(n%i==0) return 0; } return 1; }

// 求 x 的 y 次方模 p 的值 int power_mod(int x,int y,int p){ int res=1; while(y>0){ if(y&1) res=(resx)%p; x=(xx)%p; y>>=1; } return res; }

// 求逆元，即满足 ax mod m=1 的 x int inv_mod(int a,int m){ int x0=0,x1=1,r0=m,r1=a,q,r; while(r1>1){ q=r0/r1; r=r0-qr1; x=(x0-q*x1)%m; r0=r1; r1=r; x0=x1; x1=x; } if(x1<0) x1+=m; return x1; }

int main(){ int p,x,m,k,g,y,r,s; printf("请输入大素数 p: "); scanf("%d",&p); if(!is_prime(p)){ printf("p 不是素数\n"); return 0; } printf("请输入私钥 x: "); scanf("%d",&x); srand(time(NULL)); do{ g=rand()%(p-1)+1; y=power_mod(g,x,p); }while(y==1); printf("公钥为 (%d,%d,%d)\n",y,g,p); printf("请输入待签消息 m: "); scanf("%d",&m); do{ k=rand()%(p-1)+1; }while(k==x); r=power_mod(g,k,p); s=(m-x*r)inv_mod(k,p-1)%(p-1); printf("签名为 (%d,%d)\n",r,s); int h=0; printf("请输入待验证消息 m: "); scanf("%d",&m); printf("请输入签名值 (r,s): "); scanf("%d%d",&r,&s); if(r<=0||r>=p||s<=0||s>=p-1){ printf("签名无效\n"); return 0; } h=m; int v1=power_mod(y,r,p); int v2=power_mod(r,s,p); int v=(v1v2)%p; int u=power_mod(g,h,p); if(v==u){ printf("签名有效\n"); }else{ printf("签名无效\n"); } return 0; }