www.pudn.com > 密聊源程序.rar > RSA.cpp

 
#include "stdafx.h" 
#include "SecretChat.h"	//应用程序头文件 
#include "RSA.h" 
#include 	//为了获得现在的时间 
 
#ifdef _DEBUG 
#undef THIS_FILE 
static char THIS_FILE[]=__FILE__; 
#define new DEBUG_NEW 
#endif 
 
 
 
/***************"vlong.cpp"********************/ 
//#include "vlong.h" 
static void assert ( long x ) 
{ 
	if (!x) 
	{ 
		char * z=0; 
		*z=0; 
	} 
} 
 
unsigned char bittab[256] = 
{ 
	0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 
		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8 
}; 
 
DWORD flex_unit::get( DWORD i ) const 
{ 
	if ( i >= n ) return 0; 
	return a[i]; 
} 
 
void flex_unit::clear() 
{ 
	n = 0; 
} 
 
flex_unit::flex_unit() 
{ 
	z = 0; 
	a = 0; 
	n = 0; 
} 
 
flex_unit::~flex_unit() 
{ 
	DWORD i=z; 
	while (i) { i-=1; a[i] = 0; } // burn 
	delete [] a; 
} 
 
void flex_unit::reserve( DWORD x ) 
{ 
	if (x > z) 
	{ 
		DWORD * na = new DWORD[x]; 
		for (DWORD i=0; ilimit) min = limit; 
	for (i=0; ilimit) min = limit; 
		DWORD c = 0; // carry 
		DWORD j; 
		for ( j=i; j>= 1; 
			if ( msw>= (1u<>= w; 
			} 
		} while (w>8); 
		x += bittab[msw]; 
	} 
	return x; 
} 
 
long vlong_value::cf( vlong_value& x ) const 
{ 
	if ( n > x.n ) return +1; 
	if ( n < x.n ) return -1; 
	DWORD i = n; 
	while (i) 
	{ 
		i -= 1; 
		if ( get(i) > x.get(i) ) return +1; 
		if ( get(i) < x.get(i) ) return -1; 
	} 
	return 0; 
} 
 
void vlong_value::shl() 
{ 
	DWORD carry = 0; 
	DWORD N = n; // necessary, since n can change 
	for (DWORD i=0;i<=N;i+=1) 
	{ 
		DWORD u = get(i); 
		set(i,(u<<1)+carry); 
		carry = u>>(BPU-1); 
	} 
} 
 
long vlong_value::shr() 
{ 
	DWORD carry = 0; 
	DWORD i=n; 
	while (i) 
	{ 
		i -= 1; 
		DWORD u = get(i); 
		set(i,(u>>1)+carry); 
		carry = u<<(BPU-1); 
	} 
	return carry != 0; 
} 
 
void vlong_value::shr( DWORD x ) 
{ 
	DWORD delta = x/BPU; x %= BPU; 
	for (DWORD i=0;i>= x; 
			u += (get(i+delta+1) << (BPU-x)); 
		} 
		set(i,u); 
	} 
} 
 
void vlong_value::add( vlong_value & x ) 
{ 
	DWORD carry = 0; 
	DWORD max = n; if (max>= 1; 
	} 
	return count&1; 
} 
 
void vlong_value::subtract( vlong_value & x ) 
{ 
	DWORD carry = 0; 
	DWORD N = n; 
	for (DWORD i=0;i= carry ) 
		{ 
			DWORD u = get(i); 
			DWORD nu = u - ux; 
			carry = nu > u; 
			set(i,nu); 
		} 
	} 
} 
 
void vlong_value::init( DWORD x ) 
{ 
	clear(); 
	set(0,x); 
} 
 
void vlong_value::copy( vlong_value& x ) 
{ 
	clear(); 
	DWORD i=x.n; 
	while (i) { i -= 1; set( i, x.get(i) ); } 
} 
 
vlong_value::vlong_value() 
{ 
	share = 0; 
} 
 
void vlong_value::mul( vlong_value& x, vlong_value& y ) 
{ 
	fast_mul( x, y, x.bits()+y.bits() ); 
} 
 
