#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>
//欧几里得除法
int Euclidean_Division(int a,int b){
int item;
if(b>a){
item=a;a=b;b=item;
}
int r0=1,r1=a,r2=b;
while(r0!=0){
r0=r1%r2;
item=r2;
r1=r2;
r2=r0;
}
return item;
}
int bezout(int a,int b,int s,int t){
int item,j=3,flag=0;
if(b>a){
item=a;a=b;b=item;
}
int array[100][5];
array[2][3]=a/b;
array[2][4]=(-1)*array[2][3]*b+a;
array[0][0]=-3;
array[1][0]=-2;
array[2][0]=-1;
array[1][1]=1;
array[2][1]=0;
array[1][2]=0;
array[2][2]=1;
array[0][4]=a;
array[1][4]=b;
do{
array[j][0]=-3+j;
array[j][1]=(-1)*array[j-1][3]*array[j-1][1]+array[j-2][1];
array[j][2]=(-1)*array[j-1][3]*array[j-1][2]+array[j-2][2];
array[j][3]=array[j-2][4]/array[j-1][4];
array[j][4]=((-1)*array[j][3])*array[j-1][4]+array[j-2][4];
j++;
}while(array[j-1][4]!=0);
s=array[j-1][1];
t=array[j-1][2];
return t;
}
int select_int(int v){
int i;
while(1){
srand((unsigned)time(NULL));//定义后可产生不同的随机数
i=rand()%(v+1)+2;//2~v-1的随机数
if(Euclidean_Division(i,v)==1&&bezout(i,v,0,0)>=1){
return i;
}
}
}
//二进制转换
int *erjz(int n,int &num){
int temp=n;
while(n>0){
n=n/2;
num++;
}
int c[num];
int i=0;
n=temp;
while(n>0){
c[i++]=n%2;
n=n/2;
}
return c;
}
void erjz2(int n,int *c){
int temp=n,num=0;
while(n>0){
n=n/2;
num++;
}
int i=0;
n=temp;
while(n>0){
c[i++]=n%2;
n=n/2;
}
}
//平方乘算法
long long int pow_and(int b,int n,int m){
int num=0,i,r=0;
erjz(n,num);
int c[num];
erjz2(n,c);
long long int ch[num];
ch[num-1]=b;
for(i=num-2;i>=0;i–){
if(c[i]==1){
ch[i]=(ch[i+1]*ch[i+1]*b+m)%m;
}
else{
ch[i]=(ch[i+1]*ch[i+1]+m)%m;
}
}
return ch[0];
}
int main(){
int p,q,i,d;
printf(“说明：公钥密码系统使用N=26字符集N。\n明文信息空间为k=2-字符组组成的集合M=N^k。\n”);
printf(“密文信息空间为l=3-字符组组成的集合C=N^l。\n”);
printf(“请分别输入素数对p,q:”);
scanf(“%d%d”,&p,&q);
printf(“运用素数对p=%d,q=%d。\n”,p,q);
int n=p*q,v=(p-1)*(q-1);
printf(“(1)计算n=p*q=%d 和 v=(p-1)(q-1)=%d。\n”,n,v);
int e=select_int(v);
//e=13;
printf(“(2)随机选取整数e=%d，1<e<v，使得gcd(e,v)=1。\n”,e);
d=bezout(e,v,0,0);
//d=237;
printf(“(3)运用广义欧几里得算法具体计算唯一的整数d=%d，1<d<v,使得e*d=1(modv)。\n”,d);
printf(“(4)说明公钥是Ke=(n,e)=(%d,%d)，私钥是Kd=d=%d\n”,n,e,d);
printf(“(5)以两字符为一组给出明文的数字信息，加密后的数字信息和密文字符\n”);
printf(“输入明文字符（两字符为一组）：”);
char ch[100];
int m[50],r;
scanf(“%s”,ch);
for(i=0;i<strlen(ch);i=i+2){
m[i/2]=(ch[i]-‘a’)*26+ch[i+1]-‘a’;
printf(“%c%c = %d*36+%d = %d\n”,ch[i],ch[i+1],ch[i]-‘a’,ch[i+1]-‘a’,m[i/2]);
}
printf(“\n/****加密过程****/\n\n”);
printf(“为加密信息，将明文转换为数字信息，再通过公钥加密\n”);
int c[50];
for(i=0;i<strlen(ch);i=i+2){
c[i/2]=pow_and(m[i/2],e,n);
printf(“发送者B计算c = m^e(mod n) = %d^%d(mod %d) = %d\n”,m[i/2],e,n,c[i/2]);
printf(“将数字信息转换为%d = %d*26+%d = %c%c\n”,c[i/2],c[i/2]/26,c[i/2]%26,c[i/2]/26+’a’,c[i/2]%26+’a’);
}
printf(“\n/****解密过程****/\n\n”);
printf(“为解密信息，将明文转换为数字信息，再通过密文转换成数字信息\n”);
int t[50];
for(i=0;i<strlen(ch);i=i+2){
t[i/2]=pow_and(c[i/2],d,n);
printf(“用私钥d = %d计算：c^d(mod n) = %d^%d(mod %d) = %d\n”,d,c[i/2],d,n,t[i/2]);
printf(“将数字信息转换为%d = %d*26+%d = %c%c = 明文\n”,t[i/2],t[i/2]/26,t[i/2]%26,t[i/2]/26+’a’,t[i/2]%26+’a’);
}
}