big.cpp

RSA算法

#include "Big.h"
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;

void Big::Output()
{
	if(!negative)
		cout<<'-';
	int i = length - 1;
	cout<<setbase(16)<<numbers[i--]<<' ';
	for(;i >= 0;i--)	
		cout<<setbase(16)<<setw(8)<<setfill('0')<<numbers[i]<<' ';
	cout<<endl;
}

void Big::Push_back(const long n)
{
	numbers[length++] = n;
}

Big::Big(const long n0)
{	
	long n=n0;
	length = 0;
	if(n >= 0)
		negative = true;
	else
	{	
		n = -n;
		negative = false;
	}
	//	unsigned long temp;	//	temp = n % 4294967296;		//65536 * 65536
	Push_back(n);
	this->Clean();
}

void Big::Clean()
{
	if(!length)
	{
		Push_back(0);
		return;
	}
	while(!numbers[length-1])
	{
		length--;
		if(length<=0)
			break;
	}
	if(!length)
		Push_back(0);
}

int Judge(const Big &b1,const Big& b2)
{
	if(b1.negative > b2.negative)
		return 1;
	if(b1.negative < b2.negative)
		return -1;
	if(b1.length<b2.length)
		return -1;			//b1 < b2
	if(b1.length>b2.length)
		return 1;			//b1 > b2
	for(int i = b1.length-1;i >= 0;i--)
	{				
		if(b1.numbers[i]>b2.numbers[i])
			return b1.negative? 1:-1 ;		//b1 > b2
		if(b1.numbers[i]<b2.numbers[i])
			return b1.negative? -1:1 ;		//b1 < b2
	}
	return 0;
}

Big Big::operator + (const Big& bx)
{	
	Big answer;
	Big b2=bx;
	if( negative != b2.negative)	//b1 ,b2 符号相反
	{
		if(negative)	//b1>=0,b2<0
		{
			b2.ChangeNegative();
			return *this - b2;
		}
		else
		{
			ChangeNegative();	//b1 < 0,b2>=0
			return b2 - *this;
		}
	}
	if( length < b2.length)
	{
		return b2 + *this;
	}
	unsigned long temp;
	bool carry = false;
	for(int i = 0;i < b2.length;i++)
	{
		temp = numbers[i] + b2.numbers[i] + carry;
		if(temp < numbers[i] || temp < b2.numbers[i])
			carry = 1;
		else
			carry = 0;
		answer.Push_back(temp);
	}
	if(carry)	
		for(;i < length && carry;i++)
		{
			temp = numbers[i] + carry;
			if(temp < numbers[i])
				carry = 1;
			else
				carry = 0;
			answer.Push_back(temp);
		}
		if(carry)
			answer.Push_back(1);
		while(i < length)
			answer.Push_back(numbers[i++]);
		answer.negative = b2.negative;
		return answer;
}

Big Big::operator += (const Big& b2)
{
	return	*this = *this + b2;
}

Big Big::operator - (const Big& b2)
{
	Big answer;
	if(negative > b2.negative)
	{	//b1 >=0 , b2<0 
		answer = b2;
		answer.ChangeNegative();//b1,b2 >= 0
		return *this + answer;
	}
	if(negative < b2.negative)
	{	//b1 <0 , b2>=0 
		answer = b2;
		answer.ChangeNegative();//b1,b2 < 0
		return *this + answer;
	}
	bool carry = false;
	if(Judge(*this,b2)<0)	//b1<b2
	{	
		Big temp = b2;
		answer = temp - *this; //answer>0
		answer.ChangeNegative();
		return answer;
	}
	//现在 *this >= b2
	unsigned long i,temp;
	for(i = temp = 0;i < b2.length;i++)
	{	
		temp = numbers[i] - b2.numbers[i] - carry;
		if(carry && (temp == numbers[i]))
			carry = 1; 
		else 
		{	
			if(temp > numbers[i])	
				carry = 1;
			else 
				carry = 0;
		}
		answer.Push_back(temp);
	}
	if(carry)
		while(i < length)
		{
			temp = numbers[i]-carry;
			answer.Push_back(temp);
			if(temp > numbers[i])
			{	
				i++;
				break;
			}
			else
				carry = 0;
			i++;
		}
		while(i < length)
			answer.Push_back(numbers[i++]);
		answer.Clean();
		return answer;
}

