【導讀】的密鑰隨機序列與明文按位異或。密碼就是一組含有參數(shù)k的變換E。設已知信息m，通。過變換E得到密文c。即c=Ek這個過程稱之為加密，參數(shù)k稱為密鑰。解密算法D是加密算法E的逆運算，分別為加密解密函數(shù)，滿足dk=x,這里x∈P。xn,其中xi∈P,Alice用加密算法ek作yi=ek1≤i≤。.yn,在信道上發(fā)送，2*.加密函數(shù)ek必須是單射函數(shù)，就是一對一的函數(shù)。3*.好的密鑰算法是唯密鑰而保密的。這個加密體制為對稱的，否則稱為非對稱的。兩者相互對立、促進。暫時接近密碼機，可選擇密文串，并構造出相應的明文。Shannon理論：僅當密鑰至少和明文一樣長時才無條件安全。本，才是無條件安全的。所有其它的密碼系統(tǒng)在唯密文攻擊。這個算法則被認為在計算上是安全的。用作攻擊輸入所需的數(shù)據(jù)量。進行攻擊所需要的存儲量。中的另外一個字符，代替后的各字母保持原來位置。進行逆替換就可恢復出明文。母表的一一映射。替的密文并不唯一。是不行的，然而，可由統(tǒng)計的方式破譯它。

　　

