main.cpp

RSA公钥密钥生成程序,C++语言编写,采用了自己的大数类,可在短时间内生成1024位的RSA公钥和密钥,内有详细注解

#include <iostream>
#include <fstream>
#include <time.h>
#include <stdlib.h>
#include "BigInt.h"
#include "primer.h"
using namespace std;

//RabinMiller检测,每一轮成功率为75%.N为待检测的素数.
bool RabinMiller(const BigInt& n)
{
	BigInt r,a,y;
	unsigned int s,j;
    r=n-1;
	s=0;

	//找到令N-1=2^S*R的S和R,R为奇数
	while(!r.IsOdd())
	{
		s++;
		r>>1;
	}
 
	//产生一个小于N-1的检测随机数
	a.Randomsmall();
	
	y=PowerMode(a,r,n);

	//检测J=2至J<S轮
	if((!(y==1))&&(!(y==(n-1))))
	{
		j=1;
		while((j<=s-1)&&(!(y==(n-1))))
		{
			y=(y*y)%n;
			if(y==1)
				return false;
			j++;
		}
		if(!(y==(n-1)))
			return false;
	}
	return true;
}

//产生一个素数
BigInt GeneratePrime()
{
	BigInt n;
	int i;

	while(i<5)
	{
		//产生一个待测素数
		SortPrime(n);
		i=0;
		//进行五轮RABINMILLER测试,五轮全部通过则素数合格
		//理论素数合格率达99.9%
		for(;i<5;i++)
		{
			cout<<"进行第"<<i+1<<"轮RabinMiller测试"<<endl;
			if(!RabinMiller(n))
			{
				cout<<"测试失败!"<<endl;
				cout<<endl;
				break;
			}
		}
	}
	return n;
}

//求两个大数的最大公约数,采用辗转相除法
BigInt Gcd(const BigInt& m,const BigInt& n)
{
	if(n==0)
		return m;
	else
		return Gcd(n,m%n);
}

//用扩展欧几里德算法求乘法模逆
BigInt ExtendedGcd(const BigInt& a, const BigInt& b,BigInt& x, BigInt& y)
{
        BigInt t,d;   
        //如果一个操作数为零则无法进行除法运算
		if   (b==0)   
		{
			x=1;
			y=0;
			return a;
		} 
        d=ExtendedGcd(b,a%b,x,y);   
        t=x;   
        x=y;   
        y=t-((a/b)*y);   
        return d;   
}


main()
{
	srand((unsigned)time(NULL));
	ofstream outfile("liujin.txt");

	cout<<"***************************RSA公钥密钥产生程序*****************************"<<endl;
	cout<<"***********************作者:刘瑾 学号:012003025803*************************"<<endl;
	cout<<endl;

	cout<<"********随机产生p,q********"<<endl;
	cout<<endl;
	BigInt p=GeneratePrime();
	cout<<endl;
	cout<<"产生p:"<<endl;
	p.display();
	cout<<endl;
	BigInt q=GeneratePrime();
	cout<<endl;
	cout<<"产生q:"<<endl;
	q.display();
	cout<<endl;
	
	cout<<"********密钥生成********"<<endl;
	cout<<endl;
	cout<<"公钥e:"<<endl;
	BigInt t=(p-1)*(q-1);
	BigInt e,x,y,temp;
	while(1)
	{
		e.Random();
		//产生与T互质的E
		while(!(Gcd(e,t)==1))
			e.Random();
		temp=ExtendedGcd(e,t,x,y);
		temp=(e*x)%t;
		if(temp==1)
			break;
	}
	e.display();
	outfile<<"公钥e:"<<endl;
	outfile<<e;
	cout<<endl;
	
	cout<<"公钥n:"<<endl;
	BigInt n=p*q;
	n.display();
	outfile<<"公钥n:"<<endl;
	outfile<<n;
	cout<<endl;
	
	cout<<"私钥d:"<<endl;	
	BigInt d=x;
	d.display();
	outfile<<"私钥d:"<<endl;
	outfile<<d;
	cout<<endl;

	cout<<"********密钥检测********"<<endl;
	cout<<endl;
	cout<<"待检测的数据:"<<endl;	
	BigInt test;
	test.Random();
	test.display();
    outfile<<"原文test:"<<endl;
	outfile<<test;
	cout<<endl;

	cout<<"加密后的密文:"<<endl;
	BigInt encrypt=PowerMode(test,d,n);
	encrypt.display();
    outfile<<"密文encrypt:"<<endl;
	outfile<<encrypt;
	cout<<endl;
	
	cout<<"解密后的明文:"<<endl;	
	BigInt decrypt=PowerMode(encrypt,e,n);
	decrypt.display();
    outfile<<"明文decrypt:"<<endl;
	outfile<<decrypt;

	cout<<endl;
	cout<<"********产生的公钥和私钥已输出到当前文件夹下的liujin.txt中********"<<endl;
}