Big Big::operator << (const int times)
{	
	unsigned short left_carry=0;
	unsigned short right_carry=0;
	int i,j;
	Big answer = *this;
	for(i = 0;i < times;i++)
	{
		for(left_carry=right_carry=j=0;j<answer.length;j++)
		{	
			if(answer.numbers[j] & 0x80000000)
				left_carry = 1;
			else
				left_carry = 0;
			answer.numbers[j] = (answer.numbers[j] << 1) +right_carry;
			right_carry=left_carry;
		}
		if(left_carry)
			answer.Push_back(1);
	}
	return answer;
}

Big Big::operator >> (const int times)
{	
	unsigned short left_carry=0;
	unsigned short right_carry=0;
	int i,j;
	Big answer = *this;
	for(i=0;i<times;i++)
	{
		for(left_carry=right_carry=0,j=answer.length-1;j >= 0; j-- )
		{	
			if(answer.numbers[j] & 0x1)
				left_carry=1;
			else
				left_carry=0;
			answer.numbers[j] = ( answer.numbers[j] >> 1 ) + 0x80000000*right_carry;
			right_carry = left_carry;
		}
		answer.Clean();
	}
	answer.Clean();
	return answer;
}

Big Big::operator * (const Big& bx)	//俄罗斯农夫算法
{
	if(this->length > 1 && bx.length > 1)
	{
		Big answer;
		int i;
		bool flag = true;
		Big temp1 = *this,temp2 = bx;
		if((temp1.negative + temp2.negative) % 2)
			flag = false;
		temp1.negative = temp2.negative = 1;
		if(Judge(temp1,temp2) >= 0)
		{
			for(i = 0;temp1.numbers[temp1.length-1];temp1.numbers[temp1.length-1] >>= 1,i++);
			i = (temp1.length - 1) * 32 + i;
			if(i % 2)
				i++;	// i = 2n	
			i /= 2;
			temp1.numbers[temp1.length-1] = this->numbers[this->length-1];	
		}
		else
		{
			for(i = 0;temp2.numbers[temp2.length-1];temp2.numbers[temp2.length-1] >>= 1 ,i++);
			i = (temp2.length - 1) * 32 + i;	//获得位数信息
			if(i % 2)
				i++;	// i = 2n
			i /= 2;
			temp2.numbers[temp2.length-1] = bx.numbers[bx.length-1];
		}
		Big a1 = temp1 >> i,b1 = temp2 >> i;
		Big a0 = temp1 - (a1 << i),b0 = temp2 - (b1 << i);
		temp1 = a1 * b1;
		temp2 = a0 * b0;	
		answer = (temp1 << (2*i));
		answer += temp1 << i;
		temp1 = (a1 - a0) * (b0 - b1);
		answer += temp1 << i;
		answer += temp2 << i;
		answer += temp2;
		if(flag)
			return answer;		//return temp1 << (2*i) + temp1 << i + ((a1 - a0) * (b0 - b1)) << i + temp2 + temp2 << i;
		answer.ChangeNegative();
		return answer;
	}
	else
	{
		Big answer(0);
		Big c1,b2;
		if(Judge(*this,bx) < 0)
		{
			c1 = *this;
			b2 = bx;
		}
		else
		{
			b2 = bx;
			c1 = *this;
		}
		if(b2.length==1 && !b2.numbers[0])
			return answer;
		if(c1.length==1 && !c1.numbers[0])
			return answer;
		while( !(c1.length == 1 && c1.numbers[0] == 1))
		{
			if(c1.numbers[0] & 0x1)		//numbers[0]是奇数
				answer += b2;
			c1 = c1 >> 1;
			b2 = b2 << 1;
		}
		answer += b2;
		answer.negative = !((this->negative + b2.negative) % 2);
		return answer;
	}
}

