encrypt.cpp

RSA加密算法的实现 2^1024大的素数实现

#include"function.h"
#include<fstream>
#include<string>

using namespace std;
/*--------------------------------------------------------------
  Instruction:
  a,b satisfied that GCD(a,b)=1;find x s.t: x*a + y*b = 1.
  we know that the famous GCD(a,b) algorithm, we get the result
  when b = 0,namely a = 1,we can iterate forware to get x and y.
  --------------------------------------------------------------*/
mathInt ex_euclid(mathInt a ,mathInt b)
{
	mathInt x = 1,y = 0,u = 0,v = 1;
	mathInt ori_b = b;
    mathInt temp1,temp2;

	while(!(b==ZERO))
	{
		mathInt quotient = a/b;
		mathInt remainder = a%b;

		temp1 = x - quotient*u;//next item :that  is new u;
		temp2 = y - quotient*v;//next item : that is new v;

		x = u;//iterating
		y = v;
		u = temp1;
		v = temp2;
     
		a = b;
		b = remainder;
	
	}
	while(!x.is_pos())
		x = x + ori_b;//note that if x*a + y*b = 1  --> if x is negative
	                   //we can always find a positive x through (x+b)*a + (y-a)*b = 1;
	return x;
}
/*-------------------------------------------------------------
  Instruction:First,we might as well use e=3 as the public key.
  We random generate two prime here,then fai_n = (p-1)*(q-1),
  GCD(3,fai_n)=1,use ex_euclid to get the private key.Then output
  public base(p*q) and private key to .txt files.
  ---------------------------------------------------------------*/
void GenerateKey()
{
	mathInt p, q, fai_n, n, key;
	
    srand(time(NULL));//在这儿srand 就不会产生出相同的随机数了~
    p = GeneratePrime();
	cout<<"P is:"<<endl; p.display();
	q = GeneratePrime();
	cout<<"Q is:"<<endl; q.display();
	fai_n = (p-1)*(q-1);

	while(fai_n%3==ZERO||p==q)//fai_n and 3 must satisfied that GCD(fai_n,3)=1;and to make sure that p!=q;
	{
		if((p-1)%3==ZERO)
		{
			p = GeneratePrime();
			cout<<"Regenerated P~"<<endl; p.display();
		}
		else
		{
			q = GeneratePrime();
			cout<<"Regenerate Q~"<<endl; q.display();
		}
		fai_n = (p-1)*(q-1);
	}
	n = p*q;//public base;
	key = ex_euclid(3,fai_n);//private key;

	cout<<"n is:"<<endl; n.display();
	cout<<"Private key is a secret~"<<endl;
	n.OutToFile("public_base.txt");//output the public base and private key to a txt file;
	key.OutToFile("private_key.txt");
	
}
void encrypt(void)//n is the base;
{
	ifstream fileIn;
	int i = 0;
	vector<int> v(VSIZE);
	mathInt n = GetFromFile("public_base.txt");
	int n_len = n.length();

	fileIn.open("FileToEncrypt.txt");
	ofstream clear("FileEncrypted.txt");//if the file has been existed, make sure it be recreated.
	clear.close();
	while(fileIn.peek()!=EOF)
	{
		while(fileIn.peek()!=EOF&&i<=n_len-2)//以n_len-1 作为encrypt 的长度,这样就保证了 encrypt<n;
		{
		   v[i] = fileIn.get();//in order that blanks won't be missed
		   i++;
		}//注意。空格也要读！！！！！！！！
		
		mathInt enpt(1,v);
		mathInt c = QuickMod(enpt,3,n);//c is the encrypted information;
		c.OutToFile("FileEncrypted.txt");

		i = 0;
	    for(int j=0;j<=VSIZE-1;j++)
		   v[j] = 0;	
	}
}
void decode(void)
{
	ifstream fileIn;
	int i=0, length = 0;
    bool sign;
	vector<int> v(VSIZE);
	mathInt n = GetFromFile("public_base.txt");
	mathInt my_key = GetFromFile("private_key.txt");
   
	ofstream clear("FileDecoded.txt");//if the file has been existed, make sure it recreated.
	clear.close();
	fileIn.open("FileEncrypted.txt");
	while(fileIn.peek()!=EOF)
	{
         fileIn>>sign;
		 fileIn>>length;
		 while(i<=length-1&&fileIn.peek()!=EOF)
		 {
			fileIn>>v[i];
			 i++;
		 }
		 mathInt c(1,v);
		 mathInt m = QuickMod(c,my_key,n);//m is the original information
		 m.OutToString("FileDecoded.txt",1);
		 i = 0;
	     for(int j=0;j<=VSIZE-1;j++)
		    v[j] = 0;
	}
}
//to get a mathInt from a appointed file.
mathInt GetFromFile(char* name)
{
	ifstream Inf(name);
    vector<int> v(VSIZE);
	int i=0;
	bool sign;
	int length;
    
	Inf>>sign;
	Inf>>length;
	while(Inf.peek()!=EOF&&i<=length-1)//get the public base from a public txt file;
	{
		Inf>>v[i];
		i++;
	}
	return mathInt(sign,v);
}