rsa3.cpp

RSA算法

	a[MAX-1]=1;
	
	sub(p,t,s);
	
	expmod ( a, s, p ,o);
	if ( cmp(o,t) != 0 ) 
	   {
		return 0;
	   }
	
	a[0]=3;
	for(i=0;i<MAX;i++)  o[i]=0;
	
	expmod ( a, s, p ,o);
	if ( cmp(o,t) != 0 ) 	   
	   {
		return 0;
	   }
	
	a[0]=5;
	for(i=0;i<MAX;i++)  o[i]=0;
	
	expmod ( a, s, p ,o);
	if ( cmp(o,t) != 0 ) 
	{	   
		return 0;
	}
	
	a[0]=7;
	for(i=0;i<MAX;i++)  o[i]=0;
	
	expmod ( a, s, p ,o);
	
	if ( cmp(o,t) != 0 ) 
	{
		
		return 0;
	}
	
	return 1;
}
int coprime(int e[MAX],int s[MAX]) /*//// 求两个大数之间是否互质////*/

{
    int a[MAX],b[MAX],c[MAX],d[MAX],o[MAX],l[MAX];
    int i;
	for(i=0;i<MAX;i++)
		l[i]=o[i]=c[i]=d[i]=0;
	o[0]=0;o[MAX-1]=1;
	l[0]=1;l[MAX-1]=1;
	mov(e,b);
	mov(s,a);
	do
	{
		if(cmp(b,l)==0)
		{
			return 1;
		}
		for(i=0;i<MAX;i++)
			c[i]=0;
		divt(a,b,d,c);
		mov(b,a);/*b--->a*/
		mov(c,b);/*c--->b*/
		
	}while(cmp(c,o)!=0);
	/*	printf("Ihey are  not coprime!\n");*/
	return 0;
}
void prime_random(int *p,int *q)
{
	int i,k;
	time_t t; 
	p[0]=1;
	q[0]=3;
	
	//	p[19]=1;
	//	q[18]=2;
	
	p[MAX-1]=10;
    q[MAX-1]=11;
	do
	{
		t=time(NULL);
		srand((unsigned long)t);
		for(i=1;i<p[MAX-1]-1;i++)
		{
			k=rand()%10;
			p[i]=k;
		}
		k=rand()%10;
		while (k==0)
		{
			k=rand()%10;
		}
		p[p[MAX-1]-1]=k;
		
	}while((is_prime_san(p))!=1);
	printf("素数 p 为  : ");
    for(i=0;i<p[MAX-1];i++)
	{
		printf("%d",p[p[MAX-1]-i-1]);
	}
    printf("\n\n");
	do
	{
		t=time(NULL);
		srand((unsigned long)t);
		for(i=1;i<q[MAX-1];i++)
		{
			k=rand()%10;
			q[i]=k;
		}
		
	}while((is_prime_san(q))!=1);
	printf("素数 q 为 : ");
    for(i=0;i<q[MAX-1];i++)
	{
		printf("%d",q[q[MAX-1]-i-1]);
	}
    printf("\n\n");
	return;
}	
void  erand(int e[MAX],int m[MAX])
{
	int i,k;
	time_t t;
	e[MAX-1]=5;
	printf("随机产生一个与(p-1)*(q-1)互素的 e :");
	do
	{
		t=time(NULL);
		srand((unsigned long)t);
		for(i=0;i<e[MAX-1]-1;i++)
		{
			k=rand()%10;
			e[i]=k;
		}
		while((k=rand()%10)==0)
			k=rand()%10;
		e[e[MAX-1]-1]=k;
	}while(coprime( e, m)!=1);
    for(i=0;i<e[MAX-1];i++)
	{
		printf("%d",e[e[MAX-1]-i-1]);
	}
    printf("\n\n");
	return ;
}
void rsad(int e[MAX],int g[MAX],int *d)
{
	int   r[MAX],n1[MAX],n2[MAX],k[MAX],w[MAX];
	int     i,t[MAX],b1[MAX],b2[MAX],temp[MAX];
	mov(g,n1);
	mov(e,n2);
	for(i=0;i<MAX;i++)
		k[i]=w[i]=r[i]=temp[i]=b1[i]=b2[i]=t[i]=0;
	b1[MAX-1]=0;b1[0]=0;/*/b1=0;*/
	b2[MAX-1]=1;b2[0]=1;/*/b2=1;*/
	while(1)
	{
		
		for(i=0;i<MAX;i++)
			k[i]=w[i]=0;
		divt(n1,n2,k,w);/*/k=n1/n2;*/
		for(i=0;i<MAX;i++)
			temp[i]=0;
		mul(k,n2,temp);/*/temp=k*n2;*/
		for(i=0;i<MAX;i++)
			r[i]=0;
        sub(n1,temp,r);
		
		if((r[MAX-1]==1) && (r[0]==0))/*/r=0*/
		{
			break;
		}
		else
		{
			mov(n2,n1);/*/n1=n2;*/
			mov( r,n2);/*/n2=r;*/
			mov(b2, t);/*/t=b2;*/
			for(i=0;i<MAX;i++)
				temp[i]=0;
			mul(k,b2,temp);/*/b2=b1-k*b2;*/
			for(i=0;i<MAX;i++)
				b2[i]=0;
			sub(b1,temp,b2);
			mov(t,b1);
		}
	}
	
	for(i=0;i<MAX;i++)
		t[i]=0;
	add(b2,g,t);
	for(i=0;i<MAX;i++)
		temp[i]=d[i]=0;
	divt(t,g,temp,d);
    printf("由以上的(p-1)*(q-1)和 e 计算得出的 d : ");
    for(i=0;i<d[MAX-1];i++)
		printf("%d",d[d[MAX-1]-i-1]);
    printf("\n\n");
}
/*/求解密密钥d的函数(根据Euclid算法)96403770511368768000*/
unsigned long  rsa(unsigned long p,unsigned long q,unsigned long e)  /*/求解密密钥d的函数(根据Euclid算法)*/
{
	unsigned long g,k,r,n1,n2,t;
	unsigned long b1=0,b2=1;
	
	g=(p-1)*(q-1);
	n1=g;
	n2=e;
    
    while(1)
	{
        k=n1/n2;
        r=n1-k*n2;
		if(r!=0)
		{
			n1=n2;
			n2=r;
			t=b2;
			b2=b1-k*b2;
			b1=t;
		}
		
		else
		{
			break;
		}
		
	}
    return (g+b2)%g;
}