Big Big::operator % (const Big& bx)
{
	Big b1=*this,b2=bx;			//	b1 / b2
	while(Judge(b1,b2)>0)
		b2 = b2 << 1;			//之后 b2 = b1,或者b2比b1多一位
	while( Judge(b1,bx)>0)
	{
		while(Judge(b1,b2)<0)
		{	
			b2 = b2 >> 1;
		}
		if(Judge(b1,b2) == 0)		//如果b1=b2，则余数为0
		{
			b1.length = 0;
			b1.Push_back(0);
			return b1;
		}		//现在 b2 > b1,b2比b1多一位
		b1 = b1 - b2;
	}
	if(Judge(b1,bx) == 0)
	{	
		b1.length = 0;
		b1.Push_back(0);
		return b1;
	}
	b1.Clean();
	return b1;
}

Big Big::operator / (const Big& bx)
{
	Big b1 = *this,b2 = bx;			//	b1 / b2
	Big flag,answer;
	flag.Push_back(1);
	for(int i=0;Judge(b1,b2)>0;i++)
		b2 = b2 << 1;			//移动i次 之后 b2 = b1,或者b2比b1多一位
	answer.Clean();
	while( Judge(b1,bx)>0)
	{
		for(;Judge(b1,b2)<0;i--)
			b2 = b2 >> 1;			//之后b1<=b2
		answer += flag << i;
		if(Judge(b1,b2) == 0)		//如果b1=b2，则余数为0
		{
			b1.length = 0;
			b1.Push_back(0);
			return answer;
		}		//现在 b2 > b1,b2比b1多一位	
		b1 = b1 - b2;
	}
	if( Judge(b1,bx)==0 )   //b1>=bx
		answer += flag;
	answer.Clean();
	answer.negative = !((this->negative + b2.negative) % 2);
	return answer;
}

Big Modular(Big& b,Big times,const Big& m)
{
	Big answer,power;
	int temp;
	answer.Push_back(1);
	power = b % m;
	while(times.length > 0)
	{
		if(times.length == 1 && times.numbers[0] == 0)
			break;
		temp = times.numbers[0] & 1;
		times = times >> 1;
		if(temp)
			answer = ( answer * power ) % m;
		power = power * power % m;
	}
	answer.Clean();
	return answer;
}

/*
Big Modular(Big& b,Big times,const Big& m)
{
Big answer,power;
int temp;
answer.Push_back(1);
power = b % m;
while(times.length > 0)
{
if(times.length == 1 && times.numbers[0] == 0)
break;
temp = times.numbers[0] & 1;
times = times >> 1;
if(temp)
answer = ( answer * power ) % m;
power = power * power % m;
}
answer.Clean();
return answer;
}*/


Big Gcd(Big &a,Big& b)
{
	Big flag(1);
	if(Judge(a,b) >= 0)
	{
		cout<<"the first number is >= the second one "<<endl;
		return flag;
	}
	Big k = b / a;
	Big ka = k * a;					// b = ka + rest
	Big rest = b % a;
	Big i(1);
	Big temp1,temp2;
	Big rest_rest = rest % a;
	Big k_from_rest(0);//k_from_rest += rest_rest
	while(rest_rest.length != 1 || rest_rest.numbers[0] != 1)		// rest_check % a   != 1	
	{	// t*b = t* ka + t*rest
		// t*b = ( t*k + k`)a + 1 ,此时rest%a =1,结束
		i += 1;						// t = i,计算+了多少次
		k_from_rest += ( rest + rest_rest ) / a;
		rest_rest = ( rest + rest_rest )  % a;
	}
	//rest_check =======1 now!
	Big k_total = i * k + k_from_rest;	//k` = k_from rest , k_total = t * k + k`
	k_total = k_total % b;
	k_total = b - k_total;
	return k_total;
}

