moni-momi.cpp

2的16次幂正整数d与n

/*
实验八  计算模逆与模幂
(一)实验内容
1．	对于两个不超过216的正整数d与n，编写计算d-1 (mod n) 的程序；
2．	对于三个不超过216的正整数a、e与n，编写计算ae (mod n) 的程序。
在上述程序基础上写出下列程序：
（1）	对给定的10000以内数判定其是否为素数；
（2）	进行ElGamal体制的加密与签名。
(二)实验要求
1.	判定n=2579是否为素数；
2.	选择p=2579，a=2，a=765，算出b=aa (mod p)=         。
设消息m=1299，若秘密选定随机整数x=853，按ElGamal体制：
i）试求出加密m的密文，并正确还原明文；ii）试对m作出签名，并进行验证。

*/

#include<stdio.h>	//头文件
#include<stdlib.h>
#include<math.h>
#include<time.h>

int  moni(int d,int n){	//求模逆
	int i,a[100][2],temp=0,vk,u=0,t;	//数组a用来存各个状态
	a[0][0]=n;	//初始阿a0=n,a1=d
	a[1][0]=d;
	for(i=2;a[i-1][0]!=0;i++){	//计算
		a[i][0]=a[i-2][0]%a[i-1][0];
		a[i-1][1]=(int)a[i-2][0]/a[i-1][0];
	}
	temp=i-3;	//长度
	if(a[temp+1][0]!=1)	//若最后一项不为1则不互素，无模逆
		printf("%d和%d不互素\n",a[1][0],a[0][0]);
	else{	//计算模逆
		for(i=1;i<=temp+1;i++)//a[i-1][0]!=0;i++)
			printf("%d=%d*%d+%d\n",a[i-1][0],a[i][1],a[i][0],a[i+1][0]);
		for(i=1,vk=-a[1][1],u=1;i<temp;i++){	//计算！
			t=vk;
			vk=u-vk*a[i+1][1];
			u=t;
		}
		a[0][1]=vk;
		printf("Vk=%d",vk);
		if(vk<0){vk=n+vk;printf("=%d\n",vk);}
		else putchar('\n');
	}
	return vk;
}

int momi(int a,int e,int n){	//求模幂，从左向右
	int i,ab[100],temp=0,tempn;	//数组ab用来存储2进制
	for(i=0,temp=e;temp!=0;i++){	//求2进制
		ab[i]=(int)temp%2;
		temp=(int)temp/2;
	}
	tempn=i-1;
	printf("%d的2进制为：",e);
	for(i=tempn;i>=0;i--)
		printf("%d",ab[i]);
	putchar('\n');
	for(i=tempn-1,temp=a;i>=0;i--){	//计算模幂
		temp=temp*temp%n;
		if(ab[i]==1)
			temp=temp*a%n;
	}	printf("\n结果为:%d\n",temp);
	return temp;
}

int jianyan(int n){	//检验素数
	int i,temp,s=0,t,a,b;
	temp=n-1;	//求2的最大次项
	while(temp%2!=1){
		temp=temp/2;
		s++;
	}
	printf("%d-1=2(%d)*%d\n",n,s,temp);
	t=temp;
	srand(time(NULL));
	a=rand()%n;	//随即生成a
	printf("a=%d\n",a);
	b=momi(a,temp,n);	//开始计算
	if(b==1){
		printf("====%d可能是素数\n",n);
		return 1;
	}
	for(i=0;i<s;i++){	//如满足条件则为素数
		if(b==-1||b==n-1){
			printf("====%d可能是素数\n",n);
			return 1;
		}
		if(b!=-1)b=momi(b,2,n);
	}
	printf("====%d是复合数\n",n);
	return 0;	
}

int ElGamal(int m,int x){	//ElGamal体制的加密与签名
	int p=2579,a=2,e=765,c,b,c1,c2,k;
	char s;
	srand(time(NULL));
	printf("1.加密 2.解密:");
	scanf("%d",&c);
	getchar();
	if(c==1){	//加密
		printf("手动输入？Y/N:");	//输入初态
		scanf("%c",&s);
		if(s=='Y'||s=='y'){
			printf("请输入 p a e:");
			scanf("%d %d %d",&p,&a,&e);
		}
		else{
			while(jianyan(p)==0||p<1000)
				p=rand()%10000;
			printf("随机整数为:");
			scanf("%d",&e);
			if(m<=0||m>p-1){
				printf("错误:m范围错误");
				return 0;
			}
		}
		b=momi(a,e,p);	//开始计算
		printf("公开密钥:(%d,%d,%d)\n",p,a,b);
		c1=momi(a,x,p);
		c2=m*momi(b,x,p)%p;
		printf("加密!!结果为:(%d,%d)",c1,c2);
	}
	if(c==2){	//解密
		printf("请输入公钥(p,a,b):");
		scanf("%d %d %d",&p,&a,&b);
		printf("密钥为:");
		scanf("%d",&e);
		k=x*moni(momi(m,e,p),p)%p;
		printf("解密!!结果为:%d\n",k);
	}
	return 0;
}

void main(){
	int c,a,d,e,m,n,x,temp;
	printf("1.求模逆\n2.求模幂\n3.检验素数\n4.ElGamal\n");
	scanf("%d",&c);

	switch(c){
		case 1 :printf("求模逆：请输入 d & n :");
				scanf("%d %d",&d,&n);
				temp=moni(d,n);
				break;
		case 2 :printf("求模幂：请输入 a & e & n :");
				scanf("%d %d %d",&a,&e,&n);
				temp=momi(a,e,n);
				printf("\n结果为:%d\n",temp);
				break;
		case 3 :printf("检验素数：请输入需要检验的数:");
				scanf("%d",&d);
				temp=jianyan(d);
				break;
		case 4 :printf("ElGamal：请输入 m & x:");
				scanf("%d %d",&m,&x);
				temp=ElGamal(m,x);
				break;
		default :printf("输入错误\n");
	}

}

/*
1.求模逆
2.求模幂
3.检验素数
4.ElGamal
3
检验素数：请输入需要检验的数:2579
2579-1=2(1)*1289
a=2428
1289的2进制为：10100001001
结果为:2578
====2579可能是素数

1.求模逆
2.求模幂
3.检验素数
4.ElGamal
4
ElGamal：请输入 m & x:1299 853
1.加密 2.解密:1
手动输入？Y/N:y
请输入 p a e:2579 2 765
765的2进制为：1011111101
结果为:949
公开密钥:(2579,2,949)
853的2进制为：1101010101
结果为:435
853的2进制为：1101010101
结果为:2424
加密!!结果为:(435,2396)

1.求模逆
2.求模幂
3.检验素数
4.ElGamal
4
ElGamal：请输入 m & x:435 2396
1.加密 2.解密:2
请输入公钥(p,a,b):2579 2 949
密钥为:765
765的2进制为：1011111101
结果为:2424
2579=1*2424+155
2424=15*155+99
155=1*99+56
99=1*56+43
56=1*43+13
43=3*13+4
13=3*4+1
4=4*1+0
Vk=-599=1980
解密!!结果为:1299
*/