www.pudn.com > VC++RSA.rar > RSAUpper.cpp

// 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。如果jp-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))) 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<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> ");  
	scanf("%ld",&m); 
	printf("a=%ld b=%ld n=%ld PHI=%ld\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); 
	 
	c=MONmod(m,e,n); 
	/* when e is relatively large */ 
	printf("encrypt Message is %ld \n",c); 
	printf("e=%ld d=%ld c=%ld\n",e,d,c); 
	m=decrypt(c,n,d); /* this function required as c to */ 
	/*the power of d causes an overflow */ 
	printf("decrypt Message is %ld \n",m); 
	scanf(""); 
	return(0); 
}