rsaupper.cpp

计算机密码学第二版卢开澄这本书后附的RSA源码

// RSAUpper.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define TRUE 1
#define FALSE 0
#define VLONG    unsigned long
//参考书：《计算机密码学》（第二版）卢开澄 清华大学出版社
//模幂算法，快速计算：x^r(mod p)，p76
VLONG MONmod(VLONG x,VLONG r,VLONG p)
{
	VLONG a,b,c;
	a=x;
	b=r;
	c=1;
	while (b!=0)
	{
		if ((b&0x01)==0)
		{
			b=b/2;
			a=(a*a)%p;
		}
		else
		{
			b=b-1;
			c=(a*c)%p;
		}
	}
	return c;
}
/*
 * Rabin-Miller
 * 这是个很容易且广泛使用的简单算法，它基于Gary Miller的部分象法，
 * 有Michael Rabin发展。事实上，这是在NIST的DSS建议中推荐的算法的一个简化版。 
 * 首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
 * （1） 选择一个小于p的随机数a。
 * （2） 设j=0且z=a^m mod p
 * （3） 如果z=1或z=p-1，那麽p通过测试，可能使素数
 * （4） 如果j>0且z=1, 那麽p不是素数
 * （5） 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p，然后回到(4)。
 *       如果z=p-1，那麽p通过测试，可能为素数。
 * （6） 如果j=b 且z<>p-1，不是素数
 * 这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花
 * 费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。

 * 实际考虑：
 * 在实际算法，产生素数是很快的。
 * （1） 产生一个n-位的随机数p
 * （2） 设高位和低位为1（设高位是为了保证位数，设低位是为了保证位奇数）
 * （3） 检查以确保p不能被任何小素数整除：如3，5，7，11等等。有效的方法
 *       是测试小于2000的素数。使用字轮方法更快
 * （4） 对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机
 *		 数a,在测试。选取较小的a值，以保证速度。做5次 Rabin-Miller测试如
 *		 果p在其中失败，从新产生p，再测试。
 */
//参考书：《计算机密码学》（第二版）卢开澄 清华大学出版社
//模幂算法，素数的米勒-勒宾(MIller-Rabin)概率测试法，p151
//输入:被 b要检测的数字,n素数产生的范围满足:(2<=b<n-1)
bool TestPrimeNum(VLONG b,VLONG n)
{
	VLONG m=1;
	VLONG l=0;
	VLONG V;
	VLONG i;
	while (m<(n-1)){m=m*2;l++;}
	if ((b<2)||(b>=(n-1))) return (false);
	V=MONmod(b,m,n);
	if (V==1) return (true);
	i=1;
	do
	{
		if (V==(n-1)) return (true);
		if (i==l) return (false);
		V=MONmod(V,2,n);
		i++;
	}
	while (1);
	return(false);
}
//参考书：《计算机密码学》（第二版）卢开澄 清华大学出版社
//求gcd{n1,n2}的快速算法，快速计算：gcd{n1,n2}=an1+bn2，p132
VLONG gcd(VLONG /*mod*/ n1,VLONG n2)
{
	VLONG c;
	VLONG t;
	if ((n1<0) || (n2<=0)) return 0;
	//s1
	c=0;
	//s2
	while ((n1%2==0)&&(n2%2==0))
	{
		n1=n1/2;
		n2=n2/2;
		c++;
	}
	//s3
	if  (n2%2==0)
	{
		t=n1;
		n1=n2;
		n2=t;
	}

	do
	{		
		//s4
		while (n1%2==0)
		{
			n1=n1/2;
		}
		//s5
		if ((long)(n1-n2)<0)
		{
			t=n1;
			n1=n2;
			n2=t;
		}
		//s6
		n1=(n1-n2)/2;
	}
	while (n1!=0);
	
	return (n2<<c);
}

