rsa.cpp

RSA算法是在1978年由Ron Rivest, AdiShamir 和Leonard Adleman提出的一种公钥加密算法。RSA能同时用于加密和数字签名的算法

/****************** RSA加密解密 **********************/
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define N 10000;
#define max 100

void E(int f,int &e)  //自动产生随机数（公钥e）
{
   int x,y,r;
   srand(time(0));
   while(1)
   {
     e=rand()%f;
	 if(e>1)
	 {
        y=e;x=f;
	    while(y!=1)
	    {
          r=x%y; x=y; y=r;
	      if(y==1||y==0)
	        break;
	     }
	     if(y==1)  break;
	 }
   }
}

int niyuan( int n, int e) // 求逆元算法
{
    int x1, x2, x3, y1, y2, y3, t1, t2, t3, temp;
    x1=1;  x2=0;  x3=n;  y1=0;  y2=1;  y3=e;
    while(1)
	{
      if(y3==1)
	  {
	     if(y2>=0)   return y2;
	     else   return (n+y2);
	     break;
	  }
	 temp=x3/y3;
	 t1=x1-temp*y1;
	 t2=x2-temp*y2;
	 t3=x3-temp*y3;
	 x1=y1;  x2=y2;  x3=y3;
	 y1=t1;  y2=t2;   y3=t3;
	}
}

unsigned __int64 mo(unsigned __int64 b,int n,int m) //  模平方重复法
{
    int temp=1;
    unsigned __int64 a=1;
    while(temp!=0)
	{
     if(n%2) a=(a*b)%m;
	 b=(b*b)%m;
	 temp=n/2;
	 n=temp;
	}
    return a;
}

int suijipq() // 随机产生初始的保密的大素数p和q
{
   int temp,n;
 do
 {
     n=rand()%100000;
	 temp=(int)sqrt(n);
	 for(int i=2;i<=temp;i++)
	     if(n%i==0)   break;
	 if(i==temp+1 && n>10000) 
         return n;
 }while(1);
}

//bb为false为加密运算,true为解密运算
void cipher(char *in,char *&out,unsigned __int64 *&temp1,int total,int n,int e,bool bb)
{
   unsigned __int64  temp;
   if(!bb)
   {
     for(int i=0;i<total;i++)
	 {
	     temp=(int)in[i];
	     temp1[i]=mo(temp,e,n);
	     if(temp1[i]!=0)
	         out[i]=(char)(temp1[i]%256);
	     else  out[i]=in[i];
	 }
    }
   if(bb)
   {
     for(int j=0;j<total;j++)
	 {
	     if(temp1[j]!=0)
	     {
	         temp=mo(temp1[j],e,n);
	         out[j]=(char)(temp%256);
		 }
	     else out[j]=in[j];
	 }
   }
}
void main()
{
    int p,q,f,e,d,i;char *mingwen=new char[max];char *miwen=new char[max];
	char *jiemi=new char[max];unsigned __int64 *temp1=new unsigned __int64[max];
	p=suijipq();
	printf("随机产生的一个大整数p=%d\n",p);
	while((q=suijipq())==p);
	printf("随机产生的一个大整数q=%d\n",q);
	f=(p-1)*(q-1);
       E(f,e);
	printf("则随机产生e=%d\n",e);
	d=niyuan(f,e);
	printf("经计算e的逆元d=%d\n",d);
	printf("请输入明文\n");
	i=0;char ch;
	while((ch=getchar())!='\n') 
          mingwen[i++]=ch;  
       printf("明文加密后的密文为：\n");
	cipher(mingwen,miwen,temp1,i,p*q,e,false);
       for(int k=0;k<i;k++)
	    putchar(miwen[k]);	
	printf("\n");		
	printf("密文解密后的明文为：\n");	
	cipher(mingwen,jiemi,temp1,i,p*q,d,true);
       for(int m=0;m<i;m++)
	    putchar(jiemi[m]);
	printf("\n");
}