void Big::odd_generator(int length){
	//	time_t ltime;
	//	time( &ltime );
	
	srand ((unsigned)(time( NULL )) );
	unsigned long temp=rand()*rand();
	while((temp&1)!=1){
		temp=rand()*rand();
	}
	//	cout<<hex<<temp<<endl;
	Push_back(temp);
	for (int i=1;i<length-1;i++){
		temp=rand()*rand();
		Push_back(temp);
	}
	temp=rand()*rand();
	while (temp & 0x80000000)
	{
		temp=rand()*rand();
	}
	Push_back(temp);
}

bool prime_tester(Big & big){
	Big temp=big-1;
	long b=0;
	Big rand_a=rand();
	while((temp.numbers[0]&1)==0){
		b++;
		temp=temp>>1;
	}
	Big z;
	unsigned j=0;
	z=Modular(rand_a,temp, big);
	if(!Judge(z,1)||!Judge(z,(big-1))) {return true;}
	for(int i=1;i<b-1;i++){
		if(!Judge(z,(big-1))) {return true;}
		z=(z*z)%big;
		if(!Judge(z,1)) {return false;}
	}
	if(Judge(z,big-1)) {return false;}
	return true;
}

/*
bool prime_tester_2(Big & big){
int n= big.numbers.size()*sizeof(unsigned long);
cout<<"计算p的有效位n"<<n<<endl;
srand ((unsigned)(time( NULL )) );
unsigned a=rand();
int z=1;i=n;
long x=z;z=(d*d)%big;
if ()
{
}
}*/

/*
2. Rabin-Miller素数检测算法
对一个待测的随机大数p，计算p的有效位n，比如p＝0x5A，则n＝7。
1) 选择一个小于p的随机数a。
2) 令z＝1，i＝n。
3) x＝z，z＝d×d MOD N。
4) 如果z＝1并且x<>1并且x<>p－1，那么测试通不过，p不是素数。
5) 如果p－1的第i位为1，令z＝z×a MOD p，i＝i－1。如果i>=0，则转到第 
三步。
6) 如果z<>1，则同不过检测，p不是素数，否则通过检测，p可能为素数。*/
bool prime_tester_small(Big & big){
	static int SMALL_PRIMES[] = {
		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//167
			,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,1289,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,1783,1787,1789,1801,1811,1823,1831,
			1847,1861,1867,1871,1873,1877,1879,1889,1901,
			1907,1913,1931,1933,1949,1951,1973,1979,1987,
			1993,1997,1999//302
			/*,2003,2011,2017,2027,2029,2039,
			2053,2063,2069,2081,2083,2087,2089,2099,2111,
			2113,2129,2131,2137,2141,2143,2153,2161,2179,
			2203,2207,2213,2221,2237,2239,2243,2251,2267,
			2269,2273,2281,2287,2293,2297,2309,2311,2333,
			2339,2341,2347,2351,2357,2371,2377,2381,2383,
			2389,2393,2399,2411,2417,2423,2437,2441,2447,
			2459,2467,2473,2477,2503,2521,2531,2539,2543,
			2549,2551,2557,2579,2591,2593,2609,2617,2621,
			2633,2647,2657,2659,2663,2671,2677,2683,2687,
			2689,2693,2699,2707,2711,2713,2719,2729,2731,
			2741,2749,2753,2767,2777,2789,2791,2797,2801,
			2803,2819,2833,2837,2843,2851,2857,2861,2879,
			2887,2897,2903,2909,2917,2927,2939,2953,2957,
			2963,2969,2971,2999*///429
	};
	for (int j=0;j<167;j++ )
	{
		if(!Judge(big%SMALL_PRIMES[j],0)){
//			cout<<"not";
			return false;
		}
	}
	return true;
}

int Fermat_primes[]={3,17,65537};
int fit_next_steps_to_choose_e(Big & big){
	for(int i=0;i<3;i++){
		if ((Judge(big%Fermat_primes[i],1))){
//			cout<<endl<<i<<endl;
			return ++i;
		}
	}
	return 0;
}
bool fit_next_steps_to_choose_e(Big & big,int count){
	if ((Judge(big%Fermat_primes[--count],1)))
		return true;
	return false;
	
}