//参考书：《计算机密码学》（第二版）卢开澄 清华大学出版社
//求u mod m的逆元素算法，快速计算：gcd{u,m}=au+bm=1，p136(替换getD)
VLONG Reciprocal_u(VLONG /*mod*/ m,VLONG u)   //私钥
{
	VLONG n1=m;
	VLONG n2=u;
	long b1=0;
	long b2=1;
	long t;
	VLONG q;
	VLONG 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);
}
//解密
VLONG decrypt(VLONG c,VLONG n, VLONG d)
{
	VLONG i,g,f;
	if (d%2==0) g=1; else g=c;
	for (i=1;i<=d/2;i++)
	{
		f=c*c % n;
		g=f*g % n;
	}
	return(g);
}
VLONG getD( VLONG e, VLONG PHI)
{
	VLONG u[3]={1,0,PHI};
	VLONG v[3]={0,1,e};
	VLONG q,temp1,temp2,temp3;
	while (v[2]!=0)
	{
		q=floor(u[2]/v[2]);
		temp1=u[0]-q*v[0];
		temp2=u[1]-q*v[1];
		temp3=u[2]-q*v[2];
		u[0]=v[0];
		u[1]=v[1];
		u[2]=v[2];
		v[0]=temp1;
		v[1]=temp2;
		v[2]=temp3;
	}
	if (u[1]<0) 
	     return(u[1]+PHI);
	else 
	     return(u[1]);
}
VLONG get_common_denom(VLONG e, VLONG PHI)
{
	VLONG great,temp,a;
	if (e >PHI)
	{
		while (e % PHI != 0)
		{
			temp= e % PHI;
			e =PHI;
			PHI = temp;
		}
		great = PHI;
	} 
	else
	{
		while (PHI % e != 0)
		{
			a = PHI % e;
			PHI = e;
			e = a;
		}
		great = e;
	}
	return(great);
}

VLONG getE( VLONG PHI)  //公钥
{
	VLONG great=0, e=2;
	while (great!=1)
	{
		e=e+1;
		great = gcd(e,PHI);
	}
	return(e);
}
void get_prime( VLONG *val)
{
	#define NO_PRIMES 39
	VLONG primes[NO_PRIMES]={3,5,7,11,13,
		                     17,19,23,29,31,
							 37,41,43,53,59,
							 61,67,71,101,103,97,
							 107,109,113,127,131,
							 137,139,149,151,157,
							 163,167,173,179,181,
							 191,193,197};
	VLONG prime,i;
	
	do
	{
		prime=FALSE;
		printf("Enter a prime number >> ");
		scanf("%ld",val);
		for (i=0;i<NO_PRIMES;i++)
			if (*val==primes[i]) 
				prime=TRUE;
	} 
	while (prime==FALSE);
}

int main(int argc, char* argv[])
{
	VLONG a,b,i,n,e,PHI,d,m[16],c[16];
	/*
	a=MONmod(123,7,187);
	a=MONmod(183,7,187);
	a=MONmod(72,7,187);
	a=MONmod(30,7,187);
	a=MONmod(1520,13,2537);
	a=get_common_denom(18,12);
	a=gcd(18,12);
	*/
    //bool result=TestPrimeNum(3,100);
	//result=TestPrimeNum(17,100);
	//result=TestPrimeNum(19,100);
	//result=TestPrimeNum(2001,10000);
	get_prime(&a);
	get_prime(&b);
	
	n=a*b;                         
	PHI=(a-1)*(b-1);
	e=getE(PHI);                    //公钥
	d= Reciprocal_u(PHI,e);         //私钥
	printf("Enter input value >> "); 
	for(i=0;i<16;i++)
	{scanf("%02x",&m[i]);}
	printf("a=%1d b=%1d n=%1d PHI=%1d\n",a,b,n,PHI);
	//模幂算法，快速计算：x^r(mod p)，p76
    //VLONG MONmod(VLONG x,VLONG r,VLONG p)
//	c=(VLONG)pow(m,e) % n; /* note, this may overflow with large numbers */
	//c=MONmod(5,173,323);
	//c=MONmod(5,173,323);
	printf("encrypt Message is  \n");
	for(i=0;i<16;i++)
	{	c[i]=MONmod(m[i],e,n);
	printf("%02x  ",c[i]);
	}
	/* when e is relatively large */

    printf(" \n");
	printf("gongyao=%1d siyao=%1d \n",e,d);
	printf("decrypt Message is  \n");
	for(i=0;i<16;i++)
	{m[i]=decrypt(c[i],n,d); /* this function required as c to */
	/*the power of d causes an overflow */
	printf("%02x  ",m[i]);}
	printf(" \n");
	scanf("");
	return(0);
}