rsa.cpp

rsa加密的另一个源代码个人觉得还可以有需要的朋友可以

///////////////////////////////////////////////////////////////
//                        main.cpp                           //
///////////////////////////////////////////////////////////////
#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"
#include "MyNumber.h"
unsigned int numbers[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
	67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,
	163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,
	257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,
	359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,
	461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,
	577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,
	677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,
	809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,
	919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,
	1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,
	1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
	1229,1231,1237,1249,1259,1277,1279,1283,1291,1297,1301,1303,1307,1319,
	1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,
	1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,
	1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,
	1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,
	1747,1753,1759,1777,1737,1787,1789,1801,1811,1823,1831,1847,1861,1867,
	1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,
	1987,1997,1999,0
};


bool witness2(MyNumber n)
{
	srand(time(NULL));
	MyNumber a=rand()%7+2;
	unsigned int *dat;
	MyNumber n0=n;
	MyNumber d,x;
	n=n-1;
	int i=0,k=n.getlength();
	dat=new unsigned int [k];
	while (n>0)
	{
		dat[i]=(n%2!=0);
		n=n/2;
		i++;
	}
	d=1;
	n=n0-1;
	for(k=n.getlength()-1;k>=0;k--)
	{
		x=d;
		d=(d*d)%n0;
		if(d==1)
			if((x!=1))
				if(x!=(n)) return true;
		if(dat[k]==1) d=d*a%n0;
	}
	if(d!=1) return true;
	return false;
}

bool witness(MyNumber n)
{
	srand(time(NULL));
	MyNumber d=1,x,n0=n-1,a=rand()%7+2;
	for(int k=n.getlength()-1;k>=0;k--)
	{
		x=d;
		d=(d*d)%n;
		if(d==1&&x!=1&&x!=n0) return true;
		if(n0.getdata(k)==1) d=d*a%n;
	}
	if(d!=1) return true;
	return false;
}

bool witness1(MyNumber n)
{
	srand(time(NULL));
	MyNumber z,m,a=rand();
	int b=0,k=2,i;
//	a = a%n;
	a = a%7+2;
	while ((n-1)%k==0)
	{
		b++;
		k=k*2;
	}
	k=k/2;
	m=(n-1)/k;
//	z.exp(a,m,n,z);
	z=1;
	while (m>0)
	{
		if (m%2!=0) { z=z*a%n; m=m-1; }
		else { a=a*a%n; m=m/2; }
	}
	for (i=0;i<=b;i++)
	{
		if ((i==0&&z==1)||(z==n-1)) return false;
		if (i>0&&z==1) return true;
		if (i==b)  return true;
		if (i<b) z=z*z%n;
	}
	return true;
}

bool witness(int n)
{
	srand(time(NULL));
	int a;
	while((a=rand())<2);
	int n0;n0=n;
	int d,x;
	d=1;
	n=n-1;
	int len=32;
	for(;(n>>len)==0;len--);
	for(int k=len;k>=0;k--)
	{
		x=d;
		d=(d*d)%n0;
		if(d==1)
		{
			cout<<"d==1"<<endl;
			if(!(x==1))
				if(!(x==(n))) return true;
		}
		if((n&(1<<k))!=0)
		{
			cout<<"d=d*a"<<endl;
			d=d*a%n0;
		}	
	}
	if(d!=1) return true;
	return false;
}

MyNumber modinv( MyNumber &a, MyNumber &m ) 
{
	MyNumber j,i,b=m,c=a,x,y;
	j=(unsigned int)1;
	i=(unsigned int)0;
	while ( c != (unsigned int)0 )
	{
		x = b / c;
		y = b - x*c;
		b = c;
		c = y;
		y = j;
		j = i - j*x;
		i = y;
	}
	if ( i < (unsigned int)0 )
		i = i+ m;
	return i;
}

