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

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

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

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

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

int main(){ int p,x,m,k,g,y,r,s; printf("请输入 p, x, m, k 的值："); scanf("%d%d%d%d",&p,&x,&m,&k);

// 判断 p 是否为素数
if(!isPrime(p)){
    printf("p 不是素数，无法生成参数\n");
    return 0;
}

// 寻找生成元 g
int flag=0;
for(g=2;g<p;g++){
    int i;
    flag=1;
    for(i=1;i<p-1;i++){
        if(power(g,i,p)==1){
            flag=0;
            break;
        }
    }
    if(flag){
        break;
    }
}
if(!flag){
    printf("无法找到生成元 g\n");
    return 0;
}

// 计算公钥和私钥
y=power(g,x,p);
printf("生成元 g 为：%d\n", g);

// 计算签名
r=power(g,k,p);
int inv_k=getInverse(k,p-1);
if(inv_k==-1){
    printf("无法求出 k 的逆元\n");
    return 0;
}
printf("k 的逆元为：%d\n", inv_k);
s=(m-x*r)*inv_k%(p-1);

// 验证签名
if(power(y,r,p)*power(r,s,p)%p==power(g,m,p)){
    printf("签名有效，签名为 (%d,%d)\n",r,s);
}
else{
    printf("签名无效\n");
}

return 0;

}