rsa_alg_crypt.cpp

32bit的rsa密码算法

//

#include "stdafx.h"
#include <windows.h>
#include <conio.h>
#include <stdlib.h>
#include <fstream.h>
#include <io.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <ostream.h>
#include <time.h>


//求两数的最大公约数
int gcd(int x,int y)
{
	int g;
	if(x<0)
		x=-x;
	if(y<0)
		y=-y;
	if(x*y==0)
	{
		printf("参数中不可能有0值!\n");
		return -1;
	}
	g=y;
	while(x>0){
		g=x;
		x=y%x;
		y=g;
	}
	return g;
}
//在32位运算域，只能作16位RSA加密
#define PRIME_BITS 8 //随机数位数(8位)
#define KEY_BITS (PRIME_BITS*2) //密钥长度位
#define PACKAGE_MAX_SIZE (~(0xFFFF8<<KEY_BITS-4)) //0x7fff
//分组比公钥小一位
//以时钟为随机种子产生素数
unsigned long  RandGetPrime()
{
	unsigned long ui(0);
	unsigned temp(0);
	int k;
	bool isPrime=false;
	while(isPrime==false)
	{
		srand(GetTickCount());
		
		
		temp=rand();
		//随机地产生一个数,
		while(temp<1<<PRIME_BITS-1) temp=(temp*7+11); //最小位满足
		temp=temp%(1<<PRIME_BITS);//不会长于规定位
		k=2;
		//产生公钥满足位长度
		if(temp>sqrt(1<<KEY_BITS-1))
		{
			for( k=2;k<=(int)sqrt(temp);k++) 
			{
				if(temp%k==0) break;//没有约数
			}
			
			if(k>(int)sqrt(temp)) isPrime=true;//即为素数
			
		}
	}
	return temp;
}
#define isEven(x) ((x&0x1)==0) //是偶数
#define isOdd(x) (x&0x1)		//是奇数
#define swap(x,y) (x^=y,y^=x,x^=y) //交换两数
//扩展欧几里得算法u,v的最大公约数，
//a*u-b*v=igcd;
//bv=a*u-igcd;
//(u-b)*v=u*v-a*u+igcd=(v-a)*u+igcd
//如果igcd=1；则(u-b)*v≡1%u
void GetInverse_ExtEuclid(int *u,//模
						  int *v,//已知数
						  int *a,//为系数
						  int *b,//u-b为逆元
						  int *igcd //gcd最大公约数
						  )
{
	int k ,t1,t2,t3;
	if(*u<*v) swap(*u,*v);
	for(k=0;isEven(*u)&&isEven(*v);++k){
		*u>>=1;*v>>=1;
	}
	*a=1;*b=0;*igcd=*u;t1=*v;t2=*u-1;t3=*v;
	do{
		do{
			if(isEven(*igcd)){
				if(isOdd(*a)||isOdd(*b)){
					*a+=*v;*b+=*u;
				}
				*a>>=1;*b>>=1;*igcd>>=1;
			}
			if(isEven(t3)||*igcd<t3){
				swap(*a,t1);swap(*b,t2);swap(*igcd,t3);
			}
		}while(isEven(*igcd));
		while(*a<t1||*b<t2){
			*a+=*v;*b+=*u;
		}
		*a-=t1;*b-=t2;*igcd-=t3;
	}while(t3>0);
	while(*a>=*v&&*b>=*u){
		*a-=*v;*b-=*u;
	}
	*a<<=k;*b<<=k;*igcd<<=k;
}

//加法链
//返回pow(x,y) mod n 值
unsigned long qe2(unsigned long x,unsigned long y,unsigned long n)
{
	unsigned long s,t,u;

	s=1;t=x;u=y;
	while(u){
		if(u&1) s=(s*t)%n;
		u>>=1;
		t=(t*t)%n;
	}
	return (s);
}

