二級c語言
. 大數(shù)的運算
1. 大數(shù)的運算原理
RSA算法依賴于大數(shù)的運算，目前主流RSA算法都建立在512位到1024位的大數(shù)運算之上，所以我們首先需要掌握大數(shù)(比如1024位)的運算原理。
大多數(shù)的編譯器只能支持到32位(或64位)的整數(shù)運算，即我們在運算中所使用的整數(shù)必須小于等于32位，即0xFFFFFFFF，這遠(yuǎn)遠(yuǎn)達不到RSA的需要，于是需要專門建立大數(shù)運算庫，來解決這一問題。
最簡單的辦法是將大數(shù)當(dāng)作字符串進行處理，也就是將大數(shù)用10進制字符數(shù)組進行表示，然后模擬人們手工進行“豎式計算”的過程編寫其加減乘除函數(shù)。但是這樣做效率很低。當(dāng)然其優(yōu)點是算法符合人們的日常習(xí)慣，易于理解。
另一種思路是將大數(shù)當(dāng)作一個二進制流進行處理，使用各種移位和邏輯操作來進行加減乘除運算，但是這樣做代碼設(shè)計非常復(fù)雜，可讀性很低，難以理解也難以調(diào)試。
這里我們采用了一種介于兩者之間的思路：將大數(shù)看作一個N進制數(shù)組，對于目前的32位系統(tǒng)而言，N可以取2的32次方，即 0x100000000，假如將一個1024位的大數(shù)轉(zhuǎn)化成0x10000000進制，它就變成了32位，而每一位的取值范圍是0- 0xFFFFFFFF。我們正好可以用一個無符號長整數(shù)來表示這一數(shù)值。所以1024位的.大數(shù)就是一個有32個元素的unsigned long數(shù)組。而且0x100000000進制的數(shù)組排列與2進制流對于計算機來說，實際上是一回事，但是我們完全可以針對unsigned long數(shù)組進行“豎式計算”，而循環(huán)規(guī)模被降低到了32次之內(nèi)，并且算法很容易理解。
但考慮到乘法和除法，都要進行擴展才能進行快速的計算(如果把除法變減法而不擴展，速度將慢的無法忍受)。所以我們將N取2的16次方的，即 0xFFFF。每一位用unsigned short來表示，當(dāng)進行乘除運算時，將short擴展成long，這是編譯器所支持的，所以運算起來，比較快。
2. 大數(shù)的各種運算
這些運算都是常見的，同時也是常用的。要實現(xiàn)RSA算法，就必須先實現(xiàn)大數(shù)的這些運算。
1) 大數(shù)的比較。兩個無符號或有符號的大數(shù)進行大小比較。大數(shù)和一般整數(shù)進行比較。大于，等于，小于，返回值各異，以區(qū)別比較結(jié)果。
2) 大數(shù)的賦值。將一個大數(shù)的值，符號等，逐位賦給另一個大數(shù)。將一般整數(shù)的值，符號等賦給一個大數(shù)。
3) 大數(shù)的加法。兩個大數(shù)從低位到高位逐位相加，要考慮到進位的問題。或大數(shù)與一般整數(shù)的相加。
4) 大數(shù)的減法。兩個大數(shù)從低位到高位逐位相減，要考慮到借位的問題。或大數(shù)與一般整數(shù)的相減。
5) 大數(shù)的乘法。兩個大數(shù)的乘法，從一個大數(shù)的低位到高位，逐位與另一個大數(shù)相乘，然后將結(jié)果低位對齊相加，要考慮進位，類似于普通的豎式乘法�；虼髷�(shù)與一般整數(shù)的乘法。
6) 大數(shù)的除法。兩個大數(shù)的除法，從一個大數(shù)的高位到低位，逐步與另一個大數(shù)相除，要考慮借位，類似于普通的豎式除法�；虼髷�(shù)與一般整數(shù)的乘法。
7) 大數(shù)的取余。兩個大數(shù)的取余，類似于大數(shù)的除法，只是當(dāng)除到底時，返回的是余數(shù)而已，也存在借位的問題。或大數(shù)于一般整數(shù)的取余。
8) 大數(shù)的歐氏算法。它是已知大數(shù)A、B，求滿足AX≡1 MOD B的X，是最大公約數(shù)算法的擴展，同樣用輾轉(zhuǎn)相除法。再遞歸的過程中，兩個參數(shù)都要用到，到要變化的。具體算法請參考源代碼。
9) 大數(shù)的蒙氏算法。它是已知大數(shù)A、B和C，求X=A^B MOD C的值。要對指數(shù)進行逐漸降階，直到變成2次方，也就是轉(zhuǎn)換成乘法和取余運算。降階的方法和算法的具體過程，請參考相關(guān)書籍和源代碼。
10) 大數(shù)的最大公約數(shù)。求兩個大數(shù)的最大公約數(shù)，用輾轉(zhuǎn)相除法。
RSA算法的實現(xiàn)
A. 生成密鑰函數(shù)
gChar gGenerateKey(gBigInt *n,gBigInt *e,gBigInt *d);
功能：該函數(shù)實現(xiàn)了產(chǎn)生密鑰的功能。先產(chǎn)生兩個隨機的大素數(shù)p和q，然后計算n=p×q，隨機產(chǎn)生(或固定)一個大數(shù)e，計算d，使得ed≡1 MOD (p-1)(q-1)。
參數(shù)：
n：兩個大數(shù)的乘積，和e或d聯(lián)合構(gòu)成加密密鑰或解密密鑰。
【二級c語言】相關(guān)文章：
二級c語言上機07-09
二級c語言筆試11-23
計算機二級C++C++語言概述11-11
計算機二級c語言11-23
二級c語言筆試真題11-23
二級c語言考試應(yīng)對技巧09-07
2015二級c語言上機題庫09-11
C語言的二級指針是什么10-05
二級C語言考試復(fù)習(xí)五要點11-12