【正文】 計算下式并發(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 。 將 y作為公開密鑰。 93 其它公鑰密碼體制 ? 背包體制 1978年提出 5年后被 Shamir破解 ? ElGamal 體制 1985年 基于有限域上計算離散對數(shù)難解性，已用于 DSS(數(shù)字簽名標準） 例： 3x mod 17=5， 解得： x=6 3x mod 13=7， 無解 ? 橢圓曲線體制 (ECC) 1985年 基于離散對數(shù) 優(yōu)點：安全性高；密鑰短；靈活性好。 設 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次加密，恢復成明文。 91 RSA算法的脆弱性 公開密鑰算法 1) 不能證明 RSA密碼破譯等同于大數(shù)因子分解 2) 速度問題 提高 p?q將使開銷指數(shù)級增長 3) 至少有 9個明文 ， 加密后不變，即 me mod n=m 4) 普通用戶難于選擇 p、 q。 速度一直是 RSA的缺陷 。 因此 ，模數(shù) n必須選大一些 。 不管怎樣 ， 分解 n是最顯然的攻擊方法 。在編程中要注意進位和借位，并定義幾百位的大數(shù)組來存放產(chǎn)生的大數(shù)。 可以證明，在找到一個素數(shù)之前，平均要進行 (X1)/ ?(X)≈LN(X)次實驗。 Y=xe mod n 7． 解密：將密文 y按模為 n自乘 d次冪 。 } 對于 s個不同的 a， 重復調用此算法，每次返回 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， 不要讓任何人知道 。 if bi=1 then d=(d?a) mod n} if d1 then return True 。 (x1) amp。d= (d? d) mod n。若返回 True， 則 n肯定不是素數(shù)；若返回 False， 則n有可能是素數(shù)。 83 素數(shù)的檢驗 ? Wilson定理： P是素數(shù) ?? (P 1)! Mod P =1 當 P較大時，很費時間，無實際價值。 該法的思想是隨機產(chǎn)生一個大奇數(shù) ， 然后測試其是否滿足條件 ， 如滿足 ， 則該大奇數(shù)可能是素數(shù) ，否則是合數(shù) 。 素數(shù)：只能被 1和它本身整除的自然數(shù)；否則為合數(shù)。37 27641 = 1311133 999999 = 3 歐幾里德算法 歐幾里德算法可以迅速地找出給定的兩個整數(shù) a和 b的最大公因數(shù) gcd（ a， b） ， 并可判斷 a與 b是否互素 ， 因此該算法可用來尋找加密密鑰和解密密鑰 。 End. 3) Q=[x3/y3] 4) (t1,t2,t3)(x1Q*y1, x2Q*y2, x3Q*y3) 5) (x1,x2,x3)(y1,y2,y3)。(y1,y2,y3)(0,1,d)。 例： a=4， n=7， φ(7)=6， a φ(7)1 =45=1024 所以， 4和 1024在模 7下互為逆元。 例： φ(3)= φ(4) = φ(6) =2， φ(5)=4， φ(7) =6 φ(12)=6 75 數(shù)論知識簡介 模運算性質： 同余 ? 模運算滿足自反性、對稱性、傳遞性； a=a mod n； 若 a=b mod n， 則 b=a mod n； 若 a=b mod n， b=c mod n， 則 a=c mod n ? 若 a mod n=b mod n， 則 (ab)mod n=0； [(a mod n) +(b mod n)]mod n=(a + b) mod n； ； * * ； 例： 152 mod 12 =(3*3) mod 12=9 76 ? 若 n是素數(shù)，則 φ(n)=n1 若 n=p*q， p、 q是素數(shù)，則 φ(n)=(p1)*(q1) 例： φ(21)= φ(3*7)=2*6=12 ? Fermat小定理：若 m是素數(shù)，且 a不是 m的倍數(shù)，則 am1 mod m=1。 ? 用 Euclid算法求乘法逆元 若 a和 n互素，則 a在模 n下有逆元。 公開密鑰算法 74 數(shù)論知識簡介 ? 互素：若 gcd(a,b)=1， 則整數(shù) a和 b互素。 RSA得到了世界上的最廣泛的應用 ， ISO在 1992年頒布的國際標準 ,將 RSA算法正式納入國際標準 。 RSA算法是一種分組密碼體制算法 ， 它的保密強度是建立在具有大素數(shù)因子的合數(shù) ，其因子分解是困難的 。若 B要向 A保密送去明文 m,可查 A的公開密鑰 ka， 若用ka加密得密文 c， A收到 c后 ， 用只有 A自己才掌握的解密密鑰 ka’對 x進行解密得到 m。 不能提供法律證據(jù) :不僅要保密還要解決證實問題 。 AES被開發(fā)用于替代 DES， 但 NIST預測 Triple DES仍將在近期作為一種實用的算法，單 DES將逐步退出。 優(yōu)劣標準：安全性；計算效率；內存要求；簡便靈活。 20xx年 10月 2日，美國商務部部長宣布比利時的 Rijndael算法成為新的 AES。 71 三、高級加密標準 (AES) NIST(國家標準技術研究所 )1997年 9月 12日發(fā)出征集高級加密標準的通知 。對 DES更有效。 線性密碼分析法： 243次嘗試 1992年提出，已知明文攻擊。分析明文對的差值對密文對差值的影響。 ? 提高加密強度（如增加密鑰長度），系統(tǒng)開銷呈指數(shù)增長，除提高硬件、并行處理外，算法本身和軟件技術無法提高加密強度。 68 DES算法的脆弱性 3） S盒中的重復因子及密鑰多值問題 ? S盒設計中利用重復因子，導致 S盒對不同輸入可能產(chǎn)生相同輸出，使加密、解密變換的密鑰具有多值性。 ? 64位固定分組，短組模式，易造成密文重復組塊 ? 有限的函數(shù)作用域 ASCII碼 0~127 ? 子密鑰只參與異或簡單的運算，有可能損害變換精度。 67 DES算法的脆弱性 DES的半公開性： S盒的原理至今保密，所以不能算作真正的公開加密算法。 單獨用一種方法，容易被攻破。 擴展輸出對輸入的相關性，盡量使密文的每一位受明文中多位影響。通過代替法實現(xiàn)，如 S盒。仍然需要一個初始向量（ IV） 65 二、數(shù)據(jù)加密標準 (DES) 數(shù)據(jù)加密標準 + ? K1 + ? K2 + ? Kn DES設計原理 重復交替使用選擇函數(shù) S和置換運算 P兩種變換 使用 Feistel密碼結構 (1967年） 66 混淆 (confusion)： 使密文與明文的統(tǒng)計獨立性關系復雜化。如對字符加密，只要密鑰長度 8bit。流密碼無需填充消息，實時運行。 61 分組密碼運行模式 數(shù)據(jù)加密標準 ECB（ 電碼本）模式： 各明文組獨立地以同一密鑰加密；傳送短數(shù)據(jù) 62 分組密碼運行模式 ? CBC（ 密碼分組鏈接）模式： Cn=Ek[Cn1⊕ Pn]； 初始向量 V1； 用途：傳送數(shù)據(jù)分組；認證。 2~16輪 2． 5 把 R（ 16） 和 L（ 16） 順序串聯(lián)起來得到一個 64位數(shù) 。 2． 4． 7 把 R（ i1） 的值賦給 L（ i） ， 完成第 1輪乘積變換 。 2． 4． 5八個選擇函數(shù) Sj(1≤j≤8)的輸出拼接為 32位二進制數(shù)據(jù)區(qū)組 ， 把它作為 P盒置換 的輸入 ， 得到輸出 2． 4． 6 把得到的結果與 L（ i1） 作異或運算 。 n即是 Sj密箱里用來替換 Z j的數(shù)所在的行數(shù) 。 m即是 Sj密箱里用來替換 Z j的數(shù)所在的列數(shù) 。 從 j=1開始 。 16位為 Z 1， 712位為 Z 2,…… 4348位為 Z 8。 2． 4． 1 利用 擴展置換 E， 擴展 32位的成 48位 （ P54 表 ) 2． 4． 2 用 E{R (i1)}與子密鑰 K(i)作按位 異或運算 。 2． 3 將變換后的數(shù)據(jù)塊等分成前后兩部分，前 32位記為 L0,后32位記為 R0。 2． 對 64位數(shù)據(jù)塊的處理： 2． 1 把數(shù)據(jù)分成 64位的數(shù)據(jù)塊 ， 不夠 64位的以適當方式填補 。 串聯(lián) Ci、 Di， 得到一個 56位數(shù) ， 然后對此數(shù)作子密鑰換位表 PC2變換以產(chǎn)生 48位子密鑰 Ki。 58 二、數(shù)據(jù)加密標準 (DES) 數(shù)據(jù)加密標準 計算子密鑰 (共 16個 )， 從 i=1開始 。 55 二、數(shù)據(jù)加密標準 (DES) 數(shù)據(jù)加密標準 Ci(28位 ) Di(28位 ) 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Ki(48位 ) 密鑰置換 2 去掉第 9， 18，22， 25， 35，38， 43， 54位， 56位變成 48位 56 二、數(shù)據(jù)加密標準 (DES) 數(shù)據(jù)加密標準 L0R0 ←IP( 明文 ) L1←R 0 R1← L 0??(R0,K1) L2←R 1 R2← L 1??(R1,K2) …… L16←R 15 R16← L 15??(R15,K16) 密文 ← IP1(R16L16) 加密過程 ： L0R0 ←IP(64 位明文 ) Ln←R n1 Rn← L n1??(Rn1,Kn) 64位密文 ← IP1(R16L16) 解密過程 ： R16L16 ←IP(64 位密文 ) Rn1←L n Ln1←R n??(Ln,Kn) 64位明文 ← IP1(L0R0) 57 二、數(shù)據(jù)加密標準 (DES) 數(shù)據(jù)加密標準 DES算法 1. 處理密鑰 : 從用戶處獲得 64位密鑰 Key.(每第 8位為校驗位 ,為使密鑰有正確的奇偶校驗 ,每個密鑰要有奇數(shù)個 ” 1”位 .(本文如未特指 ， 均指二進制位 ) 具體過程 : 對密鑰實施變換 , 經(jīng)過子密鑰換位表 PC1的變換后 ， Key 的位數(shù)由 64 位變成了 56位 。 53 二、數(shù)據(jù)加密標準 (DES) 數(shù)據(jù)加密標準 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19