void main()
{
#define DEBUG_LQ
#ifdef DEBUG_LQ
	int count=0,k=1,j=1,k1=0,j1=0;
	int total,len1,len2;
	cout<<"please input the length of the number (times of 64):"<<endl;
	cin>>total;
	int size=64;
	while(total<size*2||total>size*32)
	{
		cout<<"you input a wrong number!"<<endl;
		cin>>total;
		cout<<"please input the length of another number:"<<endl;
	}
	len1=len2=total/2;

	FILE *fp =  fopen("t512.txt", "w");
	if(fp == NULL)  
	{
		cout <<" The file  can't be opened  !!\n";
		exit(1);
	}
	MyNumber ob1,ob2;
	ob1.makerandnumber(len2);
	int i=0;
	while(numbers[i]!=0)
	{
		for(;numbers[i]!=0;i++) 
			if((ob1%numbers[i])==0)break;
		if(numbers[i]!=0)
		{
			ob1=ob1+2;
			j++;
			i=0;
		}
		else 
		{
			if (!witness(ob1)) 
			{
//				if (!witness(ob1))
//				{
//					if (!witness(ob1))
//					{
						count++;
						if (count>1) break;
						ob2=ob1;
						fprintf(fp,"%3d k=%3d j=%3d\t",count,k,j);
						if (count%5==0) fprintf(fp,"\n");
//						{
														
							cout<<"Got "<<count<<endl;
//						}
						i=0;
						k1=k1+k;
						j1=j1+j;
						k=1;
						j=1;
						ob1.makerandnumber(len2);
//						ob1=ob1+2;
//					}else cout<<"no 3.......\n";
//				}else cout<<"no 2.......\n";
			}else  k++; // cout<<"no 1..."<<k<<"....\n"; 
			ob1=ob1+2;
			j++;
			i=0;
		}
	}
	//////到此为止生成两个通过五次witness检查的概率素数ob1,ob2//////
	if (witness(ob1)) cout  <<"ob1 is not a prime number!\n";
	if (witness1(ob1)) cout  <<"ob1 is not a prime number!\n";
	if (witness(ob2)) cout  <<"ob2 is not a prime number!\n";
	if (witness1(ob2)) cout  <<"ob2 is not a prime number!\n";
	cout<<"Got "<<count<<" k="<<k;
	cout<<" j="<<j<<endl;
	cout<<" k1="<<k1<<endl;
	cout<<" j1="<<j1<<endl;
	fprintf(fp,"%3d k=%3d j=%4d\n",count,k,j);
	fprintf(fp,"%4d primes, testing times= %5d Odd numbers= %6d\n",count,k1,j1);
	fclose(fp);
	cout<<"ob1:";ob1.display();cout<<endl; 
	cout<<ob1.getlength()<<endl;
	cout<<"ob2:";ob2.display();cout<<endl; 
	cout<<ob2.getlength()<<endl;
	MyNumber ob , n;
	n = ob1 * ob2;
	ob=(ob1-1)*(ob2-1);	//欧拉函数Ф(n)
	MyNumber  a;
	MyNumber u = 65537;
	MyNumber v = ob;
	a = modinv( u, v ) ;
	cout<<"模 n 为 :"<<n<<endl;
	cout<<"公钥 e 为 :";
	u.display();
	cout<<endl;
	cout<<"私钥 d 为 :"<<a<<endl;
	MyNumber  m,m1,m2;
//	char s1[80],s2[80],s[80]="abcdefghijklmnop123!@#$%&*()"; //s1[]="加密试验" 中文不行
	char s1[80],s2[80],s[80];
	cout<<"请输入待加密的字符串:";
	cin>>s;
	strcpy(s1,s);
	cout<<s1<<endl;
	m.Mstr(s1,m1);
	m.exp(m1,u,n,m);
	cout<<"密文为  :"<<m<<endl;
	m.exp(m,a,n,m2);
	m.Strm(m2,s2);
	cout<<"原文为  :";
	cout<<s2<<endl;
	if (m1==m2) cout<<" Ok..m1==m2..  :"<<endl;
	else cout<<" No m1 !=m2...  :"<<endl;
	if (strcmp(s1,s2)==0) cout<<" Ok.s1==s2...  :"<<endl;
	else cout<<" No  .s1!=s2...  :"<<endl;

#endif

}
//320 seconds to 256 bits