【文章內容簡介】 RSA 密碼體制 公鑰密碼體制的一個想法就是：也許能找到一個密碼體制，使得由給定的ek 來求 dk 是計算上不可行的。如果這樣的話，加密規(guī)則 ek 是一個公鑰，可以在一個目錄中公布（這也就是公鑰體制名稱的由來）。 (7) RSA 公鑰密碼體制的具體描述如下。 (4) 中山大學本科生畢業(yè)論文 7 （ 1）密鑰生成 選擇兩個隨機大素數(shù) p 和 q，并計算 n pq? 和 ( ) ( 1)( 1)n p q? ? ? ?。 選擇一個隨機數(shù) e ， 1 ( )en??? ，滿足 gcd( , ( )) 1en? ? ，并計算 1 m od( ( ))d e n??? 。 公鑰為 (, )en ，私鑰為 d 。 （ 2）加密 對明文 mn? ，其對應密文為 moded m n? 。 （ 3）解密 對密文 c ，其對應明文為 moddm c n? 。 （ 4）證明 由于 1mod( ( ))de n?? ，故存在整數(shù) k 滿足 ( ) 1de k n???。 故有 ( ) 1 1 ( 1 )( ) m ode d k n p k qm m m m m q? ? ? ?? ? ?。 而此式在 gcd( , )m p p? 時顯然也成立。同樣可以推出 ( ) 1 m oded k nm m m q? ??? 故有 中山大學本科生畢業(yè)論文 8 ( ) 1 m o dd ed k nc m m m n? ?? ? ? 二、實驗部分 （一） 實驗 目的 通過對 RSA 的研究和實現(xiàn)，學習 RSA 的數(shù)學基礎、掌握 RSA 加密的原理和方法、鞏固計算機編程能力。 （二）實驗環(huán)境 Microsoft Windows 7 Microsoft Visual Studio 2020 Microsoft .Net Framework 使用 C 編程語言 （三）實驗步驟 在引論中寫了要實現(xiàn) RSA，必須先解決 大整數(shù)類的實現(xiàn) 、模冪運算 的快速計算 以及 快速產生大素數(shù) 這三個問題。此外，計算 1 m od( ( ))d e n??? 需要用到 擴展的歐幾里德算法 （ Extended Euclid）。 1. 大整數(shù)類 大整數(shù)一般指數(shù)位超過計算機整數(shù)類型值集范圍的整數(shù)。如 C 中的 Unsigned long 型整數(shù)能處理整數(shù)值 4294967295（ 2321），占據(jù) 32bits 存儲空間，此時，大整數(shù)就是指大于 4294967295 的十位以上的整數(shù)。若取 109為“基”，即以 109為一個存儲單元。 109=（ 1000） 3102410=230，占 30 位，以 4Bytes 的整型長度存儲的話，空間利用率可達 %。 (8)同時，同時有表達直觀、容易理解、錄入輸出方便和數(shù)據(jù)處理能力較高的優(yōu)點。 中山大學本科生畢業(yè)論文 9 然而，為了模冪運算的效率，最終決定以 2 為基，用 bool 型數(shù)組而不是 int型，并重載加、減、乘、除、求余、相等、不等、大于、小于等運算符。 2. 快速 模冪運算 計算模冪運算 modbac?？焖倌邕\算又稱快速冪取模，其原理是 m o d ( m o d ) ( m o d ) m o da b c a c b c c? 。 故，令 k 為整數(shù)，若 2bk? ， 2m od m od ( m od ) ( m od ) m odb k k ka c a c a c a c c??； 若 21bk??， 2 1 2m o d m o d ( m o d ) ( m o d ) m o db k ka c a c a c a c c???。 因此可以分解計算，有快速算法： int exp_mod(int a, int b, int n) { int r = 1。 while (b) { if (b amp。 1) r = (r * a) % n。 a = (a * a) % n。 b = 1。 } return r。 } 3. 快速產生隨機素數(shù) 如引論所說，沒有方法直接產生一個素數(shù)，通常的做法是產生一個隨機奇數(shù)，判斷是 否為素數(shù)，產生一個隨機數(shù)恰好是素數(shù)的概率是。于是分為兩部分，一是隨機數(shù)產生，二是素性判斷。 由計算機函數(shù)產生的隨機數(shù)稱偽隨機數(shù)，有許多文章對偽隨機數(shù)的構造原理、實現(xiàn)方法和效果（生產效率和隨機性）進行了分析和研究，但由于 中有偽隨機數(shù)生成器 random()，所以不再重寫而是直接閱讀 MSDN (9)使用之。 素數(shù)測試算法主要分兩種：概率素數(shù)測試算法和真素數(shù)測試算法。 概率素數(shù)測試算法的特點是：算法速度較快、原理簡單、易于編程實現(xiàn)、有一定的誤判概率。真素數(shù)測試算法速度很慢，比如最基礎的從 3 開始測試每一個中山大學本科生畢業(yè)論文 10 整數(shù)是否被待測試數(shù) n 整除直到 n 。目前最好的基于橢圓曲線的算法的時間復雜度是 6logn ?? ，基于割圓環(huán)的測試算法的時間復雜度是 loglogloglog n 。且真素數(shù)測試算法背后的理論比較艱深，在計算機中的實現(xiàn)十分復雜，實現(xiàn)復雜帶來的不正確實現(xiàn)的安全隱患要比概率算法誤判帶來的安全隱患大得多。概率算法的誤判完全可以被控制在一個極低的可接受的概率范圍內，誤判概率在 80(1/2) 以下足以滿足絕大部分的安全需求。綜合上述原因，在實際應用中，大多使用基于概率的素數(shù)測試算法。 通過對比，選擇 MillerRabin 算法作為素數(shù)測試算法。 MillerRabin 算法是Fermat 算法的一個變形改進，它的理論基礎是從 Fermat 定理引申而 來的。 Fermat 定理： n 是一個奇素數(shù)， a 是任何整數(shù) (1 1)an? ? ? ，則 1 1(mod )nan? ? 。 事實： n 是一個奇素數(shù)，則方程 2 1modxn? 只有 1? 兩個解。 MillerRabin 算法的理論基礎：如果 n 是一個奇素數(shù)，將 1n? 表示為 2*s r 的形式（ r 是奇數(shù)）， a 是和 n 互素的任何整數(shù)，那么 1(mod )ran? 或者對某個j (0 1, )j s j Z? ? ? ?，等式 2 1(mod )jran?? 成立。 這個理論由 Fermat 定理以及一個事實推導而來。 MillerRabin 算法的誤判概率為 (1/4)t ，時間復雜度為 32(log ( ))On，其中 t 為測試次數(shù)。 (10) 4. 擴展的歐幾里德算法 歐幾里德算法是輾轉相除法，用于計算兩整數(shù)的公約數(shù)，其依賴原理如下： g c d ( , ) g c d ( , m o d )a b b a b? （ ab? 且 modab不為 0） 擴展歐幾里德定理：對于不完全為 0 的非負整數(shù) a ， b ，以及其最大公約數(shù)gcd( , )ab ，必存在整數(shù)對 x ， y ，使得 gcd( , )a b ax by??。 其實現(xiàn)方法是在進行輾轉相除法時，因為 中山大學本科生畢業(yè)論文 11 g c d ( , )g c d ( , m o d ) 39。 ( m o d ) 39。a b a x b yb a b b x a b y?? ?? 恒等變換得 39。39。 ( / ) 39。xyy x a b y??? （其中 /ab是取商） 故能設計出一個遞歸函數(shù)，求出 x， y，滿足 gcd( , )a b ax by??。 （四）代碼設計 1. 大整數(shù)類 在前文中已經說明了我的大整數(shù)類的數(shù)據(jù)結構定為布爾型數(shù)組。實際上，在開始寫這個類的時候，我用的是 int 數(shù)組與 bool 數(shù)組并存或者可以隨時切換的形式。這樣的類可以靈活處理數(shù)據(jù)，比如錄入一個十進制數(shù)，和另外一個十進制數(shù)相加再輸出時，可以直接調用兩個十進制數(shù)相加的函數(shù)，并直接輸出，節(jié)約了三次進制轉換。然而，這樣的類變得很復雜和臃腫，且在這個程序里不會有這樣的要求，故最后把十進制模式移出并構建新類。類的數(shù)據(jù)結構與字段如下： 圖 十進制整數(shù)類 圖 二進制整數(shù)類 字段 ，類名 Bigint 類中，用數(shù)組儲存大整數(shù)的絕對值，符號放在 sign 中，并用 length 表示長度。這里的 length 不是數(shù)組的長度，而是數(shù)組的有用長度；用 length 表示長度可中山大學本科生畢業(yè)論文 12 以在比較大小，四則運算時節(jié)約計算。大整數(shù)絕對值在 bool 數(shù)組中的儲存方式是，把大整數(shù)二進制化，低位放在數(shù)組低位，高位在數(shù)組高位。如把 2 放入，則把 2 二進制化為 102，則 _body[0]=0,_body[1]=1。并賦值 length 為 2。 接著進行運算符重載。 圖 大整數(shù)類運算符重載 其中包括一個從 int 型到 Bigint 型的隱式轉換函數(shù)，可以在進行 Bigint 型與int 型值進行運算時節(jié)約代碼。公開的函數(shù)中，對 5 種二元計算， 6 種比較運算以及 1 種一元計算進行了重載，并完成了哈希函數(shù)和相等函數(shù)的重寫。下面的私有函數(shù)用以輔助上面的函數(shù)實現(xiàn)，如 BinaryCheckZero 用于確定 body 的有效數(shù)位；BinaryDividestep 用于做除法運算中的一步，即被除數(shù)頂位減除數(shù)。 下面是進制轉換與輸入輸出。 圖 進制轉換 中山大學本科生畢業(yè)論文 13 十進制到二進制的轉換是通過一般的“除 2 取余，逆序排列” (11)方式，但二進制轉十進制卻不是用通常的“按權相加”法，而是“乘 2 加 1”的方法。