C語言:rsa算法原理
發布時間：2011-08-29 共3頁
C. 大數的運算
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，這是編譯器所支持的，所以運算起
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. 用小素數檢測
