heck_prime.cpp

RSA对称、非对称加密解密算法

/******************************************************
素数检测：
	Close["D:\\usbkey\\RSA\\tmp.txt"]
			Clear[i, result, v]
			For[i = 1; v = Read["D:\\usbkey\\RSA\\tmp.txt", {Number}], 
			  i < 300, i++, result =PrimeQ[v[[1]]]; Print[result]]
******************************************************/
#include "StdAfx.h"
#include ".\heck_prime.h"
#include <stdio.h>
#include <math.h>
#include ".\SmallPrime.h"

Check_Prime::Check_Prime(void)
{
}

Check_Prime::~Check_Prime(void)
{
}
void Check_Prime::generate_small_prime(unsigned int mymax)
{
	bool prime;
	unsigned int i,j,number=0;
	for(i=3;i<=mymax;i++)
	{
		prime=true;
		for(j=2;j<=sqrt((double)i);j++)
		{
			if(i%j==0)
			{
				prime=false;
				break;
			}
		}
		if(prime)
		{
			number++;
			printf(",%u",i);
		}
	}
	printf("\n%u\n",number);
	return;
}
//返回0表示是通过了小素数检验，其他数字是他的第一个因子
unsigned int Check_Prime::small_prime_check(unsigned int *small_prime)
{
	for(unsigned int i=1;i<small_prime[0];i++)
	{
		if(this->number.Mod((long)small_prime[i])==0)
		{
			return small_prime[i];
		}
	}
	return 0;
}
/*****************************************************************************
					Miller-Rabin素性检验算法
Input:一个奇整数n（n＞＝３）以及一个安全参数　t＞＝１
Output:n是合数或者可能是一个素数
１．让Ｎ－１＝２＾Ｓ＊Ｒ　Ｒ必须为奇数
２．Ｉ＝１；Ｉ＜＝Ｔ；Ｉ＋＋
	２．１　随机选取Ａ,（Ａ大于等于２，小于等于Ｎ－１）
	２．２　计算Ｙ＝Ａ＾Ｒmod N
	２．３　如果Ｙ不等于１且不等于Ｎ－１
			２．３．１　Ｊ＝１
			２．３．２　如果Ｊ小于等于Ｓ－１且Ｙ不等于Ｎ－１
						２．３．２．１　Ｙ＝Ｙ＾２　mod  Ｎ
						２．３．２．２　如果Ｙ不等于Ｎ－１　返回是合数
			２．３．３　如果Ｙ不等于Ｎ－１　返回是合数
３．返回可能是素数

通过测试，发现误判的可能性非常小，已经达到了我们非常满意的地步了

不过在冯登国和周玉洁两位密码学前辈的<公开密钥密码算法及其快速实现＞一书中
在这个地方是有问题的，我就是依据他们的算法来写的，可是检验的时候发现有问题
都是我很钦佩的密码学方面的专家

*****************************************************************************/
//返回0表示是合数，返回１表示可能是素数
unsigned int Check_Prime::prime_check(unsigned int iterator)
{
	int isprime=1;//默认为这个数位素数
	unsigned int small_check_result,weishu,i,j;
	CBigInt n_1(this->number.base),q(this->number.base),p(this->number.base),y;
	//如果数字本身为1，返回0
	if(this->number.Cmp(1)==0)
	{
		return 0;
	}
	small_check_result=this->small_prime_check(smallprime);
	//if(this->number.Cmp(small_check_result
	if(small_check_result!=0)
	{
		if(this->number.Cmp(small_check_result)==0)
			return 1;//
		else
			return 0;
	}
	//如果iterator==0说明由大数的位数载错误概率小于2E-80的条件下确定最优迭代次数
	if(iterator==0)
	{
		//确定被测验的大数的位数，只能大概估计，100000000大约为27位，0x100000000为32
		if(this->number.base==100000000)
		{
			weishu=27*this->number.m_nLength;
		}
		else
		{
			weishu=32*this->number.m_nLength;
		}
		if	(weishu<	73)	iterator=37;
		else if (weishu< 105) iterator=32;
		else if (weishu< 137) iterator=25;
		else if (weishu< 197) iterator=19;
		else if (weishu< 220) iterator=15;
		else if (weishu< 235) iterator=13;
		else if (weishu< 253) iterator=12;
		else if (weishu< 275) iterator=11;
		else if (weishu< 300) iterator=10;
		else if (weishu< 332) iterator=9;
		else if (weishu< 375) iterator=8;
		else if (weishu< 433) iterator=7;
		else if (weishu< 514) iterator=6;
		else if (weishu< 638) iterator=5;
		else if (weishu< 847) iterator=4;
		else if (weishu<1275) iterator=3;
		else if (weishu< 2861) iterator=2;
		else iterator=1;
	}
	n_1.Mov(this->number);
	n_1.Mov(n_1.Sub(1));
	weishu=Fact_Two(n_1,q);//这个地方是值得重点检查的地方

	//开始进行运算
	
	i=1;
	isprime=1;
	do
	{
		unsigned int tmp=smallprime[i++];
		p.Mov(tmp);
		y.Mov(p.Mon(q,this->number));//y=p^q mod n
		
		if((y.Cmp(1)!=0)&&(y.Cmp(n_1)!=0))//相等为０，大于为１，小于为－１；
		{
			j=1;
			//求平方，只要y不同于＋１和－１且weishu-1次迭代还没有执行完
			while((y.Cmp(n_1)!=0)&&(j<weishu))
			{
				y.Mov(y.Mul(y));
				y.Mov(y.Mod(this->number));
				if(y.Cmp(1)==0)
				{
					isprime=0;
					break;
				}
				j++;
			}
			if(y.Cmp(n_1)!=0)
			{
				isprime=0;
			}
		}
	}while(((--iterator)>0)&&isprime);
	return isprime;
}

//分解n-1=2的k次方*q;
unsigned int Check_Prime::Fact_Two(CBigInt n,CBigInt& q)
{
	unsigned int k=0;
	while(n.Is_Even())
	{
		n.Mov(n.Div(2));
		k++;
	}
	q.Mov(n);
	return k;
};