void Sample()
{
	unsigned long p(3);//素数
		unsigned long q(3);//素数
		unsigned long r(0);//私钥
	//相异素数，且满足软件加速采用固定m=17
	while(p==q||gcd(17,(q-1)*(p-1))!=1){
		p=RandGetPrime();//得一随机素数
		Sleep(rand()%1000);//等待10秒
		q=RandGetPrime();
	}
	printf("p:%d\n",p);	
	printf("q:%d\n",q);

	int a;//欧几里得系数
	int b;//欧几里得系数
	int igcd;//最大公约数
	
	int u(17);//公钥指数
	int EulerValue;//欧拉函数值
	EulerValue=(p-1)*(q-1);

/*	//求出素数的逆元

	for(int i=1;i<u;i++){
		v=i;
		x=i;
		y=i;
		
		GetInverse_ExtEuclid(&u,&v,&a,&b,&igcd);
		//cout<<a<<"*"<<u<<"+(-"
		//	<<b<<")*"<<v<<"="<<gcd<<endl;
		if(igcd==1);
		cout<<"the inverse of "<<v<<" mod "<<u<<" is: "<<u-b<<endl;
		
		//cout <<x<<"^"<<y<<" mod "<<u<<"="<<qe2(x,y,u)<<endl;
		
	}
*/	



	
	int plaintext(32767);//明文

			while(plaintext>9999)
			{
			cout <<"\nPlease Input 明文(<10000 的整数!，4位十进制数.): ";
			cin >> plaintext;
			}

	printf("分组最大数值：%d\n",PACKAGE_MAX_SIZE);
	//分组为最小的KEY_BITS位数
//	plaintext=plaintext & (0x1<<KEY_BITS-1);
//	printf("%0X\n",PACKAGE_MAX_SIZE);
	int ciphertext;
	int decryptciphertext;
	GetInverse_ExtEuclid(&EulerValue,&u,&a,&b,&igcd);
	cout<<a<<"*"<<EulerValue<<"+(-"
	<<b<<")*"<<u<<"="<<igcd<<endl;
	if(igcd==1)
	{
		if(plaintext>PACKAGE_MAX_SIZE)
		{
			cout<<"分组太长，不能加密!\n"<<endl;
		//	return 0;
		}		//cout<<"the inverse of "<<v<<" mod "<<u<<" is: "<<u-b<<endl;
		//m=v;
	//	n=p*q;
		cout<<"RSA公钥：u="<<u<<"	n(pq)= "<<p*q<<"公钥位数: "<<KEY_BITS<<endl;
		//	printf("pq=%0X\n",p*q);

		cout <<"plaintext="<<plaintext<<endl;
		ciphertext=qe2(plaintext,u,p*q);
		cout <<"ciphertext="<<ciphertext<<endl;
		//扩展欧几里得算法u,v的最大公约数，
		//a*u-b*v=igcd;
		//bv=a*u-igcd;
		//(u-b)*v=u*v-a*u+igcd=(v-a)*u+igcd
		//如果igcd=1；则(u-b)*v≡1%u
		r=EulerValue-b;
		cout<<"RSA私钥：r="<<r<<"	n(pq)="<<p*q<<endl;
		decryptciphertext=qe2(ciphertext,r,p*q);
		cout<<"decryptciphertext="<<decryptciphertext<<endl;
		if(plaintext==decryptciphertext)
		{
			cout<<"正确加解密!\n"<<endl;
		}
		else
			cout<<"加解密错误!\n"<<endl;
			//cout<<"the inverse of "<<v<<" mod "<<u<<" is: "<<u-b<<endl;
		
	}
	else
	{
		cout<<"no inverse"<<endl;
	}
}
void DisplayHelpInfo()
{
	cout <<"输入r:启动RSA(32bit)加密;以时钟为随机种子产生素数!\n";
//	cout <<"输入r:无种子，演示随机数发生器rand()!\n";
//	cout <<"输入s:有种子，每次取时间值为种子,演示随机数发生器srand()!\n";
//	cout <<"输入i:有种子，每次用户输入值为种子,演示随机数发生器srand()!\n";
	cout <<"输入h:获得命令帮助!\n";
	cout <<"输入e:退出程序!\n";
	cout <<"请输入指令:";
}

int main(int argc, char* argv[])
{
	char command;

	printf("\n");
	DisplayHelpInfo();
loop:
	
	cin >> command;
	switch (command)
	{
	case 'r':
		{
	Sample();			
//	char KeyStr[]="abc";
//	char strPlain[]="Hello World";

			DisplayHelpInfo();
			goto loop;
		}

	case 'e':
		{
			return;
		}
		
	case 'h': ;
		
			  {
				  DisplayHelpInfo();
				  goto loop;
			  }
	default:goto loop;
	}

	return ;
}