void vlong_value::divide( vlong_value& x, vlong_value& y, vlong_value& rem ) 
{ 
	init(0); 
	rem.copy(x); 
	vlong_value m,s; 
	m.copy(y); 
	s.init(1); 
	while ( rem.cf(m) > 0 ) 
	{ 
		m.shl(); 
		s.shl(); 
	} 
	while ( rem.cf(y) >= 0 ) 
	{ 
		while ( rem.cf(m) < 0 ) 
		{ 
			m.shr(); 
			s.shr(); 
		} 
		rem.subtract( m ); 
		add( s ); 
	} 
} 
 
// Implementation of vlong 
 
long operator !=( const vlong& x, const vlong& y ){ return x.cf( y ) != 0; } 
long operator ==( const vlong& x, const vlong& y ){ return x.cf( y ) == 0; } 
long operator >=( const vlong& x, const vlong& y ){ return x.cf( y ) >= 0; } 
long operator <=( const vlong& x, const vlong& y ){ return x.cf( y ) <= 0; } 
long operator > ( const vlong& x, const vlong& y ){ return x.cf( y ) > 0; } 
long operator < ( const vlong& x, const vlong& y ){ return x.cf( y ) < 0; } 
 
void vlong::load( DWORD * a, DWORD n ) 
{ 
	docopy(); 
	value->clear(); 
	for (DWORD i=0;iset(i,a[i]); 
} 
 
void vlong::store( DWORD * a, DWORD n ) const 
{ 
	for (DWORD i=0;iget(i); 
} 
 
void vlong::load( char * a, DWORD n )	//自己添加 
{ 
	if( (n % 2) == 1) 
	{ 
		n++; 
	}	//加多一个字节，应该还是能还原的 
	load( (DWORD *)a, n / 2); 
} 
 
void vlong::store( char * a, DWORD n ) const	//自己添加 
{ 
	store( (DWORD *)a, n / 2); 
} 
 
 
void vlong::docopy() 
{ 
	if ( value->share ) 
	{ 
		value->share -= 1; 
		vlong_value * nv = new vlong_value; 
		nv->copy(*value); 
		value = nv; 
	} 
} 
 
DWORD vlong::bits() const 
{ 
	return value->bits(); 
} 
 
DWORD vlong::bit(DWORD i) const 
{ 
	return value->bit(i); 
} 
 
void vlong::setbit(DWORD i) 
{ 
	docopy(); 
	value->setbit(i); 
} 
 
void vlong::clearbit(DWORD i) 
{ 
	docopy(); 
	value->clearbit(i); 
} 
 
long vlong::cf( const vlong & x ) const 
{ 
	long neg = negative && (!value->is_zero()); 
	if ( neg == (x.negative && !x.value->is_zero()) ) 
		return value->cf( *x.value ); 
	else if ( neg ) return -1; 
	else return +1; 
} 
 
vlong::vlong (DWORD x) 
{ 
	value = new vlong_value; 
	negative = 0; 
	value->init(x); 
} 
 
vlong::vlong ( const vlong& x ) // copy constructor 
{ 
	negative = x.negative; 
	value = x.value; 
	value->share += 1; 
} 
 
vlong& vlong::operator =(const vlong& x) 
{ 
	if ( value->share ) value->share -=1; else delete value; 
	value = x.value; 
	value->share += 1; 
	negative = x.negative; 
	return *this; 
} 
 
vlong::~vlong() 
{ 
	if ( value->share ) value->share -=1; else delete value; 
} 
 
DWORD to_unsigned ( const vlong & x ) // conversion to DWORD 
{ 
	return x.value->to_unsigned(); 
} 
 
vlong& vlong::operator ^=(const vlong& x) 
{ 
	docopy(); 
	value->xor( *x.value ); 
	return *this; 
} 
 
vlong& vlong::operator &=(const vlong& x) 
{ 
	docopy(); 
	value->and( *x.value ); 
	return *this; 
} 
 
vlong& vlong::ror(DWORD n) 
{ 
	docopy(); 
	long carry = value->shr(); 
	if (carry) 
		value->setbit(n-1); 
	return *this; 
} 
 
vlong& vlong::rol(DWORD n) 
{ 
	docopy(); 
	long carry = value->bit(n-1); 
	if (carry) value->clearbit(n-1); 
	value->shl(); 
	if (carry) value->setbit(0); 
	return *this; 
} 
 
vlong& vlong::operator >>=( DWORD n ) // divide by 2**n 
{ 
	docopy(); 
	value->shr(n); 
	return *this; 
} 
 
vlong& vlong::operator +=(const vlong& x) 
{ 
	if ( negative == x.negative ) 
	{ 
		docopy(); 
		value->add( *x.value ); 
	} 
	else if ( value->cf( *x.value ) >= 0 ) 
	{ 
		docopy(); 
		value->subtract( *x.value ); 
	} 
	else 
	{ 
		vlong tmp = *this; 
		*this = x; 
		*this += tmp; 
	} 
	return *this; 
} 
 
vlong& vlong::operator -=(const vlong& x) 
{ 
	if ( negative != x.negative ) 
	{ 
		docopy(); 
		value->add( *x.value ); 
	} 
	else if ( value->cf( *x.value ) >= 0 ) 
	{ 
		docopy(); 
		value->subtract( *x.value ); 
	} 
	else 
	{ 
		vlong tmp = *this; 
		*this = x; 
		*this -= tmp; 
		negative = 1 - negative; 
	} 
	return *this; 
} 
 
vlong operator +( const vlong& x, const vlong& y ) 
{ 
	vlong result = x; 
	result += y; 
	return result; 
} 
 
vlong operator -( const vlong& x, const vlong& y ) 
{ 
	vlong result = x; 
	result -= y; 
	return result; 
} 
 
vlong operator *( const vlong& x, const vlong& y ) 
{ 
	vlong result; 
	result.value->mul( *x.value, *y.value ); 
	result.negative = x.negative ^ y.negative; 
	return result; 
} 
 
vlong operator /( const vlong& x, const vlong& y ) 
{ 
	vlong result; 
	vlong_value rem; 
	result.value->divide( *x.value, *y.value, rem ); 
	result.negative = x.negative ^ y.negative; 
	return result; 
} 
 
vlong operator %( const vlong& x, const vlong& y ) 
{ 
	vlong result; 
	vlong_value divide; 
	divide.divide( *x.value, *y.value, *result.value ); 
	result.negative = x.negative; // not sure about this? 
	return result; 
} 
 
vlong operator ^( const vlong& x, const vlong& y ) 
{ 
	vlong result = x; 
	result ^= y; 
	return result; 
} 
 
vlong operator &( const vlong& x, const vlong& y ) 
{ 
	vlong result = x; 
	result &= y; 
	return result; 
} 
 
vlong operator <<( const vlong& x, DWORD n ) // multiply by 2**n 
{ 
	vlong result = x; 
	while (n) 
	{ 
		n -= 1; 
		result += result; 
	} 
	return result; 
} 
 
 
vlong abs( const vlong & x ) 
{ 
	vlong result = x; 
	result.negative = 0; 
	return result; 
} 
 
long product ( const vlong &X, const vlong &Y ) 
{ 
	return X.value->product( *Y.value ); 
} 
 
vlong pow2( DWORD n ) 
{ 
	vlong result; 
	result.setbit(n); 
	return result; 
} 
 
vlong gcd( const vlong &X, const vlong &Y ) 
{ 
	vlong x=X, y=Y; 
	while (1) 
	{ 
		if ( y == 0 ) return x; 
		x = x % y; 
		if ( x == 0 ) return y; 
		y = y % x; 
	} 
} 
 
vlong modinv( const vlong &a, const vlong &m ) // modular inverse 
// returns i in range 1..m-1 such that i*a = 1 mod m 
// a must be in range 1..m-1 
{ 
	vlong j=1,i=0,b=m,c=a,x,y; 
	while ( c != 0 ) 
	{ 
		x = b / c; 
		y = b - x*c; 
		b = c; 
		c = y; 
		y = j; 
		j = i - j*x; 
		i = y; 
	} 
	if ( i < 0 ) 
		i += m; 
	return i; 
} 
 
class monty // class for montgomery modular exponentiation 
{ 
	vlong m,n1; 
	vlong T,k;   // work registers 
	DWORD N;  // bits for R 
	void mul( vlong &x, const vlong &y ); 
public: 
	vlong R,R1; 
	vlong exp( const vlong &x, const vlong &e ); 
	vlong monty_exp( const vlong &x, const vlong &e ); 
	monty( const vlong &M ); 
}; 
 
monty::monty( const vlong &M ) 
{ 
	m = M; 
	N = 0; R = 1; 
	while ( R < M ) 
	{ 
		R += R; 
		N += 1; 
	} 
	R1 = modinv( R-m, m ); 
	n1 = R - modinv( m, R ); 
} 
 
void monty::mul( vlong &x, const vlong &y ) 
{ 
	// T = x*y; 
	T.value->fast_mul( *x.value, *y.value, N*2 ); 
	 
	// k = ( T * n1 ) % R; 
	k.value->fast_mul( *T.value, *n1.value, N ); 
	 
	// x = ( T + k*m ) / R; 
	x.value->fast_mul( *k.value, *m.value, N*2 ); 
	x += T; 
	x.value->shr( N ); 
	 
	if (x>=m) x -= m; 
} 
 
vlong monty::monty_exp( const vlong &x, const vlong &e ) 
{ 
	vlong result = R-m, t = x; // don't convert input 
	t.docopy(); // careful not to modify input 
	DWORD bits = e.value->bits(); 
	DWORD i = 0; 
	while (1) 
	{ 
		if ( e.value->bit(i) ) 
			mul( result, t); 
		i += 1; 
		if ( i == bits ) break; 
		mul( t, t ); 
	} 
	return result; // don't convert output 
} 
 
vlong monty::exp( const vlong &x, const vlong &e ) 
{ 
	return ( monty_exp( (x*R)%m, e ) * R1 ) % m; 
} 
 
//// 求 x的e次幂，再对m求模 
vlong modexp( const vlong & x, const vlong & e, const vlong & m ) 
{ 
	monty me(m); 
	return me.exp( x,e ); 
} 
 
vlong monty_exp( const vlong & x, const vlong & e, const vlong & m ) 
{ 
	monty me(m); 
	return me.monty_exp( x,e ); 
} 
 
vlong monty_exp( const vlong & x, const vlong & d, const vlong & m, const vlong &p, const vlong &q ) 
{ 
	monty me(m); 
	vlong x1 = ( x * me.R1 ) % m; // Transform input 
	 
	vlong u = modinv( p, q ); 
	vlong dp = d % (p-1); 
	vlong dq = d % (q-1); 
	 
	// Apply chinese remainder theorem 
	vlong a = modexp( x1 % p, dp, p ); 
	vlong b = modexp( x1 % q, dq, q ); 
	if ( b < a ) b += q; 
	vlong result = a + p * ( ((b-a)*u) % q ); 
	 
	// Transform result 
	return ( result * me.R ) % m; 
} 
 
static vlong half(const vlong &a, vlong p) 
{ 
	if (a.bit(0)) 
		return (a+p)/2; 
	return a/2; 
} 
 
vlong lucas ( vlong P, vlong Z, vlong k, vlong p ) // P^2 - 4Z != 0 
{ 
	vlong D = P*P - 4*Z, U = 1, V = P, U1,V1; 
	DWORD i=k.bits()-1; 
	while (i) 
	{ 
		i -= 1; 
		U1 = U*V; V1 = V*V + D*U*U; U = U1%p; V = half(V1%p,p); 
		if ( k.bit(i) ) 
		{ 
			U1 = P*U+V; V1 = P*V+D*U; U = half(U1%p,p); V = half(V1%p,p); 
		} 
	} 
	return V; 
} 
 
vlong sqrt( vlong g, vlong p ) 
{ 
	vlong result; 
	if (p%4==3) 
		result = modexp( g, p/4+1, p ); 
	else if (p%8==5) 
	{ 
		vlong gamma = modexp( 2*g, p/8, p); 
		vlong i = 2*g*gamma*gamma - 1; 
		result = g*gamma*i; 
	} 
	else 
	{ 
		vlong Z = g; 
		vlong P = 1; 
		while (1) 
		{ 
			vlong D = (P*P-4*g)%p; if (D<0) D += p; 
			if ( D==0 ) 
			{ 
				result = half(P,p); 
				break; 
			} 
			if ( modexp( D, (p-1)/2, p ) != 1 ) 
			{ 
				result = half( lucas( P, Z, (p+1)/2, p ), p ); 
				break; 
			} 
			P += 1; // Is this ok (efficient?) 
		} 
	} 
	result = result % p; 
	if ( result < 0 ) result += p; 
	 
	return result; 
} 
/***************"vlong.cpp"********************/ 
 
 
 
/***************"rsa.cpp"********************/ 
//#include "rsa.h" 
static vlong from_str( const char * s ) 
{ 
	vlong x = 0; 
	while (*s) 
	{ 
		x = x * 256 + (unsigned char)*s; 
		s += 1; 
	} 
	return x; 
} 
 
public_key::public_key() 
{ 
	/*在这里必须初始化requires为1，否则无法进行加解密 
	在Debug版中它初始化就不会为0，而在Release版中它初始化为0 
	这就会出现只有Release版才会出的错*/ 
	requires = true; 
} 
 
void private_key::create() 
{ 
	char prand[2][LEVEL * 4/*必须不小于LEVEL*2 */], tc; 
	DWORD i, j; 
	DWORD validate[LEVEL];	//验证m的最高位是否为0 
	prime_factory pf; 
	vlong tmp; 
 
start:	//条件不成立，重新再生成p和q 
	srand((unsigned)time(NULL)); 
	for(i = 0; i < 2; i++) 
	{ 
		for(j = 0; j < (LEVEL * 2); j++) 
		{ 
			tc = (char)(0x41+rand()%0xAF); 
			prand[i][j] = tc; 
		} 
		prand[i][j]=0; 
	} 
	// Choose primes 
 
	p = pf.find_prime( from_str(prand[0]) );//计算生成两个大奇数 p, q 
	q = pf.find_prime( from_str(prand[1]) ); 
	if ( p > q ) 
	{ 
		tmp = p; 
		p = q; 
		q = tmp; 
	} 
	 
	// Calculate public key 
	m = p * q;	//当m的最高位是非0时，要加密的大整数最高位是0，就满足加密的条件了 
	m.store(validate, LEVEL); 
	//如果这个m不能满足条件，就重新生成p和q，直到条件成立，其实这也不能完全解决问题还是要有requires 
	if(validate[LEVEL - 1] == 0x00000000) goto start; 
 
	e = 65537;	//如果这个固定的e不能满足条件，就重新生成p和q，直到条件成立 
	if( gcd(p-1,e) != 1 || gcd(q-1,e) != 1 ) goto start; 
 
	/*while ( gcd(p-1,e) != 1 || gcd(q-1,e) != 1 ) 
	{ 
		e += 2; 
	}*/ 
} 
 
 
vlong public_key::encrypt( const vlong& plain ) 
{ 
	if(plain >= m) 
	{ 
		requires = false; 
		//::MessageBox(NULL,"加密的数必须小于m","public_key::encrypt",MB_ICONSTOP); 
	} 
	if(!requires) 
	{	//只有出错一次就永远不能进行加密，只有再把requires=true 
		return m;	 
	} 
 
	return modexp( plain, e, m ); 
} 
 
vlong private_key::decrypt( const vlong& cipher ) 
{ 
	if(cipher >= m) 
	{ 
		requires = false; 
		//::MessageBox(NULL, "加密的数必须小于m", "private_key::decrypt", MB_ICONSTOP); 
	} 
	if(!requires) 
	{	//只有出错一次就永远不能进行加密，只有再把requires=true 
	//	::MessageBox(NULL,"我错了","private_key::decrypt",MB_ICONSTOP); 
 
		return m; 
	} 
 
	// Calculate values for performing decryption 
	// These could be cached, but the calculation is quite fast 
	vlong d = modinv( e, (p-1)*(q-1) ); 
	vlong u = modinv( p, q ); 
	vlong dp = d % (p-1); 
	vlong dq = d % (q-1); 
	 
	// Apply chinese remainder theorem 
	vlong a = modexp( cipher % p, dp, p ); 
	vlong b = modexp( cipher % q, dq, q ); 
	if ( b < a ) b += q; 
	return a + p * ( ((b-a)*u) % q ); 
} 
 
 
void public_key::PK_to_vlong(PK pk) 
{ 
	m.load(pk.m, LEVEL); 
	e = 65537;	//一个固定的e 
} 
 
void private_key::SK_to_vlong(SK sk) 
{ 
	p.load(sk.p, LEVEL / 2); 
	q.load(sk.q, LEVEL / 2); 
 
	m = p * q; 
	e = 65537;	//一个固定的e 
} 
 
void public_key::vlong_to_PK(PK &pk) 
{ 
	//把公开密钥转换成可用格式 
	m.store(pk.m, LEVEL);	 
} 
 
void private_key::vlong_to_SK(SK &sk) 
{ 
	//把私人密钥转换成可用格式 
	p.store(sk.p, LEVEL / 2); 
	q.store(sk.q, LEVEL / 2); 
} 
 
int public_key::get_requires() 
{ 
	return requires; 
} 
 
void public_key::set_requires(int req) 
{ 
	requires = req; 
} 
 
void public_key::encrypt(MessageDollop &dollop) 
{ 
	vlong m, c; 
	c.load( (DWORD *)&dollop, LEVEL); 
	m = encrypt(c); 
	m.store( (DWORD *)&dollop, LEVEL); 
 
} 
 
void private_key::decrypt(MessageDollop &dollop) 
{ 
	vlong m, c; 
	m.load( (DWORD *)&dollop, LEVEL/*必须是dollop的长度，否则会出错*/); 
	c = decrypt(m); 
	c.store( (DWORD *)&dollop, LEVEL); 
 
} 
 
void public_key::encrypt(MessagePackage &package) 
{	 
	MessageDollop dollop; 
	int quotient, remainder, i; 
 
	quotient = (package.n * 2) / sizeof(MessageDollop); 
	remainder = (package.n * 2) % sizeof(MessageDollop); 
	quotient = remainder?++quotient:quotient; 
 
	for(i = 0;i < quotient;i++) 
	{	//把消息包分成若干块 
		::MoveMemory( 
			&dollop,						//目标 
			package.data + i * sizeof(MessageDollop),//源内容 
			sizeof(MessageDollop)); 
 
		//用公钥加密消息快 
		encrypt(dollop);	//dollop.nil[0]必须为零，之前应该设置好了，如果已被解密就不用 
 
		//把处理的消息保存到原来的消息包中 
		::MoveMemory( 
			package.data + i * sizeof(MessageDollop),//目标 
			&dollop,						//源内容 
			sizeof(MessageDollop)); 
	} 
 
} 
 
void private_key::decrypt(MessagePackage &package) 
{ 
	MessageDollop dollop; 
	int quotient, remainder, i; 
 
	quotient = (package.n * 2) / sizeof(MessageDollop); 
	remainder = (package.n * 2) % sizeof(MessageDollop); 
	quotient = remainder?++quotient:quotient; 
 
	for(i = 0;i < quotient;i++) 
	{	//把消息包分成若干块 
		::MoveMemory( 
			&dollop,						//目标 
			package.data + i * sizeof(MessageDollop),//源内容 
			sizeof(MessageDollop)); 
 
		//用私钥解密消息快 
		decrypt(dollop);//dollop.nil[0]必须为零，之前应该设置好了，如果已被加密就不用	 
 
		//把处理的消息保存到原来的消息包中 
		::MoveMemory( 
			package.data + i * sizeof(MessageDollop),	//目标 
			&dollop,							//源内容 
			sizeof(MessageDollop)); 
	} 
 
} 
/***************"rsa.cpp"********************/ 
 
 
 
/***************"prime.cpp"********************/ 
//#include "prime.h" 
long is_probable_prime( const vlong &p ) 
{ 
	// Test based on Fermats theorem a**(p-1) = 1 mod p for prime p 
	// For 1000 bit numbers this can take quite a while 
	const rep = 4; 
	const DWORD any[rep] = { 2,3,5,7 /*,11,13,17,19,23,29,31,37..*/ }; 
	for ( DWORD i=0; i