1. 大數的運算原理
RSA算法依賴於大數的運算，目前主流RSA算法都建立在512位到1024位的大數運算之上，所以我們首先需要掌握大數（比如1024位）的運算原理。
大多數的編譯器只能支持到32位（或64位）的整數運算，即我們在運算中所使用的整數必須小於等於32位，即0xFFFFFFFF,這遠遠達不到RSA的需要，於是需要專門建立大數運算庫，來解決這一問題。
最簡單的辦法是將大數當作字符串進行處理，也就是將大數用10進制字符數組進行表示，然後模擬人們手工進行"豎式計算"的過程編寫其加減乘除函數。但是這樣做效率很低。當然其優點是算法符合人們的日常習慣，易於理解。
另一種思路是將大數當作一個二進制流進行處理，使用各種移位和邏輯操作來進行加減乘除運算，但是這樣做代碼設計非常復雜，可讀性很低，難以理解也難以調試。
這裡我們采用了一種介於兩者之間的思路：將大數看作一個N進制數組，對於目前的32位系統而言，N可以取2的32次方，即 0x100000000,假如將一個1024位的大數轉化成0x10000000進制，它就變成了32位，而每一位的取值范圍是0- 0xFFFFFFFF.我們正好可以用一個無符號長整數來表示這一數值。所以1024位的大數就是一個有32個元素的unsigned long數組。而且0x100000000進制的數組排列與2進制流對於計算機來說，實際上是一回事，但是我們完全可以針對unsigned long數組進行"豎式計算",而循環規模被降低到了32次之內，並且算法很容易理解。
但考慮到乘法和除法，都要進行擴展才能進行快速的計算（如果把除法變減法而不擴展，速度將慢的無法忍受）。所以我們將N取2的16次方的，即 0xFFFF.每一位用unsigned short來表示，當進行乘除運算時，將short擴展成long,這是編譯器所支持的，所以運算起來，比較快。
2. 大數的各種運算
這些運算都是常見的，同時也是常用的。要實現RSA算法，就必須先實現大數的這些運算。
1） 大數的比較。兩個無符號或有符號的大數進行大小比較。大數和一般整數進行比較。大於，等於，小於，返回值各異，以區別比較結果。
2） 大數的賦值。將一個大數的值，符號等，逐位賦給另一個大數。將一般整數的值，符號等賦給一個大數。
3） 大數的加法。兩個大數從低位到高位逐位相加，要考慮到進位的問題。或大數與一般整數的相加。
4） 大數的減法。兩個大數從低位到高位逐位相減，要考慮到借位的問題。或大數與一般整數的相減。
5） 大數的乘法。兩個大數的乘法，從一個大數的低位到高位，逐位與另一個大數相乘，然後將結果低位對齊相加，要考慮進位，類似於普通的豎式乘法。或大數與一般整數的乘法。
6） 大數的除法。兩個大數的除法，從一個大數的高位到低位，逐步與另一個大數相除，要考慮借位，類似於普通的豎式除法。或大數與一般整數的乘法。
7） 大數的取余。兩個大數的取余，類似於大數的除法，只是當除到底時，返回的是余數而已，也存在借位的問題。或大數於一般整數的取余。
8） 大數的歐氏算法。它是已知大數A、B,求滿足AX≡1 MOD B的X,是最大公約數算法的擴展，同樣用輾轉相除法。再遞歸的過程中，兩個參數都要用到，到要變化的。具體算法請參考源代碼。
9） 大數的蒙氏算法。它是已知大數A、B和C,求X=A^B MOD C的值。要對指數進行逐漸降階，直到變成2次方，也就是轉換成乘法和取余運算。降階的方法和算法的具體過程，請參考相關書籍和源代碼。
10） 大數的最大公約數。求兩個大數的最大公約數，用輾轉相除法。
RSA算法的實現
A. 生成密鑰函數
gChar gGenerateKey（gBigInt *n,gBigInt *e,gBigInt *d）；
功能：該函數實現了產生密鑰的功能。先產生兩個隨機的大素數p和q,然後計算n=p×q,隨機產生（或固定）一個大數e,計算d,使得ed≡1 MOD （p-1）（q-1）。
參數：
n:兩個大數的乘積，和e或d聯合構成加密密鑰或解密密鑰。
e:一個大數，作為加密密鑰。
d:一個和e互異的大數，作為解密密鑰。
返回值：1-成功，0-失敗。
B. 數據加密函數
char gEncRSA（unsigned char* indata, unsigned long inlen, gBigInt* e, gBigInt* n,\
unsigned char *outdata, unsigned long* outlen, int flg）；
功能：把待加密的明文數據indata,用加密密鑰e和n進行分段加密。
加密後的數據放到提前開辟好的內存outdata中，其長度outlen不得小於（（inlen+k-12）/（k-11））*k,這裡k為n的位數。
參數：
indata:指向明文數據的指針。
Inlen:傳入數據的長度，即明文數據的長度。
e和n:兩個大數，作為加密密鑰。
Outdata:存放加密後密文數據的指針。
Outlen:傳入outdata的長度，傳出數據的長度，即密文數據的長度。
Flg:公鑰加密或私鑰加密的標志，g_PUBLIC-公鑰，g_PRIVATE-私鑰。
返回值：1-成功，0-失敗。
C. 數據解密函數
char gDecRSA（unsigned char* indata, unsigned long inlen, gBigInt* d, gBigInt* n,\
unsigned char *outdata, unsigned long* outlen, int flg）；
功能：把待解密的密文數據indata,用解密密鑰e和n進行分段解密。
解密後的數據放到提前開辟好的內存outdata中，其長度outlen不得小於（inlen）*k/（k-11），
這裡k為n的位數。
參數：
indata:指向密文數據的指針。
Inlen:傳入數據的長度，即密文數據的長度。
d和n:兩個大數，作為加密密鑰。
Outdata:存放解密後明文數據的指針。
Outlen:傳入outdata的長度，傳出數據的長度，即明文數據的長度。
Flg:公鑰加密或私鑰加密的標志，g_PUBLIC-公鑰，g_PRIVATE-私鑰。
返回值：1-成功，0-失敗。
D. 用小素數檢測
gChar gIsNotPrime（gBigInt *p）；
功能：檢測隨機大數p能否被小素數整除。
參數：
p:待檢測的隨機大數。
返回值：0-可能是素數，其它-為能整除p的小素數或1.
E. Rabin-Miller檢測
gChar gRabinMillerTest（gBigInt *p,int tNum）；
功能：用Rabin-Miller算法，對大數p進行tNum次檢測，判斷p是否可能為素數。
參數：
p:待檢測的隨機大數。
tNum:檢測的次數，它可以決定該檢測的可信度。
返回值：0-失敗或通不過，1-成功並通過，說明p可能是素數。
F. 隨機產生大素數
gChar gGeneratePrime（gBigInt *p）；
功能：隨機生成一個大素數。
參數：
p:隨機生成的大素數。
返回值：0-失敗，1-成功。
G. 順序搜索大素數
gChar gGeneratePrimeEx（gBigInt *p, int flg）；
功能：根據標志flg,遞增或遞減地搜索p附近的大素數。
參數：
p:搜索到的大素數。
Flg:方向標志，g_INCREASE-遞增，g_DECREASE-遞減。
返回值：0-失敗，1-成功。
H. 字符串與大數的轉換
gChar gStr2BigInt（gBigInt *gbi,char *str,int flg）；
功能：根據標志flg,將表示成10進制或16進制形式的字符串str轉換成大數gbi.
參數：
gbi:轉換成的大數。
Str:待轉換的字符串。
Flg:標志，OCT_FLG-8進制，DEC_FLG-10進制，HEX_FLG-16進制。
返回值：0-失敗，1-成功。
gChar gBigInt2Str（char *str,gBigInt *gbi,int flg）；
功能：根據標志flg,將大數gbi轉換成10進制或16進制形式表示的字符串str.
參數：
Str:轉換成的字符串。
gbi:待轉換的大數。
Flg:標志，OCT_FLG-8進制，DEC_FLG-10進制，HEX_FLG-16進制。
返回值：0-失敗，1-成功。
I. 一般整數的乘除
gUInt gIntMul（gUInt *a, gUInt b）；
功能：一般整數的乘法。在函數內部，對整數a和b進行擴展，然後與b相乘，把結果放在a中返回，進位作為返回值。
參數：
a:傳入一個整數，傳出相乘的結果。
b:傳入一個整數，作乘數。
返回值：兩個整數相乘的進位。失敗時，返回0.
gUInt gIntDiv（gUInt *ah, gUInt *al, gUInt b）；
功能：一般整數的除法。在函數內部，將整數ah和al合並成一個擴展了的整數，然後除以整數b,把結果的高位放到ah中，低位放到al中返回，余數作為返回值。
參數：
ah:傳入一個整數，作為被除數的高位；傳出相除後的結果的高位。
al:傳入一個整數，作為被除數的低位；傳出相除後的結果的低位。
b:傳入一個整數，作除數。
返回值：相除的余數。失敗時，返回0.
J. 大數的比較
gChar gCmp（gBigInt *a, gBigInt *b）；
功能：對大數a和大數b進行比較，不考慮它們的符號，只比較數值。
參數：
a:傳入一個大數。
b:傳入另一個大數。
返回值：-1-大數a小於大數b,0-大數a等於大數b,+1-大數a大於大數b.
gChar gCmpEx（gBigInt *a, gBigInt *b）；
功能：對大數a和大數b進行比較，考慮它們的符號，整數大於負數。
參數：
a:傳入一個大數。
b:傳入另一個大數。
返回值：-1-大數a小於大數b,0-大數a等於大數b,+1-大數a大於大數b.
gChar gCmpInt（gBigInt *a, gUInt b）；
功能：大數與整數的比較。對大數a和一般整數b進行比較，不考慮它們的符號。
參數：
a:傳入一個大數。
b:傳入一個一般整數。
返回值：-1-大數a小於b,0-大數a等於b,+1-大數a大於b.
K. 大數的賦值
gChar gMov（gBigInt *a, gBigInt *b）；
功能：將大數b的值，賦給大數a,考慮它們的符號。
參數：
a:傳出賦值的結果。
b:傳入另一個大數。
返回值：0-失敗，1-成功。
gChar gMovInt（gBigInt *a, gUInt b）；
功能：將整數b的值，賦給大數a,考慮它們的符號。
參數：
a:傳出賦值的結果。
b:傳入一個一般整數。
返回值：0-失敗，1-成功。
L. 大數的加法
gChar gAdd（gBigInt *a, gBigInt *b）；//加
功能：對大數a和大數b進行加法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相加的結果。
b:傳入另一個大數。
返回值：0-失敗，1-成功。
gChar gAddInt（gBigInt *a, gSInt b）；
功能：對大數a和整數b進行加法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相加的結果。
b:傳入一個一般整數。
返回值：0-失敗，1-成功。
M. 大數的減法
gChar gSub（gBigInt *a, gBigInt *b）；//減
功能：對大數a和大數b進行減法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相減的結果。
b:傳入另一個大數。
返回值：0-失敗，1-成功。
gChar gSubInt（gBigInt *a, gSInt b）；
功能：對大數a和整數b進行減法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相減的結果。
b:傳入一個一般整數。
返回值：0-失敗，1-成功。
N. 大數的乘法
gChar gMul（gBigInt *a, gBigInt *b）；//乘
功能：對大數a和大數b進行乘法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相乘的結果。
b:傳入另一個大數。
返回值：0-失敗，1-成功。
gChar gMulInt（gBigInt *a, gSInt b）；
功能：對大數a和整數b進行乘法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相乘的結果。
b:傳入一個一般整數。
返回值：0-失敗，1-成功。
O. 大數的除法
gChar gDiv（gBigInt *a, gBigInt *b）；//除
功能：對大數a和大數b進行除法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相除的結果。
b:傳入另一個大數。
返回值：0-失敗，1-成功。
gChar gDivInt（gBigInt *a, gSInt b）；
功能：對大數a和整數b進行除法運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出相除的結果。
b:傳入一個一般整數。
返回值：0-失敗，1-成功。
P. 大數的取余
gChar gMod（gBigInt *a, gBigInt *b）；//取余
功能：對大數a和大數b進行取余運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出取余的結果。
b:傳入另一個大數。
返回值：0-失敗，1-成功。
gChar gModInt（gBigInt *a, gSInt b）；
功能：對大數a和整數b進行取余運算，考慮它們的符號。
參數：
a:傳入一個大數，傳出取余的結果。
b:傳入一個一般整數。
返回值：0-失敗，1-成功。
Q. 歐幾裡德算法
gChar gEuc（gBigInt *a,gBigInt *b）；//歐幾裡德算法
功能：對大數a和大數b執行歐幾裡德算法，結果放到a中。即用輾轉相除的思想，求滿足aX≡1 MOD b的X的值，也即求滿足aX-bY=1的較小的大數X和Y的值。
其中用到了遞歸的思想，運算後，大數a和大數b,都改變了。
參數：
a:傳入一個大數，傳出滿足aX-bY=1的X的值。
b:傳入另一個大數，傳出滿足aX-bY=1的Y的值
返回值：0-失敗，1-成功。
R. 蒙格馬利算法
gChar gMon（gBigInt *a, gBigInt *b, gBigInt *c）；//蒙格馬利算法
功能：對大數a,大數b和大數c執行蒙格馬利算法，結果放到a中。
即用指數降階的思想，求算式a^b MOD c的值。至於降階的原理，請參考相關書籍。
參數：
a:傳入一個大數，傳出運算的結果。
b:傳入另一個大數。
c:傳入第三個大數。
返回值：0-失敗，1-成功。
S. 最大公約數
gChar gGcd（gBigInt *a, gBigInt *b）；//最大公約數
功能：用輾轉相除法，求大數a和大數b的最大公約數。
參數：
a:傳入一個大數，傳出a和b的最大公約數
b:傳入另一個大數。
返回值：0-失敗，1-成功。
摘自 脈凌網絡
