【導讀】揮著越來越重要的作用，其中密碼學已成為信息安全技術的核心。本文研究課題是基于。用JAVA語言開發(fā)，實現(xiàn)可以對文件進行RSA加密操作的窗體應用程序。對任意文件進行RSA加密并可解密的完整應用程序。

　　

【正文】 了 54％的奇數(shù)，用小于 100的所有素數(shù)篩值，去掉了 76％的奇數(shù)，用小于 256的所有素數(shù)篩值則去掉了 80％的奇數(shù)，??。事實上，用小于 n的所有素數(shù)篩值后，剩下的奇數(shù)占所有奇數(shù)的比例為 。 n越大， ，去掉的合數(shù)就越多，剩下的奇數(shù)為素數(shù)的概率就越大；當然，n選得越大，進入 MillerRabin正式測試之前的預計算量就越大。 針對 RSA算法，素數(shù)的 p和 q的選取應該使得 n=p q的分解不可行。對 p和 q的主要限制是，首先，為避免橢圓曲線因子分解算法， p和 q應有大致相同的比特長度?？紤]上述情況，本設計采取的方案如下： 確定大素數(shù) p和 q的長度：本設計采用 1024位的模值，因此 p和 q的位數(shù)大約為 512位，考慮到 p和 q不能太接近，也不能取太小的值，我們?nèi)∷財?shù) p的比特長為 500～ 510之間的值，然后再定素數(shù)的長 (為模 n的長度減去素數(shù) P的長度 )。 確定搜索空間：得到了大素數(shù) p及 q的長度，我們就可以在該長度范圍內(nèi)隨機搜索大素數(shù) p和 q，由素數(shù)定理知，在比特長為 512的自然數(shù)中，大約每 178個連續(xù)的奇自然數(shù)就有一個素數(shù)。因而，對我們選取的自然數(shù)區(qū)域 [N， N+t]， t=k*178， N是隨機數(shù)，其長為所求素數(shù)的長度，即比特長在 512左右，該區(qū)域基本上會含有素數(shù)。為保險起見，可增河南理工大學畢業(yè)設計（論文）說明書 21 大自然數(shù)區(qū)域的長度，即增加 t的值，這里取 k=3。 篩值：先用值小于 r的小素數(shù)，對自然數(shù)區(qū)域 [N， N+t]進行篩值，篩去是這些小素數(shù)的倍數(shù)的合數(shù)?？紤]到篩值算 法的計算量隨 r的加大增加得并不太多，我們?nèi)?r為 1023。 MillerRabin檢測：這是目前最實用、效率最高、計算量最小的算法。該算法中，需要選取和待測自然數(shù) n互素的隨機數(shù) a， n屬于 [N， N+t]， an。為節(jié)省計算量，我們?nèi)為篩值算法中使用的小素數(shù)，它們顯然滿足要求。下圖是素數(shù)的產(chǎn)生流程： 圖 大素數(shù)產(chǎn)生的流程 綜合以上方案考慮，本設計采用的方法是先用隨機數(shù)發(fā)生電路產(chǎn)生 n bit的串，然后通過小素數(shù)在設定的搜索空間篩值，最后在通過 MillerRabin素數(shù)檢測來判斷是否為素數(shù)，產(chǎn)生大素數(shù)的流程如圖 。 大素數(shù)產(chǎn)生主要涉及三個函數(shù) :(1) 隨機數(shù)產(chǎn)生 ； (2) 篩值； (3) MillerRabin素數(shù)檢測。 模逆運算 在 RSA算法中，由加密指數(shù) e和歐拉函數(shù)Φ (N)求 d，就是求模逆元，即 d是 e模 ()N? 的設定素數(shù) p 和 q 的長度 產(chǎn)生 n比特長的隨機數(shù) 在剩余偽素數(shù)中使用MillerRabin 素數(shù)檢測 用小于 2020 的小素數(shù)在此區(qū)間進行篩值，得到偽素數(shù) 設定搜索區(qū)間 [N,N+t] 得到大素數(shù) p 和 q 河南理工大學畢業(yè)設計（論文）說明書 22 逆元。乘法逆元的定義：若 1(mod )ab n? ，則稱 b為 a在模 n的乘法逆元， b可表示為 1a? 。 關于模逆元，有如下結(jié)論：一般而言，如果 a和 n互素，那么 1a? =xmodn有唯一解，如果 a和 n 不互素 ，那 么 1a? =xmodn無解。 在 RSA 算法 中， 即是要 求滿 足： e d=1(mod(p1)(q1))。我們在選擇加密指數(shù) e時，首先確保其與 ()N? 互素，所以，解密指數(shù) d是必然存在的，且唯一存在。同時，有 d與 ()N? 也互素。根據(jù)模逆元的性質(zhì)，有加密指數(shù) e也是解密指數(shù) d的模逆元，因此，先由 e加密，然后用 d解密，或者先由 d加密，然后用 e解密，都成立，所謂加密指數(shù)、解密指數(shù)只是相對概念。該性質(zhì)也使 RSA既可以用于加解密 (由 e加密，然后用 d解密 )，也可以用于簽名驗證 (由 d加密，然后用 e解密 )。 故而，在進行 RSA消息處理時，可以將加解密與簽名驗證歸納為同一模型。 在本設計中，加密指數(shù) e和歐拉函數(shù) 的互素性前一節(jié)已經(jīng)得到保證了，因此，能保證 d的存在。即一定存在一個 d滿足 e d=1(mod(p1)(q1))。 Euclid算法的流程圖如下： 圖 歐幾里德算法流程 利用 Euclid(歐幾里德 )算法 (輾轉(zhuǎn)相除法 )求乘法逆元： 己知 a及 n且 (a,n)=1，求 1 1(mod )aa n? ? 。 歐幾里德算法是古希臘數(shù)學家歐幾里德給出的求兩個自然數(shù)的最大公約數(shù)的方法，如果 (a， n)=1，則 b一定存在。首先介紹利用歐幾里德算法求 gcd(a， n)的方法，再介紹求乘法逆元的方法。 令 nr =n， 1r =a， an? ，利用輾轉(zhuǎn)相除 法可得 Y r=m%n 開始 輸入 m和 n m=n n=r r=0 輸出 n 結(jié)束 N 河南理工大學畢業(yè)設計（論文）說明書 23 0 1 1 2r r g r?? 210 rr?? 1 2 2 3r r g r?? 320 rr?? . . . 2 1 1j j j jr r g r? ? ??? 10 jjrr??? 3 2 2 1m m m mr r g r? ? ? ??? 120 mmrr???? 2 1 1m m m mr r g r? ? ??? 10 mmrr??? 1m m mr r g? ? 則 mr 為 a及 n的最大公因子。 (歐幾里德算法求 gcd的主要概念在于：若 c=dg+r，則 (c，d)=(d， r)。因此在上述算法中， (a， n)=( 0r ， 1r )=(1r ， 2r )=? 1( , )mmrr? =。 0( , )mrr=mr 。 可以通過舉例說明利用歐幾里德算法求逆元的方法，如： 求 1001b≡ lmod 3837， b是 1001關于模 3837的乘法逆元。 因為 (1001， 3837)=l，而 3837=3 1001+834 834=4 167+166 167=1 166+1 所以 l=167166=167(8344 167)=5 167— 834 =5 (1001— 834)一 834 =5 10016 834 =5 10016 (3837— 3 1001) =23 10016 3837 因此 23 1001≡ l(mod3837)，故 1001關于模 3837的乘法逆元為 23。一般 求乘法逆元以歐幾里德算法為佳。 歐幾里德算 法的部分實現(xiàn)代碼如下： package algorithm。 Public class MaxFeed{ Public int getnum(int m,int n){ int r=getleave(m,n)。 while(r!=0){ int[] s = swapnum(m,n,r)。 河南理工大學畢業(yè)設計（論文）說明書 24 m=s[0]。 n=s[1]。 r=getleave(m,n)。 } return n。 } Private int getleave(int m,int n){ int r = m%n。 return r。 } Private int[] swapnum(int m,int n,int r){ m=n。 n=r。 int[] s= newint[2]。 s[0]=m。 s[1]=n。 return s。 } 模冪乘運算 RSA算法中無論是加密還是解密，發(fā)送方和接收方需要完成大數(shù)模冪乘運算。很多加密算法都用到模冪乘運算，如 DiffieHellman密鑰交換算法， ElGamal數(shù)字簽名及 DSA數(shù)字簽名等都需要作模冪乘運算。所不同的是在一些算法中， m， e， n是己知的，可以把 modemn預先計算并存儲起來，在需要時調(diào)用即可。而 RSA則不同，僅有 e和 n是己知的， m是未知的，因此，不能采用預先計算的辦法來解決 RSA的模冪乘運算問題。 計算模冪運算 memod n不能先計算 me然后再求 模，因為如果 m為 200位的大數(shù)， em 的結(jié)果會占用巨量的存儲空間而無法實現(xiàn)，必須對 em 的中間結(jié)果進行求模運算，使結(jié)果二進制位數(shù)始終保持在一定范圍內(nèi)。如果將 e劃分后，取冪可作為一連串乘法，并且每次都進行模運算，可使運算速度加快。 河南理工大學畢業(yè)設計（論文）說明書 25 例如，如果要計算 8 modan，不需要直接做 7次乘法和一個大數(shù)的模化簡，即 a a a a a a a a mod n 而是應進行三次較小的乘法和三次較小的模化簡，即 2 2 2{ ( m o d ) m o d } m o da n n n 當冪指數(shù) e不是偶數(shù)時，計算 modemn稍微麻煩點。例如 2 5 2 4 8 1 6m o d m o d m o da n a a n a a a n? ? ? ? ? 2 2 2 2 2 2 2 2 2 2 2(( ) ) ((( ) ) ) mod ((( ) ) ) moda a a n a a n? ? ? 適當存儲中間結(jié)果，只需要 6次乘法， 2 2 2 2((( ((( mod ) ) mod ) mod ) mod ) mod ) ) moda n a n n n n a n?? 這種平方 乘降冪方法也被稱之為二進制平 方和乘法。本文設計的 1024位的 RSA算法就是基于這個思想。使 e快速哀減，并分成乘法和平方運算可以提高 em 計算速度，從而提高 RSA的實現(xiàn)速度。 一般地，根據(jù)對指數(shù) e掃描方向不同，求 modemn的二進制掃描算法又分為兩種：LR算法 (從左到右掃描算法 )與 RL算法 (從右到左掃描算法 )從左到右掃描法 (即 LR算法 )描述為： Input： m， e， n Output： modemn 1)if 1 1Ne ? ? then c=m else c=l 2)for i=N2 down to 0 3)c=c c mod n 是 LR算法。例如要計算 modban本沒計采用如下流 程來計算模冪運算 河南理工大學畢業(yè)設計（論文）說明書 26 圖 模冪運算實現(xiàn)流程圖 從流程圖中可以看出，模冪運算是由一系列的模乘和模平方運算來實現(xiàn)的，且對模指數(shù)的掃描是采用從左到右的掃描方式，如果 ei為 1，則進行模乘運算；如果 ie 為 O，則進行模平方運算。模乘和模平方運算的區(qū)別僅在于輸入的不同，因此可以把他們統(tǒng)一歸為模乘運算。因此，模乘運算是 RSA算法的核心運算，模冪運算由反復的模乘運算來完成。 開始 d=1 i=0? d0? ie =1 d=(d*d)%n 返回d+n d=(d*a)%n 返回 d i=i1 Yes No No Yes 河南理工大學畢業(yè)設計（論文）說明書 27 第 4 章 數(shù)據(jù)文件加解密的實現(xiàn)過程 本系統(tǒng)的主要功能就是實現(xiàn) 對數(shù)據(jù)文件加解密的一個演示過程，這是一個基于 B/S架構的系統(tǒng)，登陸網(wǎng)址為 主界面如圖 圖 系統(tǒng)主界面 用戶信息管理 此功能分為了三個模塊：（ 1）用戶 信息管理；（ 2）用戶信息添加 ； （ 3）用戶注冊信息，主要是為了便于管理用戶的信息，同時可以對用戶信息進行更改操作，實現(xiàn)界面如, 河南理工大學畢業(yè)設計（論文）說明書 28 圖 用戶管理界面 圖 用戶信息管理 RSA 算法加解密管理 此部分分為了三個模塊，主要是密鑰產(chǎn)生，加密，解密，界面如圖 ： 河南理工大學畢業(yè)設計（論文）說明書 29 圖 RSA文件加解密 密鑰產(chǎn)生 此設計采用隨機生成大素數(shù)，并生成密鑰對，生成的公鑰和私鑰存放在一個 .dat文件中，在加解密過程中，系統(tǒng)會自動調(diào)用此文件進行加解密，存放路徑為：D:/webspace/Wan/dat 中， 截圖 ： 圖 密鑰存放地址 加密文件 由以上敘述可知，在進行加密文件之前，已經(jīng)產(chǎn)生密鑰并進行了保存，本系統(tǒng)實現(xiàn)了對 .txt 文件， .jpg 文件， .doc 文件等小型文件的加解密，可以從本地讀取任意在理論上可以用 RSA加解密的文件，解密之后文件會自動保存在路徑 D:/webspace/rsa中，下面給出不同類型的文件加密前后的截圖： 首先選取需要加密的文件如 下圖： 圖 選取加密文件 河南理工大學