multiple.cpp

实现RSA加密

# include <iostream.h>
# include <math.h>

class RSA
{   
	public:
	   int p;
	   int q;
	   int M,d,n;
	   int e;
	   int m;
	   //unsigned __int64 c;
	   int c;
    public:
     RSA(int i=0,int j=0,int k=0)
	 {
		 if(Isprime(i)&&Isprime(j))
		 {  
		    //cout<<i<<j<<endl;
            p=i;
			q=j;
			m=k;
			//cout<<p<<q<<endl;
		 }
		 else
		 {
			 cout<<"输入数据不能为空且必须是素数！"<<endl;
		 }
	 }
	 void creatN()//计算N
	 {
		 n=p*q;
	 }
	 void creatM()//计算M
	 {
		 M=(p-1)*(q-1);
	 }
	 void setE()//赋值 e
	 {
		 e=13;
	 }
	 void creatD()//生成D
	 {
		 int sum=M;
		 while(1)
		 {
			 if((sum+1)%e==0)
			 {
				 d=(sum+1)/e;
				 break;
			 }
			 else
				 sum+=M;
		 }
	 }
	 bool Isprime(int m)//判断素数
	 {
         double d=sqrt(m);
		 for(int i=2;i<=d;i++)
			 if(m%i==0)
				 return false;
		  return true;
		 
	 }
	 
