【正文】 ,95,其它公鑰密碼體制,背包體制 1978年提出 5年后被 Shamir破解 ElGamal 體制 1985年 基于有限域上計算離散對數(shù)難解性，已用于DSS(數(shù)字簽名標(biāo)準(zhǔn)） 例：3x mod 17=5，解得：x=6 3x mod 13=7， 無解 橢圓曲線體制(ECC) 1985年 基于離散對數(shù) 優(yōu)點：安全性高；密鑰短；靈活性好。設(shè)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次加密，恢復(fù)成明文。,93,RSA算法的脆弱性,公開密鑰算法,不能證明RSA密碼破譯等同于大數(shù)因子分解 速度問題 提高p?q將使開銷指數(shù)級增長 至少有9個明文，加密后不變，即me mod n=m 普通用戶難于選擇p、q。速度一直是RSA的缺陷。因此，模數(shù)n必須選大一些。不管怎樣，分解n是最顯然的攻擊方法。 歐幾里德算法 歐幾里德算法可以迅速地找出給定的兩個整數(shù)a和b的最大公因數(shù) gcd（a，b），并可判斷a與b是否互素，因此該算法可用來尋找加密密鑰和解密密鑰。素數(shù)定理說明素數(shù)有無窮多個，同時也說明通過隨機產(chǎn)生一個大奇數(shù)來判斷其素性是具有實用性的。 目前，適用于RSA算法的最實用的辦法是概率測試法。,89,素數(shù)的檢驗,素數(shù)的產(chǎn)生 在 2到X的區(qū)間中，隨機選擇一個值為素數(shù)的概率近似等于?(X)/(X1)。 x=yd mod r,88,二、RSA算法的實現(xiàn),公開密鑰算法,大數(shù)的運算 上百位大數(shù)之間的運算是實現(xiàn)RSA算法的基礎(chǔ),因此程序設(shè)計語言本身提供的加減乘除及取模算法都不能使用，否則會產(chǎn)生溢出，必須重新編制算法。 4．隨機選取整數(shù)e,滿足 gcd(e, ?(r))=1(公開e加密密鑰) 5．計算d滿足de≡1(mod ?(n))(保密d解密密鑰) 6．將明文x（按模為r自乘e次冪以完成加密操作，從而產(chǎn)生密文y（x、y值在0到r1范圍內(nèi)）。 例：a=4，n=7， φ(7)=6， a φ(7)1 =45=1024 所以，4和1024在模7下互為逆元。,公開密鑰算法,83,數(shù)論知識簡介,互素：若gcd(a,b)=1，則整數(shù)a和b互素。 RSA得到了世界上的最廣泛的應(yīng)用，ISO在1992年頒布的國際標(biāo)準(zhǔn)X.509中,將RSA算法正式納入國際標(biāo)準(zhǔn)。 RSA算法是一種分組密碼體制算法，它的保密強度是建立在具有大素數(shù)因子的合數(shù)，其因子分解是困難的。 ４）從已知的PK不可能推導(dǎo)出SK。,第五章 密碼學(xué)的應(yīng)用,81,公開密鑰算法的主要特點如下： １）用加密密鑰PK對明文A加密后得到密文，再用解密密鑰SK對密文解密，即可恢復(fù)出明文A。 A和B已獲得了相同的秘密值K。 當(dāng)A和B按如下步驟進(jìn)行保密通信： (1)A取大的隨機數(shù)x，并計算 X= gx (mod P) (2)B選取大的隨機數(shù)y，并計算Y = gy (mod P) (3)A將X傳送給B；B將Y傳送給A。,第五章 密碼學(xué)的應(yīng)用,80,DH密鑰交換協(xié)議：A和B協(xié)商一個大素數(shù)p和大整數(shù)g，1gp，g最好是FP中的本原元，即gx mod p可生成1~p1中的各整數(shù)，例：2是11的本原元。公鑰密碼學(xué)中使 最廣泛的有限域為素域FP 。這個算法是基于有限域中計算離散對數(shù)的困難性問題之上的：對任意正整數(shù)x，計算gx 是容易的；但是已知g和y求x使y= gx，是計算上幾乎不可能的。,第五章 密碼學(xué)的應(yīng)用,79,DiffieHellman 密鑰交換算法,Diffie 和Hellman 并沒有給出公鑰密碼實例，也既沒能找出一個真正帶陷門的單向函數(shù)。由于加密函數(shù)是公開的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設(shè)計者（可以通過不安全信道傳送）；由于設(shè)計者擁有Sk，他自然可以解出x=f1(y)。此時加密密鑰便稱為公開密鑰，記為Pk。 注：1*. 僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，δ 稱為陷門信息。,公開密鑰算法,77,一、 RSA算法概述,公鑰密碼(雙鑰密碼、非對稱密碼），是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的 單向陷門函數(shù)是滿足下列條件的函數(shù)f： (1)給定x，計算y=f(x)是容易的； (2)給定y, 計算x使y=f(x)是非常困難的，無實際意義。 1976年，美國學(xué)者Diffie和Hellman發(fā)表了著名論文《密碼學(xué)的新方向》，提出了建立“公開密鑰密碼體制”：若用戶A有加密密鑰ka（公開），不同于解秘密鑰ka’（保密），要求ka的公開不影響ka’的安全。這樣可以避免產(chǎn)生相同的比特流，從而避免“已知明文”攻擊.,76,一、RSA算法概述,傳統(tǒng)密碼體制的缺陷： 密鑰管理的麻煩：n個用戶保存n*(n1)/2個密鑰。 8.OFB模式不是自同步的，如果加密和解密兩個操作失去同步，那么系統(tǒng)需要重新初始化。 6.j的位數(shù)應(yīng)該為8的整數(shù)倍。 4.可以使用不同的初始變量，使得產(chǎn)生不同的密鑰流，從而使得相同的明文使用相同密鑰產(chǎn)生不同的密文。 2.當(dāng)使用相同的密鑰和初始向量的時候，相同明文使用CFB模式加密輸出相同的密文,需要注意的是，在OFB模式相同的密鑰和開始變量產(chǎn)生相同的密鑰流，所以，為了安全原因，一個特定的開始變量對一個給定的密鑰應(yīng)該只使用一次。 8.一旦某位數(shù)據(jù)出錯，會影響到目前和其后的加密數(shù)據(jù).,74,分組密碼運行模式,OFB（輸出反饋）模式：用分組密碼產(chǎn)生一個隨機密鑰流，將此密鑰流和明文流進(jìn)行異或可得密文流。 6.當(dāng)j的取值比較小的時候，相同的明文一般需要更多的循環(huán)來完成加密，這可能會導(dǎo)致過大的開銷。 4.可以使用不同的初始化變量使相同的明文產(chǎn)生不同的密文，防止字典攻擊。 2.當(dāng)使用相同的密鑰和初始向量的時候，相同明文使用CFB模式加密輸出相同的密文。如對字符加密，只要密鑰長度8bit。流密碼無需填充消息，實時運行。 6.不得實時解密，當(dāng)實時性比較高的時候不合適。 4.可以使用不同的初始化向量來避免相同的明文產(chǎn)生相同的密文,一定程度上抵抗字典攻擊。 2.當(dāng)相同的明文使用相同的密鑰和初始向量的時候CBC模式總是產(chǎn)生相同的密文。 4.一個錯誤僅僅會對一個密文塊產(chǎn)生影響.,分組密碼運行模式,70,分組密碼運行模式,CBC（密碼分組鏈接）模式： Cn=Ek[Cn1⊕Pn]；初始向量V1； 用途：傳送數(shù)據(jù)分組；認(rèn)證。 2.數(shù)據(jù)塊重新排序不需要檢測。 AES被開發(fā)用于替代DES，但NIST預(yù)測Triple DES仍將在近期作為一種實用的算法，單DES將逐步退出。 優(yōu)劣標(biāo)準(zhǔn)：安全性；計算效率；內(nèi)存要求；簡便靈活。2000年10月2日，美國商務(wù)部部長宣布比利時的Rijndael算法成為新的AES。,67,三、高級加密標(biāo)準(zhǔn)(AES),NIST(國家標(biāo)準(zhǔn)技術(shù)研究所)1997年9月12日發(fā)出征集高級加密標(biāo)準(zhǔn)的通知 。 提高加密強度（如增加密鑰長度），系統(tǒng)開銷呈指數(shù)增長，除提高硬件、并行處理外，算法本身和軟件技術(shù)無法提高加密強度。,65,DES算法的脆弱性,3）S盒中的重復(fù)因子及密鑰多值問題 S盒設(shè)計中利用重復(fù)因子，導(dǎo)致S盒對不同輸入可能產(chǎn)生相同輸出，使加密、解密變換的密鑰具有多值性。 64位固定分組，短組模式，易造成密文重復(fù)組塊 有限的函數(shù)作用域 ASCII碼 0~127 子密鑰只參與異或簡單的運算，有可能損害變換精度。,63,二、數(shù)據(jù)加密標(biāo)準(zhǔn)(DES),數(shù)據(jù)加密標(biāo)準(zhǔn),DES設(shè)計原理 重復(fù)交替使用選擇函數(shù)S和置換運算P兩種變換 使用 Feistel密碼結(jié)構(gòu)(1967年）,64,DES算法的脆弱性,DES的半公開性：S盒的原理至今保密，所以不能算作真正的公開加密算法。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位二進(jìn)制數(shù)據(jù)區(qū)組，把它作為P盒置換的輸入，得到輸出 2．4．6 把得到的結(jié)果與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位 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位的以適當(dāng)方式填補。 1.2.3.2 串聯(lián)Ci、Di，得到一個56位數(shù)，然后對此數(shù)作子密鑰換位表PC2變換以產(chǎn)生48位子密鑰Ki。,60,二、數(shù)據(jù)加密標(biāo)準(zhǔn)(DES),數(shù)據(jù)加密標(biāo)準(zhǔn),1.2.3 計算子密鑰(共16個)， 從i=1開始。,57,二、數(shù)據(jù)加密標(biāo)準(zhǔn)(DES),數(shù)據(jù)加密標(biāo)準(zhǔn),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位,58,二、數(shù)據(jù)加密標(biāo)準(zhǔn)(DES),數(shù)據(jù)加密標(biāo)準(zhǔn),L0R0 ←IP(明文) L1←R0 R1← L0??(R0,K1) L2←R1 R2← L1??(R1,K2) …… L16←R15 R16← L15??(R15,K16) 密文← IP1(R16L16),加密過程： L0R0 ←IP() Ln←