void  tencrypto(int e[MAX], int n[MAX])/*//对有需要的文件进行加密*/
{
	FILE *fp;
    int i,k,count,temp,c;
	char filename[25],ch;
	struct slink  *p,*p1,*p2;
	struct slink  *h;
	h=p=p1=p2=(struct slink * )malloc(LEN);
	h=NULL;
	printf("\n输入需要加密的文件路径 : ");
	scanf("%s",filename);
	if((fp=fopen(filename,"r"))==NULL)
	{
		printf("Cannot open file !\n");
		exit(0);
	}
	printf("\n文件的原文内容：\n\n");
	count=0;
	while((ch=fgetc(fp))!=EOF)
	{  
		putchar(ch);
		c=ch;
		k=0;
		if(c<0)
		{
			c=abs(c);/*/把负数取正并且做一个标记*/
			p1->bignum[MAX-2]='0';
		}
		else
		{
			p1->bignum[MAX-2]='1';
		}
		
		while(c/10!=0)
		{
			temp=c%10;
			c=c/10;
			p1->bignum[k]=temp;
			k++;
		}
		p1->bignum[k]=c;
		p1->bignum[MAX-1]=k+1;
		count=count+1;
		if(count==1)
			h=p1;
		else p2->next=p1;
		p2=p1;
		p1=(struct slink * )malloc(LEN);
	}
    p2->next=NULL; 
    printf("\n");
  	 fclose(fp);
	 
	 //   printf("加密后文件的保存路径 : \n");
	 //   scanf("%s",encryfile);
	 //   fp=fopen(encryfile,"w");
	 fp=fopen(filename,"w");
	 p=p1=(struct slink * )malloc(LEN);
	 p=h;
	 printf("\n加密后文件中所形成密文：\n\n");
	 if(h!=NULL)
		 do 
		 { 
			 expmod( p->bignum , e ,n ,p1->bignum);
			 ch=p1->bignum[MAX-2];
			 printf("%c",ch);
			 fputc(ch,fp);
			 if ((p1->bignum[MAX-1]/10) ==0)/*/判断p1->bignum[99]的是否大于十；*/
			 {
				 ch=0+48;
				 printf("%c",ch);
				 fputc(ch,fp);
				 ch=p1->bignum[MAX-1]+48;
				 printf("%c",ch);
				 fputc(ch,fp);
			 }
			 else
			 {
				 ch=p1->bignum[MAX-1]/10+48;
				 printf("%c",ch);
				 fputc(ch,fp);
				 ch=p1->bignum[MAX-1]%10+48;
				 printf("%c",ch);
				 fputc(ch,fp);
			 }
			 
			 for(i=0;i<p1->bignum[MAX-1];i++)
			 {
				 printf("%d",p1->bignum[i]);
				 ch=p1->bignum[i]+48;
				 fputc(ch,fp);
			 }
			 p=p->next;
			 p1=(struct slink * )malloc(LEN);
		 }while(p!=NULL);
		 printf("\n\n");
		 fclose(fp);
		 return;
}
void  tdecrypto(int d[MAX], int n[MAX])
{
	
	FILE *fp;   
	struct slink *h,*p1,*p2;
	char ch,encryfile[25];
	   int i,j,k,c,count,temp;
	   printf("\n输入加密过的文件路径 : ");
	   scanf("%s",encryfile);
	   if((fp=fopen(encryfile,"r"))==NULL)
	   {
		   printf("此文件不存在!\n");
		   exit(0);
	   }
	   printf("\n文件中密文内容：\n\n");
	   i=0;
	   j=3;
	   count=0;
	   h=p1=p2=(struct slink * )malloc(LEN);
	   
	   while((ch=fgetc(fp))!=EOF)
	   {  
		   putchar(ch);
		   c=ch;	   
		   if(j==3)
		   {
			   p1->bignum[MAX-2]=c;
			   j--;
		   }
		   else if(j==2)
		   {
			   temp=c-48;
			   j--;
		   }
		   else if(j==1)
		   {
			   p1->bignum[MAX-1]=temp*10+c-48;
			   j--;
		   }
		   else if (j==0)
		   {
			   p1->bignum[i]=c-48;
			   i++;
			   if(i==p1->bignum[MAX-1])
			   { 
				   i=0;
				   j=3;
				   count++;
				   if (count==1)
					   h=p1;
				   else p2->next=p1;
				   p2=p1;
				   p1=(struct slink * )malloc(LEN);
			   }
		   }
	   }
	   p2->next=NULL; 
	   printf("\n");
	   fclose(fp);	
	   //	printf("解密后的明文文件保存路径 : \n");
	   //    scanf("%s",decryfile);
	   //    fp=fopen(decryfile,"w");
	   fp=fopen(encryfile,"w");
	   printf("\n解密密文后文件中的明文:\n\n");
	   p2=(struct slink * )malloc(LEN);
	   p1=h;
	   k=0;
	   if(h!=NULL)/*/temp为暂存ASIIC码的int值*/
		   do
		   {
			   for(i=0;i<MAX;i++)
				   p2->bignum[i]=0;
			   expmod( p1->bignum , d ,n ,p2->bignum);		  
			   temp=p2->bignum[0]+p2->bignum[1]*10+p2->bignum[2]*100;
			   if (( p2->bignum[MAX-2])=='0')
			   {
				   temp=0-temp;
			   }/*/转化为正确的ASIIC码，如-78-96形成汉字	*/	 
			   ch=temp;/*  str[k]--->ch */
			   printf("%c",ch);/*  str[k]--->ch */
			   fputc(ch,fp);/*/写入文件str[k]--->ch*/
			   k++;
			   p1=p1->next;
			   p2=(struct slink * )malloc(LEN);
		   }while (p1!=NULL);
		   printf("\n\n");
		   fclose(fp);
		   return;
}
/*/-------------------------------------------------主MAIN函数-----------------------------------/*/
void main()
{
	   int  i;
       int  p[MAX],q[MAX],n[MAX],d[MAX],e[MAX],m[MAX],p1[MAX],q1[MAX];
	   for(i=0;i<MAX;i++)
		   m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0;/*/简单初始化一下*/
	   printf("\n\n随机密钥对产生如下：\n\n");
	   prime_random(p,q);/*/随机产生两个大素数*/
	   mul(p,q,n);
	   printf("由 p、q 得出 n :");
	   print(n);
	   mov(p,p1);
	   p1[0]--;      
	   mov(q,q1);
	   q1[0]--;      /*/q-1;*/
	   mul(p1,q1,m);//m=(p-1)*(q-1)
	   erand(e,m);
	   rsad(e,m,d);
	   printf("密钥对产生完成，现在可以直接进行加解密文件!\n");
	   tencrypto( e,  n);
	   printf("\n加密文件操作完成!\n");
	   tdecrypto( d, n);
	   printf("\n解密文件操作完成!\n");	   
}