精品理论电影在线_日韩视频一区二区_一本色道精品久久一区二区三区_香蕉综合视频

　　C. 大數(shù)的運(yùn)算

　　1. 大數(shù)的運(yùn)算原理

　　RSA算法依賴(lài)于大數(shù)的運(yùn)算，目前主流RSA算法都建立在512位到1024位的大數(shù)運(yùn)算之上，所以我們首先需要掌握大數(shù)（比如1024位）的運(yùn)算原理。

　　大多數(shù)的編譯器只能支持到32位（或64位）的整數(shù)運(yùn)算，即我們?cè)谶\(yùn)算中所使用的整數(shù)必須小于等于32位，即0xFFFFFFFF，這遠(yuǎn)遠(yuǎn)達(dá)不到RSA的需要，于是需要專(zhuān)門(mén)建立大數(shù)運(yùn)算庫(kù)，來(lái)解決這一問(wèn)題。

　　最簡(jiǎn)單的辦法是將大數(shù)當(dāng)作字符串進(jìn)行處理，也就是將大數(shù)用10進(jìn)制字符數(shù)組進(jìn)行表示，然后模擬人們手工進(jìn)行“豎式計(jì)算”的過(guò)程編寫(xiě)其加減乘除函數(shù)。但是這樣做效率很低。當(dāng)然其優(yōu)點(diǎn)是算法符合人們的日常習(xí)慣，易于理解。

　　另一種思路是將大數(shù)當(dāng)作一個(gè)二進(jìn)制流進(jìn)行處理，使用各種移位和邏輯操作來(lái)進(jìn)行加減乘除運(yùn)算，但是這樣做代碼設(shè)計(jì)非常復(fù)雜，可讀性很低，難以理解也難以調(diào)試。

　　這里我們采用了一種介于兩者之間的思路：將大數(shù)看作一個(gè)N進(jìn)制數(shù)組，對(duì)于目前的32位系統(tǒng)而言，N可以取2的32次方，即 0x100000000，假如將一個(gè)1024位的大數(shù)轉(zhuǎn)化成0x10000000進(jìn)制，它就變成了32位，而每一位的取值范圍是0－ 0xFFFFFFFF。我們正好可以用一個(gè)無(wú)符號(hào)長(zhǎng)整數(shù)來(lái)表示這一數(shù)值。所以1024位的大數(shù)就是一個(gè)有32個(gè)元素的unsigned long數(shù)組。而且0x100000000進(jìn)制的數(shù)組排列與2進(jìn)制流對(duì)于計(jì)算機(jī)來(lái)說(shuō)，實(shí)際上是一回事，但是我們完全可以針對(duì)unsigned long數(shù)組進(jìn)行“豎式計(jì)算”，而循環(huán)規(guī)模被降低到了32次之內(nèi)，并且算法很容易理解。

　　但考慮到乘法和除法，都要進(jìn)行擴(kuò)展才能進(jìn)行快速的計(jì)算（如果把除法變減法而不擴(kuò)展，速度將慢的無(wú)法忍受）。所以我們將N取2的16次方的，即 0xFFFF。每一位用unsigned short來(lái)表示，當(dāng)進(jìn)行乘除運(yùn)算時(shí)，將short擴(kuò)展成long，這是編譯器所支持的，所以運(yùn)算起

　　9) 大數(shù)的蒙氏算法。它是已知大數(shù)A、B和C，求X=A^B MOD C的值。要對(duì)指數(shù)進(jìn)行逐漸降階，直到變成2次方，也就是轉(zhuǎn)換成乘法和取余運(yùn)算。降階的方法和算法的具體過(guò)程，請(qǐng)參考相關(guān)書(shū)籍和源代碼。

　　10) 大數(shù)的最大公約數(shù)。求兩個(gè)大數(shù)的最大公約數(shù)，用輾轉(zhuǎn)相除法。

　　RSA算法的實(shí)現(xiàn)

　　A. 生成密鑰函數(shù)

　　gChar gGenerateKey(gBigInt *n,gBigInt *e,gBigInt *d);

　　功能：該函數(shù)實(shí)現(xiàn)了產(chǎn)生密鑰的功能。先產(chǎn)生兩個(gè)隨機(jī)的大素?cái)?shù)p和q，然后計(jì)算n＝p×q，隨機(jī)產(chǎn)生（或固定）一個(gè)大數(shù)e，計(jì)算d，使得ed≡1 MOD (p-1)(q-1)。

　　參數(shù)：

　　n：兩個(gè)大數(shù)的乘積，和e或d聯(lián)合構(gòu)成加密密鑰或解密密鑰。

　　e：一個(gè)大數(shù)，作為加密密鑰。

　　d：一個(gè)和e互異的大數(shù)，作為解密密鑰。

　　返回值：1－成功，0－失敗。

　　B. 數(shù)據(jù)加密函數(shù)

　　char gEncRSA(unsigned char* indata, unsigned long inlen, gBigInt* e, gBigInt* n,\

　　unsigned char *outdata, unsigned long* outlen, int flg);

　　功能：把待加密的明文數(shù)據(jù)indata，用加密密鑰e和n進(jìn)行分段加密。

　　加密后的數(shù)據(jù)放到提前開(kāi)辟好的內(nèi)存outdata中，其長(zhǎng)度outlen不得小于((inlen+k-12)/(k-11))*k，這里k為n的位數(shù)。

　　參數(shù)：

　　indata：指向明文數(shù)據(jù)的指針。

　　Inlen：傳入數(shù)據(jù)的長(zhǎng)度，即明文數(shù)據(jù)的長(zhǎng)度。

　　e和n：兩個(gè)大數(shù)，作為加密密鑰。

　　Outdata：存放加密后密文數(shù)據(jù)的指針。

　　Outlen：傳入outdata的長(zhǎng)度，傳出數(shù)據(jù)的長(zhǎng)度，即密文數(shù)據(jù)的長(zhǎng)度。

　　Flg：公鑰加密或私鑰加密的標(biāo)志，g_PUBLIC－公鑰，g_PRIVATE－私鑰。

　　返回值：1－成功，0－失敗。

　　C. 數(shù)據(jù)解密函數(shù)

　　char gDecRSA(unsigned char* indata, unsigned long inlen, gBigInt* d, gBigInt* n,\

　　unsigned char *outdata, unsigned long* outlen, int flg);

　　功能：把待解密的密文數(shù)據(jù)indata，用解密密鑰e和n進(jìn)行分段解密。

　　解密后的數(shù)據(jù)放到提前開(kāi)辟好的內(nèi)存outdata中，其長(zhǎng)度outlen不得小于(inlen)*k/(k-11)，

　　這里k為n的位數(shù)。

　　參數(shù)：

　　indata：指向密文數(shù)據(jù)的指針。

　　Inlen：傳入數(shù)據(jù)的長(zhǎng)度，即密文數(shù)據(jù)的長(zhǎng)度。

　　d和n：兩個(gè)大數(shù)，作為加密密鑰。

　　Outdata：存放解密后明文數(shù)據(jù)的指針。

　　Outlen：傳入outdata的長(zhǎng)度，傳出數(shù)據(jù)的長(zhǎng)度，即明文數(shù)據(jù)的長(zhǎng)度。

　　Flg：公鑰加密或私鑰加密的標(biāo)志，g_PUBLIC－公鑰，g_PRIVATE－私鑰。

　　返回值：1－成功，0－失敗。

　　D. 用小素?cái)?shù)檢測(cè)