RSA算法

RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
　　RSA的算法涉及三个参数，n、e1、e2。
　　其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
　　e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
　　(n及e1),(n及e2)就是密钥对。
　　RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n；
　　e1和e2可以互换使用，即：
　　A=B^e2 mod n；B=A^e1 mod n;

下面是加密函数：

encrypt.h

#ifndef EN
#define EN
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h >
#include<time.h>

void TxtEncrypt(unsigned* cipSourceTxt, int buffSize, unsigned int Ke, unsigned int model)//对原文进行加密并覆盖原缓冲区
{
 int i;
 for( i=0; i < buffSize; i++ )
 {
  cipSourceTxt[i] = GetOutNum( cipSourceTxt[i], Ke, model );//求b的e次方除d的余数
 }
}

unsigned int GetOutNum(unsigned int b,unsigned int e , unsigned int d)//求b的e次方除d的余数
{
 unsigned int i;
 unsigned int outNum= 1;
 for( i=0; i < e; i++)//用了乘的模 等于 模的乘
 {
  outNum *= b;
  if( outNum >= d )
  {
   outNum %= d;
  }
  if(!outNum)
   return outNum;
 }
 return outNum%d;
}

#endif

私钥生成部分：

PR_produce.h

/*PR_produce.h*/
#ifndef PR_produce
#define PR_produce
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h >
#include<time.h>


int Produce_RSA_Key(unsigned int Ke, unsigned int Kd)
{
	unsigned int ao_la;
	unsigned int p;
	unsigned int q;
	unsigned int* model;


	RandSelect_pq(p,q);

	if( Count_N_AoLa_Num(p, q, ao_la) )//算出p*q的欧拉值
	{
		if( RandSelect_e(ao_la, Ke) )//随机选择公钥e
		{
//*Kd= GetOutNum (*Ke, CountAnyNumAola(ao_la)-1 ,ao_la) ;
//注：求Kd还是不用 x= a^(n'的欧拉数 - 1) mod n' (其中n'= (p-1)*(q-1) ),因n'的//欧拉数也不好求
			if( OverOneNum(Ke, ao_la, Kd) )//利用加的模等于模的加求e*d = 1 mod model 中的d
			{
				*model= p*q;
			}
		}
	}
	return Kd;
}

int JudgePrime(unsigned int prime)//判prime是否为素数
{
 unsigned int i;
 unsigned int limit= (unsigned int)sqrt( (double)prime );
 for(i=2; i <= limit; i++)
 {
  if(prime%i==0)
  {
   return 0;
  }
 }
 return 1;
}



int Count_N_AoLa_Num(unsigned int p, unsigned int q, unsigned int ao_la)//算出p*q的欧拉值
{
 if( !JudgePrime(p) )
  return 0;
 if( !JudgePrime(q) )
  return 0;
 ao_la = (p-1)*(q-1);
 return 1;
}

unsigned int CountCommonData(unsigned int a, unsigned int b)//求两个数的最大公因数
{
 unsigned int c ;
 if( c= a%b )
  return CountCommonData(b,c);
 else
  return b;
}

unsigned int RandSelect_pq(unsigned int p,unsigned int q) {
	srand(time(0));
	do {
		p = rand()%20;
	}while(!JudgePrime(p));

	do {
		q = rand()%20;
	}while(!JudgePrime(q));
	return p,q;
}

int RandSelect_e( unsigned int ao_la, unsigned int e )//随机选择公钥e
{
 unsigned int tmp;
 unsigned int div;
 if( ao_la <= 2 )
 {
  return 0;
 }
 srand( time(0) );
 div= ao_la - 2;
 do
 {
  tmp = ( (unsigned int)rand()+90 ) % div + 2;
 }while( CountCommonData(tmp, ao_la)!=1 );//求两个数的最大公因数
 e = tmp;
 return 1;
}

unsigned int GetOutNum(unsigned int b,unsigned int e , unsigned int d)//求b的e次方除d的余数 
{
	unsigned int i;
	unsigned int outNum= 1;
	for( i=0; i<e; i++)//用了乘的模 等于 模的乘
	{
	outNum *= b;//==============b d如果长过16位，很有可能溢出
	if( outNum >= d )
	outNum %= d;
	if(!outNum)
	return outNum;
	}
	return outNum%d;
}

int OverOneNum(unsigned int e,unsigned int model, unsigned int d)//利用加的模等于模的加求e*d = 1 mod model 中的d
{
	unsigned int i;
	unsigned int over= e;
	for(i=1; i<model; )
	{
		over= over % model;
		if( over==1 )
		{
			d = i;
			return 1;
		}
		else
		{
			if(over+e<= model)
			{
				do
				{
					i++;
					over += e;
				}while( over+e <= model );
			}else
			{
				i++;
				over +=e;
			}
		}
	}
	return 0;
}

unsigned int CountAnyNumAola(unsigned int number)//求任意大于1的整数的欧拉值
{
 unsigned int ao_la= 1;
 unsigned int i;  if( number<=1 )
  printf("本函数不处理2以下的范围!\n");
 for(i=2; i<number ; i++)
 {
  if( CountCommonData(number, i)==1 )
   ao_la ++;
 }
 return ao_la;
}

#endif

主函数部分：

RSA1.0.cpp

// RSA1.0.cpp : 定义控制台应用程序的入口点。
//
#include"encrypt.h" 
#include"PR_produce.h"
#include "stdafx.h"
#include<iostream>


void main() {
	char ke[1000]={0};
	char kd[1000]={0};
	char plain[1000]={0};
	char cipher[1000]={0};

	printf("请输入e\n");
	getchar();
	gets(ke);
	int i;

	unsigned int cke = (unsigned int)ke;
	unsigned int ckd = (unsigned int)kd;


	i = JudgePrime(cke);

	//




	////printf("请输入明文\n");
	////getchar();
	////gets(plain);
}

注：RSA算法主要解决的就是在模幂运算中的算法，要保证计算不会溢出就不能用普通的先幂后模的加密解密方法，那样的话遇到大点的字母必将溢出。