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

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

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

// 求逆元 int inverse(int k,int p){ int i; for(i=1;i<p;i++){ if((k*i)%p==1){ return i; } } return -1; }

// 快速幂 int fast_pow(int a,int b,int p){ int res=1; while(b){ if(b&1){ res=(resa)%p; } a=(aa)%p; b>>=1; } return res; }

// ElGamal 数字签名 void ElGamal(){ int p,x,m,k,r,s,y,g,h; printf("输入 p, x, m, k："); scanf("%d%d%d%d",&p,&x,&m,&k); // 判断 p 是否为素数 if(!is_prime(p)){ printf("p 不是素数\n"); return; } // 寻找生成元 g for(g=2;g<p;g++){ int flag=1; for(int i=1;i<p-1;i++){ if(fast_pow(g,i,p)==1){ flag=0; break; } } if(flag){ break; } } printf("生成元 g: %d\n", g); // 计算 y y=fast_pow(g,x,p); // 计算 h(m) h=m%p; // 计算 r r=fast_pow(g,k,p); // 计算 k 的逆元 int k_inv=inverse(k,p-1); if(k_inv==-1){ printf("k 没有逆元\n"); return; } printf("k 的逆元: %d\n", k_inv); // 计算 s s=(k_inv*(h-x*r))%(p-1); // 输出签名 printf("数字签名：(%d,%d)\n",r,s); // 验证签名 int left=fast_pow(y,r,p); int right=(fast_pow(g,h,p)*fast_pow(r,s,p))%p; if(left==right){ printf("数字签名有效\n"); }else{ printf("数字签名无效\n"); } }

int main(){ ElGamal(); return 0; }