bigint.h

RSA对称、非对称加密解密算法

/*
RSA与大数运算

==========================================================================
前言：此文来自于www.pediy.com一位Cracker---afanty之手。他建立了一个VC++（MFC）版的大数运算库。用Delphi的朋友们请到http://ace.ulyssis.student.kuleuven.ac.be/~triade/去下载Pascal的GInt大数运算库。当然，所有基于大素数分解难题的公开密匙算法都可以使用这两个库。不过请你小心里面可能存在的Bug... :)

                                                             --- Crossbow
==========================================================================

基于以下原因，俺估计RSA算法会被越来越多的共享软件采用：

1、原理简洁易懂
2、加密强度高
3、专利限制已过期
4、看雪老大三番五次呼吁共享软件采用成熟的非对称加密技术

所以，大家应该对RSA算法进行深入了解。

俺写了一个简单易懂的大数运算库，并使用该库作了一个RSA Demo，大家可以使用这一
Demo生成真正随机的、各种长度的RSA 密钥对。其中生成1024位的RSA 密钥耗时不超过
五分钟，而对1024位以内的密文进行解密则不超过三秒钟，应该是可以接受的。

有一点需要说明的是，假如类似于这个Demo的RSA工具被共享软件作者广泛用于注册码
的生成与验证，俺认为Cracker们的日子就会过得很无趣了，唉！

RSA 依赖大数运算，目前主流RSA 算法都建立在512 位到1024位的大数运算之上，所以
我们在现阶段首先需要掌握1024位的大数运算原理。

大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等
于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不到RSA
的需要，于是需要专门建立大数运算库来解决这一问题。

最简单的办法是将大数当作字符串进行处理，也就是将大数用10进制字符数组进行表示，
然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低，
因为1024位的大数其10进制数字个数就有数百个，对于任何一种运算，都需要在两个有
数百个元素的数组空间上做多重循环，还需要许多额外的空间存放计算的进位退位标志
及中间结果。当然其优点是算法符合人们的日常习惯，易于理解。

另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减
乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试。
于是俺琢磨了一种介于两者之间的思路：

将大数看作一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即0x100
00000，假如将一个1024位的大数转化成0x10000000 进制，它就变成了32位，而每一位
的取值范围就不是0-1或0-9，而是0-0xffffffff。我们正好可以用一个无符号长整数来
表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x1
00000000进制的数组排列与2 进制流对于计算机来说，实际上是一回事，但是我们完全
可以针对unsigned long 数组进行“竖式计算”，而循环规模被降低到了32次之内，并
且算法很容易理解。

例如大数18446744073709551615，等于“ffffffff ffffffff”，它就相当于10 
进制的“99”：有两位，每位都是ffffffff。而大数18446744073709551616，等于“00000001
00000000 00000000”，它就相当于10进制的“100”：有三位，第一位是1 ，其它两位
是0。如果我们要计算18446744073709551616-18446744073709551615，就类似于100-99：

 00000001 00000000 00000000
-           ffffffff ffffffff
-----------------------------
=        0         0        1
当然，因为在VC里面存在一个__int64类型可以用来计算进位与借位值，所以将大数当作
0x100000000进制进行运算是可能的，而在其他编译系统中如果不存在64位整形，则可以
采用0x40000000进制，由于在0x40000000进制中，对任何两个“数字”进行四则运算，
结果都在0x3fffffff*03fffffff之间，小于0xffffffff，都可以用一个32位无符号整数
来表示。

/****************************************************************/
//file://大数运算库头文件：BigInt.h
//file://作者：[e-mail]
//file://版本：1.0 (2003.4.26)
//file://说明：适用于MFC
//file://由于原来作者的程序有诸多漏洞,考虑效率和正确性上的问题
//file://要对整个程序进行改造
/****************************************************************/
#include<string>
#include<iostream>
using namespace std;

#define BI_MAXLEN 100//能够表示的最大的位数由这个决定
#define DEC 10
#define HEX 16
#define My_int64 unsigned __int64

class CBigInt
{
public:
   int m_nSign;    //file://记录大数的符号，支持负值运算
   int m_nLength;  //file://记录0x10000000进制的位数，0-40之间，相当于2进制的0-1280位

   My_int64 base;//file://确定基，考虑不同的进制有着不同问题，为了最终统一

   unsigned long m_ulvalue[BI_MAXLEN];   //file://记录每一位的“数字”

//file://默认的基为0x100000000
   CBigInt();
//file://初始化大数为0,自定义基
   CBigInt(My_int64 mybase);
   ~CBigInt();

//file://将大数清0；
   void Clear0();

//file://将大数赋值为另一个大数    
   CBigInt& Mov(CBigInt& A);

//file://将大数赋值为编译器能够理解的任何整形常数或变量  
   //CBigInt& Mov(My_int64 A); 
   CBigInt& Mov(unsigned int A);

//file://比较两个大数大小 
   int Cmp(CBigInt& A);
   int Cmp(unsigned long A);

//file://计算两个大数的和 
   CBigInt Add(CBigInt& A);

//file://重载函数以支持大数与普通整数相加
   CBigInt Add(long A);

//file://计算两个大数的差
   CBigInt Sub(CBigInt& A);

//file://重载函数以支持大数与普通整数相减
   CBigInt Sub(long A);

//file://计算两个大数的积
   CBigInt Mul(CBigInt& A);

//file://重载函数以支持大数与普通整数相乘
   CBigInt Mul(long A);

//file://计算两个大数的商
   CBigInt Div(CBigInt& A);

//file://重载函数以支持大数与普通整数相除
   CBigInt Div(long A,long& mod);
    CBigInt Div(long A);

//file://计算两个大数相除的余数
   CBigInt Mod(CBigInt& A);

//file://重载函数以支持大数与普通整数相除求模
   long Mod(long A); 

//file://将输入的10进制或16进制字符串转换成大数
   int InPutFromStr(string& str, const unsigned int system);

//file://将大数按10进制或16进制格式输出到字符串
   int OutPutToStr(string& str, const unsigned int system);

//file://欧几里德算法求：Y=X.Euc(A)，使满足：YX mod A = 1
   CBigInt Euc(CBigInt& A);
   CBigInt Euc(CBigInt& A,CBigInt& result);

//file://蒙哥马利算法求：Y=X.Mon(A,B)，使满足：X^A mod B = Y
   CBigInt Mon(CBigInt& A, CBigInt& B);
   //小指数的模乘方
   CBigInt Mon(unsigned int A,CBigInt& B);
//file://判断大数是奇数还是偶数
   int Is_Even();

   //最大公约数
   CBigInt Gcd(CBigInt A);

   //产生随机数
   void Rand(unsigned long bigint_len);
   
   //64位随机数初始化
   CBigInt Seed(CBigInt seed_l);

   //64位随机数生成
   CBigInt Rand64(void);

//file://错误处理
//   void PrintErr(int Errnum);
//   void PrintErr(string& str);
};

/*
注意以上函数的声明格式，完全遵循普通整数运算的习惯，例如大数
Y=X+Z 相当于 Y.Mov(X.(Add(Z))，这样似乎没有Mov(Y,Add(X,Z))
看起来舒服，但是一旦我们重载运算符“=”为“Mov”，“+”为“Add”，
则Y.Mov(X.(Add(Z))的形式就等价于 Y=X+Z。

俺不知道其他编程语言里是否支持运算浮重载，至少这样定义函数格式
在C++里可以带来很大的方便。
*/