/*
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://作者：afanty@vip.sina.com
//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++里可以帶來很大的方便。
*/