	 void init()//初始化n,m,e,d;
	 {
        creatN();
		setE(); 
		creatM();
		creatD();
	 }
	 void RsaEncrypt()
	 {
         //c=pow(m,e)%n;
		/* c=1;
		 int k;
		 cout<<p<<" "<<q<<" "<<e<<" "<<n<<" "<<M<<" "<<m<<endl;
		 //cout<<c*m<<endl;
		 while(e>=1)
		 {
            if(e%2==1)
			{
			
				c=MultipleModN(c,m,n);
				//c=MultipleModN(c,c,n);

				//c=c*m%n;
				cout<<"e="<<e<<" "<<c<<endl;
				cin>>k;
				
				//c=MultipleModN(c,c,n);
				e-=1;
				//if(e==0)
				//	break;
			}
			else if(e%2==0)
			{
				   //c=c*c % n;
				 c=MultipleModN(c,c,n);
                   
                 cout<<"e="<<e<<" "<<c<<endl;
				 cin>>k;
				 e=e/2; 
                       

			}
		
		}
		c=MultipleModN(c,c,n);*/
		int E[16];
		int e1=e;int e2;
		int i=0;
		c=1;
		while(e1)
		{
            e2=e1%2;
			e1=e1/2;
			E[i++]=e2;
		}
		for(int j=i-1;j>=0;j--)
		{
			c=MultipleModN(c,c,n);
			if(E[j]==1)
               c=MultipleModN(c,m,n);
		}
         
	 }
	 int MultipleModN(int c,int m,int n)
	 {   
		 int a;
         int A[16];
		 int B[16];
		 int C[16];
		 int sum[32];
		 int Alength=DecDiv(A,c);//把c的各个位上的十进制数从低位依次写入数组A中
		 int Blength=DecDiv(B,m);//把m的各个位上的十进制数从低位依次写入数组B中
		 int Clength=DecDiv(C,n);//把n的各个位上的十进制数从低位依次写入数组C中
		 //for(int i=0;i<Alength;i++)
		 //{
		 //	 cout<<A[i];
		 //}
		 int sumlength=Multiple(A,Alength,B,Blength,sum);//A*B=sum;
         a=ModN(sum,sumlength,C,Clength);
	     //for(int k=0;k<sumlength;k++)
		 //   cout<<sum[k];
		 return a;
	
	

	 }
	 int DecDiv(int * A,int i)//把i的各个位上的十进制数从低位依次写入数组A中
	 {
		 int k=0;
		 int j=0;
		 while(i)
		 {
             j=i%10;
			 i=i/10;
			 A[k++]=j;
		 }
		 return k;
	 }
     int  Multiple(int *A,int Alength,int * B ,int Blength,int * sum)
	 {
        int i,j,k,N,carry=0;
         for(k=0;k<32;k++)//初始化数组sum
		    sum[k]=0;
         for(i=0;i<Alength;i++)
		 {
		   for(j=0;j<Blength;j++)
		   {
		      N=A[i]*B[j];
				
              carry=N/10;
		      N=N%10;
              sum[i+j]+=N;
			  sum[i+j+1]+=carry;
			  carry=sum[i+j]/10;
			  sum[i+j] %= 10;
			  sum[i+j+1]+=carry;
			}
		 }
		 for( i=31;i>=0;i--)
			 if(sum[i]!=0)
				 return (i+1);
	     return 0;
		  // return Alength+Blength-1;
	 }
	 int ModN(int * sum,int sumlength,int * C,int Clength)
	 {      
		   int k=0;int ten=1;
           //while(Clength<=sumlength||C[Clength]<sum[sumlength])//可以减少比较次数
		   while(Clength<sumlength ||compare( sum, sumlength,C, Clength))
		   {
			   for(int i=0;i<Clength;i++)
			   {   
                   
				   if(C[i]<=sum[i])
				   {
					   sum[i]-=C[i];
				   }
				   else
				   {
					   borrow(sum,sumlength,i+1);//向sum的第i+1位借一;
					   sum[i]=sum[i]+10-C[i];
				   }
			   }
			   //if(Clength==sumlength && C[Clength]>sum[sumlength])
				//   break;
		   }
		  
		   for(int i=0;i<sumlength;i++)
		   {   
			   //cout<<sum[i];
			   k+=sum[i]*ten;
			   ten*=10;
		   }  
		   //cout<<endl;
		   return k;
	 }
	 bool compare(int * sum,int sumlength,int *C,int Clength)//sum小于C，返回false;
	 {                                                       //否则返回true;
             
			 if(Clength>sumlength)
				 return false;
             else
			 {   
				 int i=sumlength-1;
				 while(i>=0)
				 {
					 if(C[i]>sum[i])
						 return false;
					 else
						 if(C[i]<sum[i])
							 return true;
					 i--;
				 }
			 }
			 return true;

	 }
	 void borrow(int * sum,int & sumlength,int i)
	 {   
		 //cout<<i<<"adf"<<endl;
		 if(sum[i]>0)
		 { 
			 sum[i]--;
			 //cout<<i<<'='<<sum[i]<<endl;
			 //for(int i=sumlength-1;i>=0;i--)
			//	 cout<<sum[i];
			 //cout<<endl;
		 }
		 else
		 {
			 sum[i]=9;
			 borrow(sum,sumlength,i+1);
		 }
		 if(i+1==sumlength&&sum[i]==0)
              sumlength--;
	 }
	 int RsaUnencrypt(int c)
	 {
        int D[16];
		int d1=d;int d2;
		int i=0;
		m=1;
		while(d1)
		{
            d2=d1%2;
			d1=d1/2;
			D[i++]=d2;
		}

		for(int j=i-1;j>=0;j--)
		{   
			//cout<<D[j];
			m=MultipleModN(m,m,n);
			if(D[j]==1)
               m=MultipleModN(m,c,n);
		}
		cout<<endl;
		return m;
	 }
     
};	//End RSA; 
	


void main()
{
     /*int c;
	 int sum[5]={1,2,0,0,6};
	 int lengthsum=5;
	 int N[3]={9,0,9};
     int length=3;
    RSA a(43,59,1520);
	//c=a.MultipleModN(10000,10000,13);
	a.init ();
	a.RsaEncrypt ();
	//c=a.ModN(sum,lengthsum,N,length);
	cout<<a.c<<endl ;
	//c=60021%909;
	//cout<<c<<endl ;*/
	 RSA a(43,59,814);
     a.init ();
	 cout<<a.d<<endl ;
	 //a.RsaEncrypt ();
	 int m=a.RsaUnencrypt(95);
	 cout<<a.m<<endl ;
}