【正文】 系統(tǒng)設(shè)計(jì) 算法描述RSA算法描述：(1) 密鑰的產(chǎn)生① 選兩個(gè)保密的大素?cái)?shù)p和q。② 計(jì)算n=pq，φ(n)=(p1)(q1),其中φ(n)是n的歐拉函數(shù)值。③ 選一整數(shù)e，滿足1eφ(n)，且gcd(φ(n),e)=1。④ 計(jì)算d，滿足de≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運(yùn)算可知，它的乘法逆元一定存在。⑤ 以{e,n}為公開鑰,{d,n}為秘密鑰。(2) 加密加密時(shí)首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長(zhǎng)度小于log2n。然后對(duì)每個(gè)明文分組m，作加密運(yùn)算： c≡me mod n(3) 解密對(duì)密文分組的解密運(yùn)算為： m≡cd mod n下面證明RSA算法中解密過程的正確性。證明： 由加密過程知c≡me mod n，所以cd mod n≡med mod n≡m1 mod φ(n) mod n≡mkφ(n)+1 mod n要獲得兩個(gè)隨機(jī)的小于100的素?cái)?shù)，可以首先將系統(tǒng)當(dāng)前時(shí)間設(shè)置為隨機(jī)數(shù)種子，然后對(duì)生成的隨機(jī)數(shù)取100模，然后調(diào)用判斷素?cái)?shù)的函數(shù)。要判斷一個(gè)屬實(shí)否為素?cái)?shù)，可以判斷數(shù)n從2到n的開方，是否能整除n。偽代碼如下： for(i從 2 到 n的開方 。 i++) { if(n被i整除) 則n不是素?cái)?shù)終止循環(huán)； if（i n的開方 ） 返回n為宿舍； }求最大公因子的算法：Euclid算法就是用這種方法，因gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的輸入是兩個(gè)正整數(shù)，設(shè)為d，f，并設(shè)f d。Euclid（f, d）①X←f。 Y←d；② if Y=0 then return X=gcd(f,d)；③ R=X mod Y；④ X=Y；⑤ Y=R；⑥ goto ②。求乘法逆元：推廣的Euclid算法先求出gcd(a, b)，當(dāng)gcd(a, b)=1時(shí)，則返回b的逆元。Extended Euclid(f, d) （設(shè) f d） ① (X1,X2,X3)←(1,0,f)。(Y1,Y2,Y3)←(0,1,d)。② if Y3=0 then return X3=gcd(f, d)；no inverse。③ if Y3=1 then return Y3=gcd(f, d)；Y2=d1 mod f。④ Q=X3Y3 ；⑤ (T1,T2,T3)←(X1QY1,X2QY2,X3QY3)。⑥ (X1,X2,X3)←(Y1,Y2,Y3)。⑦ (Y1,Y2,Y3)←(T1,T2,T3)。⑧ goto ②。處理明文：將明文的每個(gè)字符提取出來將其裝換為數(shù)字。進(jìn)行加密處理，將處理后的數(shù)字字符用“+”號(hào)相連。其中加密的算法為：求am可如下進(jìn)行，其中a，m是正整數(shù)： 將m表示為二進(jìn)制形式bk bk1…b0，即m=bk2k+bk12k1+…+b12+b0因此：例如：19=124+023+022+121+120，所以a19=((((a1)2a0)2a0)2a1)2a1從而可得以下快速指數(shù)算法：c=0。 d=1；For i=k downto 0 d0 { c=2c。 d=(dd) mod n。 if bi=1 then { c=c+1。 d=(da) mod n } }return d.其中d是中間結(jié)果，d的終值即為所求結(jié)果。c在這里的作用是表示指數(shù)的部分結(jié)果，其終值即為指數(shù)m，c對(duì)計(jì)算結(jié)果無任何貢獻(xiàn)，算法中完全可將之去掉。解密過程：將“+”連接的數(shù)字字符轉(zhuǎn)換為數(shù)字并相加，用密鑰做與加密相同的算法，即可得出明文。4 源代碼： int m_p。 int m_q。 int m_n。 int m_code。 int m_decode。 CString m_dtxt。 CString m_etxt。 CString m_ptxt。：void CRSADlg::OnButtonProduce() //產(chǎn)生公鑰和密鑰函數(shù){ UpdateData(true)。 while(true) { srand(time(0))。 m_p = rand() % 100。 m_q = rand() % 100。 if (isPrime(m_p) amp。amp。 isPrime(m_q)) break。 } m_n = m_p * m_q。 int fiN = (m_p 1) * (m_q 1)。 //int e。 for (int i = 3。 i fiN。 i++) { if (isPrime(i) amp。amp。 gcd(fiN, i) == 1) { m_code = i。 break。 } } Euler(m_code, fiN)。 UpdateData(false)。}代碼分析：首先設(shè)置系統(tǒng)的當(dāng)前時(shí)間為隨機(jī)種子，循環(huán)找出p和q并且調(diào)用判斷素?cái)?shù)的函數(shù)isPrime(int)使p,q都為小于100的素?cái)?shù)，然后fiN = (m_p 1) * (m_q 1)產(chǎn)生fiN，產(chǎn)生m_n = m_p * m_q，通過調(diào)用gcd(fiN, i)找出與fiN互素的數(shù)m_code，調(diào)用uler(m_code, fiN)找出m_decode，最后UpdateData(false)刷新文本框顯示出結(jié)果。：void CRSADlg::OnCode() //加密函數(shù){ CString temp。 UpdateData(true)。 CString encSt = 。 CString e2st = 。 if (()) return。 for (int i = 0。 i ()。 i++) { temp = encSt。 (%s%d%s,temp,power((int)(i), m_code, m_n),+)。 } m_etxt = encSt。 UpdateData(false)。}代碼分析：首先判斷明文文本框是否為空，若為空則返回。取出明文的每個(gè)字符，將其裝換為數(shù)字，通過加密函數(shù)power轉(zhuǎn)換后，生成的數(shù)字字符用“+”號(hào)相連，即為密文。調(diào)用UpdateData(false)刷新文本框，顯示加密后的結(jié)果。void CRSADlg::OnDecode() // 解密函數(shù){ int ptr。 int tok。 CString temp = 。 UpdateData(true)。 CString DecSt = 。 //int t = ()。 for (int i = 0。 i ()。) { ptr = (+, i)。 tok = atoi((i, ptr i))。 temp = DecSt。 (%s%c, temp, char(power(tok, m_decode, m_n)))。 i = i + num(tok) + 1。 } m_dtxt = DecSt。 UpdateData(false)。}代碼分析：計(jì)算出密文字符串的長(zhǎng)度，循環(huán)尋找以字符“+”分隔得數(shù)字字符串，并將其轉(zhuǎn)換問數(shù)字，然后調(diào)用power函數(shù)處理，將得出的數(shù)字轉(zhuǎn)換為字符，將得出的字符連接起來就解密出了明文，最后調(diào)用UpdateData(false)刷新文本框，顯示出解密出的結(jié)果。：int CRSADlg::power(int a, int n, int m) //求出a的n次方模m的值{ int z=1, t。 for(t=a。 n0。 n=1) { if (n%2==1) z=(z*t) % m。 t=(t*t) % m。 } return(z)。}BOOL CRSADlg::isPrime(int x) //判斷整數(shù)i是否為素?cái)?shù){ int i。 for (i = 2。 i = (int)sqrt(x)。 i++) { if (x % i == 0) break。 } if (i (int)sqrt(x)) return true。 return false。}int CRSADlg::gcd(int a, int b) //求出a與b的公因子{ if (a == 0) { return b。 } else { return gcd(b % a, a)。 }}void CRSADlg::Euler(int e, int fin) //求出e相對(duì)模fin的乘法逆元{ int u1 = 1。 int u2 = 0。 int u3 = fin。 int v1 = 0。 int v2 = 1。 int v3 = e。 int v = 1。 int t1, t2, t3。 int q。 int uu, vv。 int inverse, z。 while (v3 != 0) { q = (int)(u3 /v3)。 t1 = u1 q * v1。 t2 = u2 q * v2。 t3 = u3 q * v3。 u1 = v1。 u2 = v2。 u3 = v3。 v1 = t1。 v2 = t2。 v3 = t3。 z = 1。 } uu = u1。 vv = u2。 if (vv 0) inverse = vv + fin。 else inverse = vv。 m_decode = inverse。}5 測(cè)試數(shù)據(jù)及結(jié)果 產(chǎn)生公鑰和密鑰點(diǎn)擊密鑰生成，運(yùn)行效果如下圖：圖51 產(chǎn)生公鑰和密鑰效果圖 加密與解密，運(yùn)行效果如下圖：圖52 加密效果圖，運(yùn)行效果如下圖：