rsa.cpp

本程序实现了用RSA加密算法加密、解密图片。本程序仅作为RSA原理理解

#include<iostream>
#include<time.h>
#include "rsa.h"

using namespace std;

int getprime()
{
//----------------符合要求的素数表---------------------
int prime[19] = {151, 157, 163, 167, 173, 179, 181, 191, 193, 
			197, 199, 211, 223, 227, 229, 233, 239, 241, 251}; 
	int a;
	srand(time(NULL));
	a = rand()%19;
	return prime[a];
}

int Generate_Prime()						//生成(128~256)的奇素数
{
	int a;
	srand((unsigned)time(NULL));
	a = rand()%UPPER_LIMIT;
	if(a%2 == 0)
		a += 1;
	while(a<LOWER_LIMIT || !Prime_test(a))
	{
		a = rand()%UPPER_LIMIT;
		if(a%2 == 0)
			a += 1;
	}
	return a;								//a是大奇素数
}

bool Prime_test(int n)						//因为需要判断的数是p、q，都在int范围内，											
{											//所以是int类型
	//Miller_Rabin(n)算法 实现的素性测试

//----------------n-1 = 2^k * m-----------------------
	int temp1, temp2, k = 0;	
	temp1 = n - 1;					
	temp2 = temp1%2;
	while(temp2 == 0)
	{
		temp1 = temp1 / 2;
		k++;
		temp2 = temp1%2;		
	}
// 此时获得的temp1就是奇数m

//-----------------产生随机数 a = (1, n-1)-------------
	int a;	
	srand((unsigned)time(NULL));
	a = rand()%(n - 1) + 1;			// 1<=a<=n-1

//-----------------------------------------------------
	int b = 1;
	for(int i=0; i<temp1; i++)		//求a的m次方
	{
		b = (b*a)%n;	
	}

	if((b%n) == 1)					// n is prime
		return true;			
	for(i=0; i<k-1; i++)
	{
		if((b%n) == -1)
			return true;
		else
			b = (b*b)%n;		
	}
	return false;
}

int gcd(unsigned int a, unsigned int b)				//用扩展Euclidean算法实现求最大公约数
{
	unsigned int a0, b0;	
	int t0, t, s0, s, r, temp, q;

	a0 = a;
	b0 = b;
	t0 = 0;
	t = 1;
	s0 = 1;
	s = 0;
	q = a0/b0;
	r = a0 - q*b0;
	while(r>0)
	{
		temp = t0 - q*t;
		t0 = t;
		t = temp;
		temp = s0 - q*s;
		s0 = s;
		s = temp;
		a0 = b0;
		b0 = r;
		q = a0/b0;
		r = a0 - q*b0;
	}
	r = b0;
	return (int)r;
}

unsigned int Inverse(unsigned int m, int b)
{
	unsigned int a0, t, q;
	int t0, r, b0, temp;

	a0 = m;
	b0 = b;
	t0 = 0;
	t = 1;
	q = a0/b0;
	r = a0 - q*b0;
	while(r>0)
	{
		temp = (t0 - q*t)%m;
		t0 = t;
		t = temp;
		a0 = b0;
		b0 = r;
		q = a0/b0;
		r = a0 - q*b0;
	}
	if(b0 != 1)	
		return -1;			// b没有摸m的逆	
	else
		return t;
}
//------------------------------------------------------
unsigned int Reciprocal_u(unsigned int  m, unsigned int u)
{
	unsigned int n1=m;
	unsigned int n2=u;
	long b1=0;
	long b2=1;
	long t;
	unsigned int q;
	unsigned int r;
	do
	{
		q=n1/n2;
		r=n1-q*n2;
		if (r==0) 
			break;
		n1=n2;
		n2=r;
		t=b2;
		b2=b1-q*b2;
		b1=t;
	}
	while (1);

	if (n2!=1)
		return (0);   //不存在
	if (b2<0)
		return (b2+m);
	else
		return (b2);
}

RSA_Key RSA_Para()						//生成RSA参数
{
	int p, q;
	unsigned int n, m, a;
	int b;
	RSA_Key KEY;

	p = getprime();			
A:	q = p;
	while(q == p)
		q = getprime();
	n = p*q;
	if(n<32768)
	{
		goto A;
	}
	m = (p-1)*(q-1);		// m为 fi(n)

	srand(time(NULL));

	b = 2;
B:	while(gcd(b, m) != 1)
	{
		b++;
	}
	
//	a = Inverse(m, b);		//求b模m的逆
	a = Reciprocal_u(m, b);
	
	if(a == -1)
	{
		b++;				
		goto B;
	}

	if((a*b)%m != 1)
	{
		b++;
		goto B;
	}

	KEY.n = n;			//公钥
	KEY.b = b;

	KEY.a = a;			//密钥
	KEY.p = p;
	KEY.q = q;
	return KEY;
}

int BitsNum(unsigned int c)
{
	int k=1;
	while((c/=2)!=0)
		k++;	
	return k;
}

unsigned int Square_Multiply(unsigned int x, unsigned int c, unsigned int n)
{
	unsigned int z = 1;
	int l = BitsNum(c);							//计算c的长度
	
	bool *tmp = new bool[l];					//将c转化成2进制数
	if(c%2 == 0)
		tmp[0] = 0;
	else
		tmp[0] = 1;
	int i=1;
	while((c/=2) != 0)
	{
		if(c%2==0)
			tmp[i] = 0;
		else
			tmp[i] = 1;
		i++;
	}

	for(i=l-1; i>=0; i--)			//执行平方乘算法
	{
		z = (z*z)%n;
		if(tmp[i] == 1)
			z = (z*x)%n;
	}
	return z;
}

unsigned int MONmod(unsigned int x,unsigned int r,unsigned int n)
{
	unsigned int a,b,c;
	a=x;
	b=r;
	c=1;
	while (b!=0)
	{
		if ((b&0x01)==0)
		{
			b=b/2;
			a=(a*a)%n;
		}
		else
		{
			b=b-1;
			c=(a*c)%n;
		}
	}
	return c;
}