rsa.cpp

一个用RSA算法实现加密通信的聊天程序。

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<rep; i+=1 )
	{
		if ( modexp( any[i], p-1, p ) != 1 )
			return 0;
	}
	return 1;
}

prime_factory::prime_factory( DWORD MP )
{
	np = 0;
	
	// Initialise pl
	char * b = new char[MP+1]; // one extra to stop search
	for (DWORD i=0;i<=MP;i+=1) b[i] = 1;
	DWORD p = 2;
	while (1)
	{
		// skip composites
		while ( b[p] == 0 ) p += 1;
		if ( p == MP ) break;
		np += 1;
		// cross off multiples
		DWORD c = p*2;
		while ( c < MP )
		{
			b[c] = 0;
			c += p;
		}
		p += 1;
	}
	pl = new DWORD[np];
	np = 0;
	for (p=2;p<MP;p+=1)
	{
		if ( b[p] )
		{
			pl[np] = p;
			np += 1;
		}
	}
	delete [] b;
}

prime_factory::~prime_factory()
{
	delete [] pl;
}

vlong prime_factory::find_prime( vlong & start )
{
	DWORD SS = 1000; // should be enough unless we are unlucky
	char * b = new char[SS]; // bitset of candidate primes
	DWORD tested = 0;
	while (1)
	{
		DWORD i;
		for (i=0;i<SS;i+=1)
			b[i] = 1;
		for (i=0;i<np;i+=1)
		{
			DWORD p = pl[i];
			DWORD r = to_unsigned(start % p); // not as fast as it should be - could do with special routine
			if (r) r = p - r;
			// cross off multiples of p
			while ( r < SS )
			{
				b[r] = 0;
				r += p;
			}
		}
		// now test candidates
		for (i=0;i<SS;i+=1)
		{
			if ( b[i] )
			{
				tested += 1;
				if ( is_probable_prime(start) )
				{
					delete [] b;
					return start;
				}
			}
			start += 1;
		}
	}
}

long prime_factory::make_prime( vlong & r, vlong &k, const vlong & min_p )
// Divide out small factors or r
{
	k = 1;
	for (DWORD i=0;i<np;i+=1)
	{
		DWORD p = pl[i];
		// maybe pre-computing product of several primes
		// and then GCD(r,p) would be faster ?
		while ( r % p == 0 )
		{
			if ( r == p )
				return 1; // can only happen if min_p is small
			r = r / p;
			k = k * p;
			if ( r < min_p )
				return 0;
		}
	}
	return is_probable_prime( r );
}
/***************"prime.cpp"********************/


/*********试验************
	private_key pv_key;
	public_key  pl_key;
	vlong m, c;

	pv_key.create(); //计算生成两个大奇数公钥和私钥：p,q,e,m

	//传递公钥，本来已经用CA分配好的了
	pl_key.char_to_vlong(pv_key.key);	

	//要加密的数字标识的数据
	DWORD a[8];	
	a[0] = 1234567890;
	a[7] = 3666667777;
	c.load(a, 8);

	m = pv_key.decrypt(c);	//先用私钥进行加密
	c = pl_key.encrypt(m);	//再用公钥进行解密
	//可以用在数字签名中
****************************/

/*******对数据进行加密*******
	private_key pv_key;
	public_key  pl_key;
	vlong m//*明文大整数*, c//*密文大整数*; 

	pv_key.create(); //计算生成两个大奇数公钥和私钥：p,q,e,m
	//传递公钥
	pl_key.char_to_vlong(pv_key.key);

	char *s = new char[VL + 3];
	char *q = new char[VL * 4];

	//加密数据
	pl_key.encrypt(s, VL + 3, q);
	pv_key.decrypt(q, VL + 3, s);
*******************************/