EIGamal数字签名的实现(c++)——大三密码学实验

2023-11-15

实验原理：

1.密钥产生：Alice要对一个消息签名。她选择一个大素数p和一个本原根g。选择一个秘密整数 $1\leq x\leq p-2$ ,并且计算 $y=g^{x}(mod p)$ ,(p,g,y)公开。x秘密保存。【注：EIGamal签名方案的安全性在于x的保密性。由于离散对数学问题难解，很难由(p,g,y)确定x.】

2.数字签名：Alice签署消息m.

选择一个安全的随机数k，使得gcd(k,p-1)=1;
计算 $r\equiv g^{k}$ (mod p);
计算 $s\equiv k^{-1}$ (m-x*r)(mod p-1);
Alice签署的消息是三元组(m,r,s);

3.验证：Bob确认签名

下载Alice的公钥(p,g,y);
计算 $v1\equiv y^{r}r^{s}$ (mod p)和 $v2\equiv g ^{m}$ (mod p)；
当且仅当v1 $\equiv$ v2(mod p)时，签名是有效的。

实验内容：

1.mod函数的构造

int mod(int a,int b){
	int ans;
	while(a<0){
		a=a+b; 
	}
	ans=a%b;
	return ans;
}

虽然%能表示取与，但是当a为负数时，%就不能再适用

为此我们需要构建一个既可以处理正数也可以处理负数的mod函数

对于负数，我们需要把它变成正数，需要加模数，即a+n*b，直到a为正数，这样它就可以使用%来求得余数

2.tongyu函数的构造

int tongyu(int a,int m,int n){//递归原理 
	long long int temp=a%n,ans;
	if(m==1){
		ans=temp;
	}
	else if(m>=2){
		ans=mod((temp*tongyu(a,m-1,n)),n);
	}
	return ans;
}

即求 $a^{m}mod n$

原理是(a*b)mod c=((a mod c)*(b mod c))mod c

3.f_mod函数的构造

int f_mod(int k,int p){
	int ans;
	for(int i=1;;i++){
		ans=mod(i*k-1,p);
		if(ans==0){
			return i;
			break;
		}
	}
}

这个函数用来求分数，1/k这种形式的分数对p的余数

$n\equiv \frac{1}{k}$ mod p转化为 $n*k\equiv 1$ mod p,然后通过for循环找到合适的n

4.gcd函数的构造

int gcd(int k,int p){
	int temp;
	if(k<p){
		temp=k;
		k=p;
		p=temp;
	}
	while(p!=0){
		temp=p;
		p=mod(k,p);
		k=temp;
	}
	return k;
}

gcd函数是用来计算k和p之间的最大公约数

利用辗转相除法，gcd(k,p)=gcd(p,k%p)。

5.suiji函数的构造

int suiji(int p){
	int k,k1,p1;
	k=2+rand()%(1000);
	k1=k;
	p1=p;
	if(gcd(k1,p1)==1){
		return k;
	}
	else{
		suiji(p);
	}
}

生成随机数k，如果与p的最大公约数为1，就返回，否则继续生成k，直到可以返回

6.主函数


int main(){
	int p,g,x,y,m,k,r,s,v1,v2,temp1,temp2,flag;
	cout<<"请输入大素数p:";
	cin>>p;
	cout<<"请输入本原根g:";
	cin>>g;
	cout<<"请输入秘密整数x(1——"<<p-2<<"):";
	cin>>x;
	cout<<"请输入消息m:";
	cin>>m;
	y=tongyu(g,x,p);
	k=suiji(p-1);
	r=tongyu(g,k,p);
	temp1=f_mod(k,p-1);
	s=mod((mod(m-x*r,p-1)*mod(temp1,p-1)),p-1);
	temp1=tongyu(y,r,p);
	temp2=tongyu(r,s,p);
	v1=mod((mod(temp1,p)*mod(temp2,p)),p);
	v2=tongyu(g,m,p); 
	flag=mod(v1-v2,p);
	if(flag==0){
		cout<<"签名有效";
	}
	else{
		cout<<"无效";
	}
}

flag是判断是否v1 $\equiv$ v2(mod p)。

7.总代码

#include<iostream>
#include<math.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
int mod(int a,int b){
	int ans;
	while(a<0){
		a=a+b; 
	}
	ans=a%b;
	return ans;
}
int tongyu(int a,int m,int n){//递归原理 
	long long int temp=a%n,ans;
	if(m==1){
		ans=temp;
	}
	else if(m>=2){
		ans=mod((temp*tongyu(a,m-1,n)),n);
	}
	return ans;
}
int f_mod(int k,int p){
	int ans;
	for(int i=1;;i++){
		ans=mod(i*k-1,p);
		if(ans==0){
			return i;
			break;
		}
	}
}

int gcd(int k,int p){
	int temp;
	if(k<p){
		temp=k;
		k=p;
		p=temp;
	}
	while(p!=0){
		temp=p;
		p=mod(k,p);
		k=temp;
	}
	return k;
}
int suiji(int p){
	int k,k1,p1;
	k=2+rand()%(1000);
	k=5;
	k1=k;
	p1=p;
	if(gcd(k1,p1)==1){
		return k;
	}
	else{
		suiji(p);
	}
}
int main(){
	int p,g,x,y,m,k,r,s,v1,v2,temp1,temp2,flag;
	cout<<"请输入大素数p:";
	cin>>p;
	cout<<"请输入本原根g:";
	cin>>g;
	cout<<"请输入秘密整数x(1——"<<p-2<<"):";
	cin>>x;
	cout<<"请输入消息m:";
	cin>>m;
	y=tongyu(g,x,p);
	k=suiji(p-1);
	r=tongyu(g,k,p);
	temp1=f_mod(k,p-1);
	s=mod((mod(m-x*r,p-1)*mod(temp1,p-1)),p-1);
	temp1=tongyu(y,r,p);
	temp2=tongyu(r,s,p);
	v1=mod((mod(temp1,p)*mod(temp2,p)),p);
	v2=tongyu(g,m,p); 
	flag=mod(v1-v2,p);
	if(flag==0){
		cout<<"签名有效";
	}
	else{
		cout<<"无效";
	}
}

8.输出结果

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

密码学