二級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，這是編譯器所支持的，所以運算起來，比較快。

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聯合構成加密密鑰或解密密鑰。

【二級c語言】相關文章：

二級c語言上機07-09

二級c語言筆試11-23

計算機二級C++C++語言概述11-11

計算機二級c語言11-23

二級c語言筆試真題11-23

二級c語言考試應對技巧09-07

2015二級c語言上機題庫09-11

C語言的二級指針是什么10-05

二級C語言考試復習五要點11-12