【正文】 推論：若 a與 n互素，則 a與 a φ(n)1 互為逆元。 例： a=4， n=7， φ(7)=6， a φ(7)1 =45=1024 所以， 4和 1024在模 7下互為逆元。 驗證： 4x1024 mod7 =1 78 求乘法逆元 Function Euclid(d,f) //求 d在模 f下的逆元 1) (x1,x2,x3)(1,0,f)。(y1,y2,y3)(0,1,d)。 2) If y3=1 then print “逆元是 ” y2 else print “無逆元 ” 。 End. 3) Q=[x3/y3] 4) (t1,t2,t3)(x1Q*y1, x2Q*y2, x3Q*y3) 5) (x1,x2,x3)(y1,y2,y3)。 6) (y1,y2,y3)(t1,t2,t3) 7) Go to 2) 79 高次冪剩余的運算 公開密鑰算法 要計算 gn mod p， 因 g、 n、 p都是大數(shù)而不能采用先高次冪再求剩余的方法來處理 ，而要采用平方取模的算法 ， 即每一次平方或相乘后 ， 立即取模運算 。 歐幾里德算法 歐幾里德算法可以迅速地找出給定的兩個整數(shù) a和 b的最大公因數(shù) gcd（ a， b） ， 并可判斷 a與 b是否互素 ， 因此該算法可用來尋找加密密鑰和解密密鑰 。 80 X r mod p 的快速算法流程圖 Ax Br C1 B=0 輸出 C B mod 2=0 B B/2 A A*A mod p B B1 CC*A mod p Y N N Y 81 一、 RSA算法概述 公開密鑰算法 每個合數(shù)都可以唯一地分解出素數(shù)因子 6 = 2 3 999999 = 3337111337 27641 = 131121 從 2 開始試驗每一個小于等于 √27641 的素數(shù)。 素數(shù)：只能被 1和它本身整除的自然數(shù)；否則為合數(shù)。 整數(shù) n的十進制位數(shù) 因子分解的運算次數(shù) 所需計算時間（每微秒一次） 50 75 104天 100 74年 200 300 500 82 素數(shù)的檢驗 素數(shù)的產(chǎn)生 目前 ， 適用于 RSA算法的最實用的辦法是概率測試法 。 該法的思想是隨機產(chǎn)生一個大奇數(shù) ， 然后測試其是否滿足條件 ， 如滿足 ， 則該大奇數(shù)可能是素數(shù) ，否則是合數(shù) 。 素數(shù)定理說明素數(shù)有無窮多個 ， 同時也說明通過隨機產(chǎn)生一個大奇數(shù)來判斷其素性是具有實用性的 。 83 素數(shù)的檢驗 ? Wilson定理： P是素數(shù) ?? (P 1)! Mod P =1 當 P較大時，很費時間，無實際價值。 ? RabinMiller方法 概率檢驗 Witness(a,n) /* 將 n1表示為 bk b k1… b0的形式 n是待檢驗的數(shù)， a是小于 n的整數(shù)。若返回 True， 則 n肯定不是素數(shù)；若返回 False， 則n有可能是素數(shù)。 */ 84 RabinMiller方法 { d=1 for i=k down to 0 { x=d。d= (d? d) mod n。 if d=1 amp。 (x1) amp。(x1) return True。 if bi=1 then d=(d?a) mod n} if d1 then return True 。 return False 。 } 對于 s個不同的 a， 重復調(diào)用此算法，每次返回 False， 則 n是素數(shù)的概率至少為 12s 85 二、 RSA算法的實現(xiàn) 公開密鑰算法 RSA加密算法的過程 1． 取兩個隨機大素數(shù) p和 q（ 保密 ） 2． 計算公開的模數(shù) n=p*q(公開 ) 3． 計算秘密的歐拉函數(shù) ?(n) =（ p1)*(q1)（ 保密 ） ， 丟棄p和 q， 不要讓任何人知道 。 4． 隨機選取整數(shù) e,滿足 gcd(e, ?(n))=1(公開 e加密密鑰 ) 5． 計算 d滿足 de≡1(mod ?(n))(保密 d解密密鑰 ) 6． 將明文 x（ 按模為 r自乘 e次冪以完成加密操作 ， 從而產(chǎn)生密文 y（ X、 Y值在 0到 n1范圍內(nèi) ） 。 Y=xe mod n 7． 解密：將密文 y按模為 n自乘 d次冪 。 X=Yd mod n 86 二、 RSA算法的實現(xiàn) 公開密鑰算法 例設 p=43,q=59,r=p?q=43*59=2537, ?(r)=(p1)(q1) =42*58 =2436, 取 e=13,求 e的逆元 d 解方程 d ? e = 1 mod 2436 2436 =13* 187+ 5, 13= 2* 5+ 3 5= 3+ 2, 3= 2+ 1 所以 1= 3 2 ， 2= 5 3， 3 =13 2* 5 5 =2436 13* 187 所以， 1= 3 2= 3（ 5 3） = 2* 3 5 =2*（ 13 2* 5） 5= 2 *13 5* 5 =2* 13 5*（ 2436 13 *187） =937* 13 5* 2346 即 937* 13 ≡ 1 mod 2436 取 e= 13 時 d= 937 87 二、 RSA算法的實現(xiàn) 公開密鑰算法 若有明文 public key encryptions 先將明文分塊為 pu bl ic ke nc ry pt io ns 將明文數(shù)字化令 a b z 分別為 00 01 25 得 1520 0111 0802 1004 2404 1302 1724 1519 0814 1418 利用加密可得密文 0095 1648 1410 1299 1365 1379 2333 2132 1751 1289 88 公開密鑰算法 關于素數(shù)的分布 1 100 25 101 200 21 201 300 16 301 400 16 401 500 17 501 600 14 601 700 16 701 800 14 801 900 15 901 1000 14 素數(shù)定理：當 X變得很大時，從 2到 X區(qū)間的素數(shù)數(shù)目 ?(X)與 X/ln(X)的比值趨近于 1，即 ?(X) X/ln(X) = 1 lim x?? X ?(X) X/ln(X) ?(X) X/ln(X) 1000 168 145 10,000 1,229 1,086 100,000 9,592 8,686 1,000,000 78,498 72,382 10,000,000 664,579 620,421 100,000,000 5,761,455 5,428,681 1,000,000,000 50,847,478 48,254,942 89 二、 RSA算法的實現(xiàn) 公開密鑰算法 在 2到 X的區(qū)間中，隨機選擇一個值為素數(shù)的概率近似等于 ?(X)/(X1)。 可以證明，在找到一個素數(shù)之前，平均要進行 (X1)/ ?(X)≈LN(X)次實驗。 大數(shù)的運算 上百位大數(shù)之間的運算是實現(xiàn) RSA算法的基礎 ,因此程序設計語言本身提供的加減乘除及取模算法都不能使用，否則會產(chǎn)生溢出，必須重新編制算法。在編程中要注意進位和借位，并定義幾百位的大數(shù)組來存放產(chǎn)生的大數(shù)。 90 RSA 的安全性 公開密鑰算法 依賴于大數(shù)分解 ， 但是否等同于大數(shù)分解一直未能證明 。 不管怎樣 ， 分解 n是最顯然的攻擊方法 。 1994年 4月 26日 ， 美國各大媒體報道：由 RSA發(fā)明人在 17年前出的 129位數(shù)字已被因子分解 ， 并破解了附帶的密語： The magic words are squeamish ossifrage. 目前 ， 已能分解 140位十進制的大素數(shù) 。 因此 ，模數(shù) n必須選大一些 。 RSA最快的情況也比 DES慢上 100倍 ， 無論是軟件還是硬件實現(xiàn) 。 速度一直是 RSA的缺陷 。 一般只用于少量數(shù)據(jù)加密 。 91 RSA算法的脆弱性 公開密鑰算法 1) 不能證明 RSA密碼破譯等同于大數(shù)因子分解 2) 速度問題 提高 p?q將使開銷指數(shù)級增長 3) 至少有 9個明文 ， 加密后不變，即 me mod n=m 4) 普通用戶難于選擇 p、 q。 對 p、 q的基本要求： ? p、 q不相同，即不要太接近，又不能差別太大 ? p q1都有大素數(shù)因子，增加猜測 φ(r) 難度 ? Gcd( p1,q1)應當小 92 RSA算法的脆弱性 公開密鑰算法 5) P、 q選擇不當，則變換周期性、封閉性而泄密 例： p=17， q=11， e=7， 則 n=187。 設 m=123， 則 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文 m經(jīng)過 4次加密，恢復成明文。 總之， RSA對用戶要求太苛刻，密鑰不能常更換。 93 其它公鑰密碼體制 ? 背包體制 1978年提出 5年后被 Shamir破解 ? ElGamal 體制 1985年 基于有限域上計算離散對數(shù)難解性，已用于 DSS(數(shù)字簽名標準） 例： 3x mod 17=5， 解得： x=6 3x mod 13=7， 無解 ? 橢圓曲線體制 (ECC) 1985年 基于離散對數(shù) 優(yōu)點：安全性高；密鑰短；靈活性好。 同等安全下的密鑰長度： RSA:512 1024 2048 21000 ECC:106 160 211 600 94 ElGamel 加密體制： 選大素數(shù) P及其本源根 g， p、 g公開； 隨機選一整數(shù) x作為私鑰 (保密 )； 計算 y=gx mod p 。 將 y作為公開密鑰。 ? 加密過程 在公鑰數(shù)據(jù)庫中查找獲取用戶的公鑰 y； 在 0 ~ p1間取整數(shù) k0。 計算下式并發(fā)送 C1和 C2: K=yk0 mod p， C1=gk0 mod p， C2=K?m mod p； ? 解密過程 計算 K=C1x mod p 明文 m=C2 ?K1 mod p