largeint.h

rsa算法/// ////

// LargeInt.h
// 作者 pAnic 2005年9月22日。
// 大整数类的声明，包含了质数检查，随机数生成，以及RSA密钥生成及加密解密函数。
// 有问题请到
// http://blog.vckbase.com/panic 
// 留言。
//////////////////////////////////////////////////////////////////////////////


#if !defined(LARGEINT_HEADER)
#define LARGEINT_HEADER

#include <vector>

namespace panic
{
	//必须保证T_DWORD是4字节。
	typedef unsigned long T_DWORD;
	
	
	class CLargeInt  
	{
	public:
		//说明：
		//基本的操作函数之所以没有设置成运算符的重载，主要是因为，
		//大数运算的过程中，经常需要额外的参数，例如错位相加减的offset值。
		//以及某些额外的结果
		//例如，除法运算的商和余数。
		//为了代码尽量通用，都写成了静态成员函数。
		//运算符的重载可以通过对这些静态成员函数进一步封装来实现。
		
		//复制
		static void Copy(const CLargeInt& source,CLargeInt& target);
		
		//比较
		static bool LargerEqual(const CLargeInt& source,const CLargeInt& target,T_DWORD offset = 0);
		static bool Equal(const CLargeInt& source,const CLargeInt& target);
		
		//和T_DWORD类型交互的底层操作函数
		static void Mul(const CLargeInt& faciend,T_DWORD multiplier,CLargeInt& product);
		
		static void Div(const CLargeInt& dividend,T_DWORD divisor,CLargeInt& quotient,T_DWORD& residual);
		
		//移位：
		
		//右移一位，用来取代 /2 操作。
		static void RCR(CLargeInt& n);
		
		//左移一位，用来取代 *2 操作。
		static void RCL(CLargeInt& n);
		
		//CLargeInt类型底层操作函数，
		
		static void Add(const CLargeInt& augend,const CLargeInt& addend,CLargeInt& sum,T_DWORD offset = 0);
		
		static void Sub(const CLargeInt& minuend,const CLargeInt& subtrahend,CLargeInt& difference,T_DWORD offset = 0);
		
		static void Mul(const CLargeInt& faciend,const CLargeInt& multiplier,CLargeInt& product);
		
		static void Div(const CLargeInt& dividend,const CLargeInt& divisor,CLargeInt& quotient,CLargeInt& residual);
		
		static void ExpMod(const CLargeInt& source,const CLargeInt& exponent,const CLargeInt& modulo,CLargeInt& result);
		
		//高阶的测试：
		static bool RabinMillerTest(const CLargeInt& source,const CLargeInt& base);
		static bool Coprime(const CLargeInt &source,const CLargeInt &target);
		
		//RSA算法相关函数：
		static bool IsPrime(const CLargeInt &n);
		static void CreatePrime(CLargeInt &n);
		static bool RSACreate( const CLargeInt &p,const CLargeInt & q,const CLargeInt &e,CLargeInt &d,CLargeInt &n);		
		static void RSAEncode( const CLargeInt &n,const CLargeInt &d,const CLargeInt &m,CLargeInt &c);
		static void RSADecode( const CLargeInt &n,const CLargeInt &e,const CLargeInt &c,CLargeInt &m);
		
		//建立随机数。
		static void CreateRandom(CLargeInt &n,T_DWORD bitcount);
	public:
		CLargeInt(T_DWORD value = 0);
		CLargeInt(const char * str);
		CLargeInt(const CLargeInt& other);
		
		~CLargeInt();
	private:
		enum LIMIT{ LENGTH = 0x3FF,SMALLPRIMES = 5000};
		T_DWORD _len;
		mutable T_DWORD _data[LENGTH]; //之所以用 mutable 是因为需要在计算中获取指针，并且有时还需要在不改变数值的情况下修改某些数组元素。
		
		//辅助用的小质数表和相关的函数。
		static std::vector<T_DWORD> _smallPrimes;
		static void InitSmallPrimes(T_DWORD count = SMALLPRIMES);
		static bool SmallPrimeTest(const CLargeInt& n);
		
		
	public:
		
		//临时的打印函数，以16进制字符串形式在标准控制台上输出整个数字。
		void Print() const
		{
			printf("0x");
			for( int i = _len-1 ; i >= 0; i--)
			{
				char str[] = "%08X";
				str[2] = '0' + sizeof(T_DWORD) * 2;
				if( i != (_len-1) )printf(str,_data[i]);
				else printf("%X",_data[i]);
			}
			printf("\n");
		}
	};
}


#endif // LARGEINT_HEADER