信息安全密碼編碼學

1信息安全

密碼編碼學沈志東武漢大學國際軟件學院zd_shen@163.com2為什么需要密碼信息的保護信息的存儲：公開的地方信息的交換：使用非隱秘介質信息的傳輸：通過不安全信道安全機制機密性3密碼編碼學基本概念和術語密碼學的歷史密碼技術4基本概念和術語加密(encryption)將報文(或消息)進行編碼，以模糊其含義的過程。encode,encipher解密(decryption)將加密過的報文恢復為原始形式。decode,decipher明文(plaintext)和密文(ciphertext)報文的原始方式為明文，加密后成為密文5基本概念和術語密碼編碼學(cryptography)研究對信息進行編碼,實現(xiàn)對信息的隱蔽密碼專家(cryptographer)密碼分析學(cryptanalytics)研究加密消息的破譯(break)或消息的偽造.密碼破譯者(cryptanalyst)密碼學(cryptology)研究信息系統(tǒng)安全保密的科學，包括密碼編碼學和密碼分析學6密碼算法的分類按照保密的內(nèi)容分受限制的(restricted)算法：算法的保密性基于保持算法的秘密。基于密鑰(key-based)的算法：算法的保密性基于對密鑰的保密。7密碼算法的分類按照明文的處理方法分分組密碼(blockcipher)：將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。流密碼(streamcipher)：又稱序列密碼，每次加密一位或一字節(jié)的明文。

8密碼算法的分類按照密鑰使用方法分對稱密碼算法(symmetriccipher)：又稱傳統(tǒng)密碼算法(conventionalcipher)或秘密密鑰算法、單密鑰算法。非對稱密鑰算法(asymmetriccipher)，又稱公開密鑰算法(public-Keycipher)。9密碼體制加密解密明文P密文C明文P密鑰(K)對稱密碼體制(symmetriccryptosystem)加密密鑰和解密密鑰是相同的C=E(K,P)P=D(K,E(K,P))10密碼體制加密解密明文P密文C明文P加密密鑰Ke解密密鑰KdC=E(Ke,P)P=D(Kd,E(Ke,P)非對稱密碼體制(asymmetriccryptosystem)加密密鑰和解密密鑰是成對出現(xiàn)加密過程和解密過程不同，使用的密鑰也不同11密碼分析密碼分析學企圖利用算法的性質和明文的一般特性或某些明密文推導出特別的明文或使用的密鑰。窮舉攻擊攻擊者對一條密文嘗試所有可能的密鑰，直到得到有意義的明文。12密碼的安全性考慮無條件安全(Unconditionallysecure)無論破譯者有多少密文,他也無法解出對應的明文,即使他解出了,他也無法驗證結果的正確性.一次一密計算上安全的破譯密碼的代價超出密文信息的價值破譯密碼的時間超出密文信息的有效生命期13密碼編碼學基本概念和術語密碼學的歷史密碼技術14密碼學的發(fā)展史古代加密方法（手工階段）古典密碼（機械階段）現(xiàn)代密碼（計算機階段）15古代加密方法起源于公元前440年出現(xiàn)在古希臘戰(zhàn)爭中的隱寫術(steganography)：通過隱藏消息的存在來保護消息。16古代加密方法斯巴達人用于加解密的一種軍事設備(SpartanScytale,400B.C.)發(fā)送者把一條羊皮螺旋形地纏在一個圓柱形棒上思想：置換（permutation)17古代加密方法一個叫AeneasTacticus的希臘人在《論要塞的防護》一書中對傳輸密文做了最早的論述。公元前2世紀，一個叫Polybius的希臘人設計了一種將字母編碼成符號對的方法，他使用了一個稱為Polybius的校驗表，表中包含許多后來在加密系統(tǒng)中常見的方法，如代替與換位。18古典密碼古典密碼的加密方法一般是文字置換，使用手工或機械變換的方式實現(xiàn)。古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出近代密碼系統(tǒng)的雛形，它比古代加密方法復雜，其變化較小。單表代替密碼：Caesar密碼；多表代替密碼：Vigenere密碼、Hill密碼；轉輪密碼：二戰(zhàn)中的Enigma。19古典密碼EngimaTYPEXHagelinC-36TUNNYHagelinC-4820現(xiàn)代密碼計算機的發(fā)展使得基于復雜計算的密碼成為可能，密碼學成為一門新的學科。1949年信息論之父C.E.Shannon發(fā)表了“TheCommunicationTheoryofSecretSystems”，密碼學走上了科學與理性之路1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實驗室的HorstFeistel等的幾篇技術報告21現(xiàn)代密碼對稱密鑰密碼算法進一步發(fā)展1977年DES正式成為標準80年代出現(xiàn)IDEA,RCx,CAST等90年代對稱密鑰密碼進一步成熟：Rijndael,RC6,MARS,Twofish,Serpent等出現(xiàn)2001年Rijndael成為DES的替代者,即AES。22現(xiàn)代密碼公鑰密碼的出現(xiàn)1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了公鑰密碼思想。1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法一些新的密碼技術，如，混沌密碼、量子密碼等23密碼編碼學基本概念和術語密碼學的歷史密碼技術24密碼技術對稱加密技術非對稱加密技術消息認證和HASH函數(shù)25對稱密碼傳統(tǒng)加密技術替換(substitution)：明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復出明文。置換(permutation)，又稱換位(transposition)：明文的字母保持相同，但打亂排列的順序。26替換密碼簡單替換密碼(simplesubstitutioncipher),又稱單字母密碼(monoalphabeticcipher)明文的一個字符用相應的一個密文字符替換，而且密文所用的字符與一般的明文所用字符屬同一語言系統(tǒng)。多字母密碼(ployalphabeticcipher)明文中的字符映射到密文空間的字符還依賴于它在上下文中的位置。27替換密碼——單字母替換Caesar密碼加密：ci=E(pi)=(pi+3)mod26解密：pi=E(ci)=(ci-3)mod26ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC字母編碼treatyimpossiblewuhdwblpsrvvleoh明文密文28替換密碼——單字母替換一般的愷撒密碼加密：ci=E(pi)=(pi+k)mod26解密：pi=E(ci)=(ci-k)mod26其中k為密鑰，1

k

25一般的愷撒密碼的破譯分析已知加密和解密算法需要測試的密鑰只有25個明文所用的語言是已知的，且其意義易于識別?？梢圆捎酶F舉攻擊29替換密碼——單字母替換使用密鑰的愷撒密碼使用密鑰k控制字母表中的排列密文空間增加(26!)ABCDEFGHIJKLMNOPQRSTUVWXYZwordABCEFGHIJKLMNPQRSTUVXYZ字母編碼密鑰為word單表替換密碼每條消息用一個字母表（給出從明文字母到密文字母的映射）加密30替換密碼——單字母替換單字母替換的破譯——語言的統(tǒng)計特性語言的頻率特征連接特征重復特征31替換密碼——單字母替換英文單字母的相對頻率表32替換密碼——單字母替換頻率特征雙字母：THHEINERANREEDONESSTENATTONTHANDOUEANGASORTIISETITARTESEHIOF三字母：THEINGANDHEREREENTTHANTHWASETHFORDTHHATSHEIONINTHISSTHERSVER一半的單詞以esdt結尾一半的單詞以tasw開頭Y的使用頻率90%都集中在單詞的結尾33替換密碼——單字母替換Playfair密碼——多表1854年由英國科學家CharlesWheatstone發(fā)明。將明文中的雙字母音節(jié)作為一個單元并將其轉換成密文的“雙字母音節(jié)”。算法基于一個由密鑰詞構成的5

5字母矩陣。

例：密鑰詞為monarchy，明文為balloon如果該字母對兩個字母相同，則它們之間加一個填充字母，如x；則明文分為四個字母對：balxloon落在矩陣同一行的明文字母對中的字母由其右邊的字母替換；on替換成na落在矩陣同一列的明文字母對中的字母由其下面的字母替換；ba替換成ib(或jb)其他的每組明文字母對中的字母如下替換：它所在的行是該字母的所在行，列則為另一個字母的所在列。

lo替換成pm

lx替換成suMONARCHYBDEFGI/JKLPQSTUVWXZ密文為：ibsupmna或jbsupmna35替換密碼——單字母替換Playfair密碼有26

26=676種字母對組合字符出現(xiàn)幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當?shù)慕Y構信息

36替換密碼——多表替換Vigenere密碼替換規(guī)則由26個類似caesar密碼的替換表組成，其中每一個替換表是對明文字母移位0到25次后得到的替換單表。每個替換單表由一個密鑰字母表示。ABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHI……

……ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJVigenere替換表deceptivedeceptivedeceptivewearediscoveredsaveyourself密鑰明文zicvtwqngrzgvtwavzhcqyglmgj密文38置換密碼將明文的字母順序打亂，得到新的排列最簡單的置換密碼：柵欄技術明文

meetmeafterthetogaparty置換方法

mematrhtgpryetefeteoaat密文

mematrhtgpryetefeteoaat39置換密碼列置換換位密碼把明文按行寫入,按列讀出THISISAMESSAGETOSHOW明文：thisisamessagetoshow密文：tssohaasimghseeoistw40置換密碼帶密鑰的列置換換位密碼把明文按行寫入,按密鑰規(guī)定讀出字母的列順序THISISAMESSAGETOSHOW明文：thisisamessagetoshow密鑰：35214密文：IMGHISTWHAASTSSOSEEO

41傳統(tǒng)加密機制小結代替密碼和置換密碼對稱密碼的兩個基本運算代替和置換(Substitution&permutation)對稱密碼分析的兩個基本方法統(tǒng)計分析法、窮舉法多輪加密數(shù)據(jù)安全基于算法的保密42對稱密碼對稱密碼機制提供一個雙向信道：A和B共享一個秘密密鑰，雙方既能加密信息發(fā)送給對方，也可以解密從對方得到的密文信息。流密碼（streamcipher）分組密碼（blockcipher）43對稱密碼流密碼（streamcipher）每次加密數(shù)據(jù)流的一位或一個字節(jié)密鑰由密鑰序列發(fā)生器生成用于加密和解密的密鑰序列古典流密碼：Vigenere密碼和Vernam密碼44對稱密碼分組密碼將明文分成一段一段，將一段明文作為一個分組進行加密，每組分別在密鑰的控制下變換成等長的輸出密文序列。如：Wewillmeetthisafternoon.以5個字符為一組，則得到明文分組：wewillmeetthisafternoonxx，其中不夠一個分組的采用填充。45對稱密碼明文(p0,..,pn-1)解密加密密文(c1,…,cn-1)明文(p0,..,pn-1)密鑰(k0,..,km-1)密鑰(k0,..,km-1)分組密碼模型加密：C=(c0,…,cn-1)

=E((p0,…,pn-1),(k0,…,km-1)

)解密：P=(p0,…,pn-1)

=D((c0,…,cn-1),(k0,…,km-1))46對稱密碼混淆和擴散Shannon引見混淆和擴散兩個術語刻畫密碼系統(tǒng)的兩個部件。擴散：使明文的統(tǒng)計特征消散在密文中，可以讓每個明文字母盡可能的影響多個密文字母。即盡可能多的使明密文之間的統(tǒng)計關系變得復雜。混淆：盡可能使密文和加密密鑰間的統(tǒng)計關系復雜，以組織攻擊者發(fā)現(xiàn)密鑰。...Feistel密碼結構明文(2w位)FF密文(2w位)第1輪第n輪L0(w位)R0(w位)Ln-1(w位)Rn-1(w位)K1KnLn(w位)Rn(w位)Ln+1(w位)Rn+1(w位)...48對稱密碼Fesitel密碼結構的具體實現(xiàn)分組長度密鑰長度迭代輪數(shù)子密鑰產(chǎn)生算法輪函數(shù)快速加/解密簡化分析難度49對稱密碼——DES1973年5月15日,NBS公開征集標準加密算法,并公布了它的設計要求:算法必須提供高度的安全性算法必須有詳細的說明,并易于理解算法的安全性取決于密鑰,不依賴于算法算法適用于所有用戶算法適用于不同應用場合算法必須高效、經(jīng)濟算法必須能被證實有效算法必須是可出口的50對稱密碼——DES1974年8月27日,IBM提交了算法LUCIFER，該算法由IBM的工程師在1971~1972年研制1976年11月23日，采納為聯(lián)邦標準，批準用于非軍事場合的各種政府機構1977年1月15日,“數(shù)據(jù)加密標準”FIPSPUB46發(fā)布。FIPSPUB81（DES的工作方式）在1980年公布FIPSPUB74（實現(xiàn)和使用DES的指南）于1981年公布FIPSPUB112規(guī)定了DES用作口令加密的標準FIPSPUB113規(guī)定了DES如何用作計算機數(shù)據(jù)鑒別51對稱密碼——DESDES的應用1979年，美國銀行協(xié)會批準使用1980年，美國國家標準局（ANSI）贊同DES作為私人使用的標準,稱之為DEA（ANSIX.392）1983年，國際化標準組織ISO贊同DES作為國際標準，稱之為DEA-152對稱密碼——DESDES加密64位明文輸入56位密鑰輸入64位密文輸出初始置換第1輪第2輪第16輪32位互換逆初始置換置換選擇2置換選擇2置換選擇2置換選擇1循環(huán)左移循環(huán)左移循環(huán)左移64位明文64位密文K1K2K16DES加密算法的一般描述密鑰初始置換IP逆初始置換IP-1初始置換把明文的第58位換到第1位的位置，第50位換到第2位的位置,…是DES算法的最后一步，是一次簡單的數(shù)碼移位，也與密鑰無關。它是把乘積變換輸出的64位碼重新排列，其結果即為64位密文。Li-1(32位)Ri-1(32位)擴充置換運算(E)替換運算(S盒)置換運算(P)Li-1(32位)Ri-1(32位)48b子密鑰Ki(48b)32b32b48bDES的一輪迭代32481216202428123456789101112131415161718192021222324252627282930313259131721252911672021291228171152326518311028241432273919133062211425擴充置換運算E置換運算P57對稱密碼擴充置換的作用產(chǎn)生了與密鑰同長度的數(shù)據(jù)進行異或運算產(chǎn)生了更長的結果，使得在代替運算時能進行壓縮輸入的一位將影響兩個替換，所以輸出對輸入的依賴性將傳播得更快，明文或密鑰的一點小的變動應該使密文發(fā)生一個大的變化.這叫雪崩效應(avalancheeffect)。替換運算(S盒)：對每個盒，6比特輸入中的第1和第6比特組成的二進制數(shù)確定的行，中間4位二進制數(shù)用來確定的列，相應行、列位置的十進制數(shù)的4位二進制數(shù)表示作為輸出。DES的S-BoxDES的S-Box61子密鑰生成外部輸入的56位密鑰(64位中去掉8個校驗位，即第8，16，24，32，40，48，56，64位)通過置換和移位操作生成加密和解密需要的16個48位的子密鑰。 具體步驟如下圖。C0(28位)D0(28位)密鑰(64位)置換選擇1循環(huán)左移循環(huán)左移C1(28位)D1(28位)循環(huán)左移循環(huán)左移C16(28位)D16(28位)置換選擇2置換選擇2K1(48b)K16(48b)子密鑰的產(chǎn)生置換選擇1571101949582114150593334251602534435217263544918273663714215562613475461539465328313845202330371215222941417112415328156211019191242681672720132415231374755304051453348444939563453464250362932置換選擇2每輪的循環(huán)左移次數(shù)迭代輪數(shù)12345678910111213141516移位次數(shù)112222221222222165DES解密DES的解密算法與加密算法相同，解密密鑰也與加密密鑰相同。只是解密時逆向取用加密時用的密鑰順序。即：加密時第1-16輪回迭代使用的子密鑰順序是k1,…,k16

；而解密時使用的子密鑰順序是k16,…,k1

，產(chǎn)生子密鑰時的循環(huán)移位是向右的。66DES加密過程的數(shù)學模型

L0R0=IP(M64)(M64為64位輸入明文)Ki=ks(i,key)i=1,2,…,16

(ks表示密鑰運算函數(shù),產(chǎn)生48位的子密鑰)Li=Ri-1，Ri=Li-1

f(Ri-1,Ki)

?(Ri-1,Ki)中涉及到E變換、S盒代替、P盒變換和異或運算等步驟

C64=IP-1(L16,R16)67DES解密過程的數(shù)學模型

L16R16=IP(C64)Ki=ks(i,key)i=16,15,…,1Ri-1=

LiLi-1=Ri

?(Ri,Ki)M64=IP-1(L0,R0)68對稱密碼——DESDES算法特點只使用了標準的算術與邏輯運算解密算法與加密算法相同，只是子密鑰的使用次序相反適合軟硬件的實現(xiàn)69對稱密碼——DESDES的破譯1990年，以色列密碼學家EliBiham和AdiShamir提出了差分密碼分析法，可對DES進行選擇明文攻擊。線性密碼分析(1993)比差分密碼分析更有效

強力攻擊：平均255次嘗試差分密碼分析法線性密碼分析法70對稱密碼——3DES三重DES算法需要執(zhí)行三次DES的加密。一般三重DES算法使用兩個DES密鑰。其算法步驟為：發(fā)送端用密鑰K1進行DES加密；發(fā)送端用密鑰K2對上一結果進行DES解密；發(fā)送端用密鑰K1對上一結果進行DES加密；接收方則相應地使用K1解密，K2加密，再使用K1解密。71對稱密碼——3DESDESDES-1DESDES-1DESDES-1K1K2K3明文明文加密解密密文密文72國際數(shù)據(jù)加密算法(IDEA)IDEA是分組密碼算法，分組長度為64位，但密鑰長度128位。該算法是用128位密鑰對64位二進制碼組成的數(shù)據(jù)組進行加密的，也可用同樣的密鑰對64位密文進行解密變換。IDEA的密鑰比DES的多一倍，增加了破譯難度，被認為是多年后都有效的算法。73國際數(shù)據(jù)加密算法(IDEA)IDEA算法也是通過一系列的加密輪回操作的，每輪中也使用壓縮函數(shù)進行變換，只是不使用移位置換。IDEA中使用的運算有：異或模216加法模216+1乘法這三種運算彼此混合可產(chǎn)生很好的效果。運算時IDEA把數(shù)據(jù)分為四個子分組，每個16位74對稱密碼——AESAES產(chǎn)生的背景1997年4月15日，NIST發(fā)起征集高級加密標準（AdvancedEncryptionStandard）AES的活動，活動目的是確定一個非保密的、可以公開技術細節(jié)的、全球免費使用的分組密碼算法，作為新的數(shù)據(jù)加密標準。對AES的基本要求是：比三重DES快、至少與三重DES一樣安全；無類別的；可公開的；無特權的；數(shù)據(jù)分組長度為128比特；密鑰長度為128/192/256比特。75對稱密碼——AESAES產(chǎn)生的背景1998年8月12日，在首屆AES會議上指定了15個候選算法。1999年3月22日第二次AES會議上，將候選名單減少為5個，這5個算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年10月2日，NIST宣布了獲勝者—Rijndael算法，2001年11月出版了最終標準FIPSPUB197。76對稱密碼——AESAES使用的數(shù)學背景：近似代數(shù)不屬于Feistel結構加密、解密相似但不對稱支持128/32=Nb數(shù)據(jù)塊大小支持128/192/256(/32=Nk)密鑰長度結構簡單、速度快77DES和AES的比較DESAES日期1976年1999年分組大小64b128b密鑰長度56b(有效長度)128b、192b、256b(可能更長)加密原語替換、置換替換、移位、位混合算法公開公開設計基本原理未公開公開選擇過程保密保密，但接受公開評論來源IBM,由NSA加強比利時密碼學家78對稱密碼分組密碼的工作模式電碼本(ECB)密碼分組連接(CBC)密碼反饋(CFB)輸出反饋(OFB)計數(shù)器(CTR)79對稱密碼電碼本(ElectronicCodeBook)加密p1c1k解密c1p1k加密pncnk加密pncnk......80對稱密碼ECB方式的特點簡單和有效可以并行實現(xiàn)不能隱藏明文的模式信息相同明文得到的密文相同同樣信息多次出現(xiàn)造成泄漏對明文的主動攻擊是可能的信息塊可被替換、重排、刪除、重放誤差傳遞：密文塊損壞導致僅對應明文塊損壞適合于傳輸短信息密碼分組鏈接(CiphertextBlockChaining)加密p1c1k加密cnk...IV加密c2kp2...pncn-1解密p1c1k解密cnk...IV解密c2kp2...pncn-182對稱密碼CBC的特點能隱藏明文的模式信息相同明文得到的密文不同使用了初始化向量IV（可以用來改變第一塊）信息塊不容易被替換、重排、刪除、重放誤差傳遞：密文塊損壞導致兩明文塊損壞安全性高于ECB適合于傳輸長度大于64位的報文，可以進行用戶鑒別，是大多系統(tǒng)的標準如SSL、IPSec選擇

丟棄s位|64-s位密文反饋模式(CiphertextFeedbackBlock)加密c1(s位)kp1移位寄存器64-s位|s位64位64位IV參加下一分組加密計算加密選擇

丟棄s位|64-s位加密c2(s位)kp2移位寄存器64-s位|s位64位64位IVc1(s位)同時參加下一分組解密計算_密文反饋模式(CiphertextFeedbackBlock)解密p1k移位寄存器64-s位|s位64位64位IV選擇

丟棄s位|64-s位解密解密p2k移位寄存器64-s位|s位64位64位IV選擇

丟棄s位|64-s位c2(s位)85對稱密碼CFB的特點在分組密碼中使用流密碼的模式隱藏了明文模式需要共同的移位寄存器初始值IV對于不同的消息，IV必須唯一誤差傳遞：一個單元損壞影響多個單元

輸出反饋模式(OutputFeedbackBlock)加密c1(s位)kp1移位寄存器64-s位|s位64位64位IV參加下一分組加密計算選擇

丟棄s位|64-s位加密加密c2(s位)kp2移位寄存器64-s位|s位64位64位IV選擇

丟棄s位|64-s位輸出反饋模式(OutputFeedbackBlock)c1(s位)

_解密p1k移位寄存器64-s位|s位64位64位IV選擇

丟棄s位|64-s位同時參加下一分組解密計算解密c2(s位)

_解密p2k移位寄存器64-s位|s位64位64位選擇

丟棄s位|64-s位88對稱密碼OFB的特點利用流密碼的模式隱藏了明文模式需要共同的移位寄存器初始值IV誤差傳遞：一個單元損壞只影響對應單元對明文的主動攻擊是可能的信息塊可被替換、重放安全性較CFB差計數(shù)器模式(Counter)加密計數(shù)器cikpi解密計數(shù)器pikci90對稱密碼CTR的特點利用流密碼的模式可以并行實現(xiàn)、可以預處理、適用于高速網(wǎng)絡可以隨機訪問加密的數(shù)據(jù)分組隱藏了明文模式，與CBC模式一樣安全可以處理任意長度的消息誤差傳遞：一個單元損壞只影響對應單元對于每次加密，需要使用不同的密鑰的計數(shù)器值信息塊可被替換、重放91密碼技術對稱加密技術非對稱加密技術消息認證與HASH函數(shù)92對稱密碼的不足密鑰管理量的困難傳統(tǒng)密鑰管理：兩兩分別用一個密鑰時，則n個用戶需要C(n,2)=n(n-1)/2個密鑰，當用戶量增大時，密鑰空間急劇增大。密鑰必須通過某一信道協(xié)商，對這個信道的安全性的要求比正常的傳送消息的信道的安全性要高數(shù)字簽名的問題傳統(tǒng)加密算法無法實現(xiàn)抗抵賴的需求。93公鑰密碼的起源公鑰密碼又稱為雙鑰密碼和非對稱密碼1976年由Diffie和Hellman在其“密碼學新方向”一文中提出的

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654）Rivest,Shamir和Adleman在1978年提出RSA公鑰算法

CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-12694公鑰密碼的特點加密與解密的密鑰不同公鑰密碼的密鑰是一組密鑰對（公鑰,私鑰）可以公開的密鑰稱為公鑰，必須保密的密鑰稱為私鑰。知道密碼算法和公鑰，從公鑰得到私鑰在計算上是不可行的兩個密鑰配對使用公鑰加密信息，私鑰解密信息私鑰簽名信息，公鑰驗證簽名95公鑰密碼的加密明文明文HiBobAliceB的私鑰密文AliceBobA加密B解密HiBobAliceHiBobAliceHiBobAlice公開保密B的公鑰96公鑰密碼的簽名數(shù)字簽名類似于手寫簽名簽名后不能否認發(fā)生糾紛后，可以在第三方處進行仲裁。具有法律效應數(shù)字簽名數(shù)字簽名97公鑰密碼的簽名文件A簽名的文件HiBobAliceA的公鑰A的私鑰簽名文件AliceBobA簽名B驗證HiBobAlice保密公開HiBobAliceAliceHiBobAliceAlice98公鑰密碼的特點數(shù)字簽名可以有效的解決如下安全問題否認：發(fā)送者事后不承認自己發(fā)送過文件偽造：接收者偽造一份文件，聲稱它來自發(fā)送者冒充：網(wǎng)上的某個用戶冒充另一個用戶接收或發(fā)送信息篡改：接收者對收到的信息進行部分篡改

99公鑰密碼的安全性公鑰算法的條件：產(chǎn)生一對密鑰是計算可行的已知公鑰和明文，產(chǎn)生密文是計算可行的接收方利用私鑰解密密文是計算可行的對于攻擊者，利用公鑰來推斷私鑰是計算不可行的已知公鑰和密文，恢復明文是計算不可行的100單陷門函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：(1)給定x，計算y=fk(x)是容易的；(2)給定y,計算x使x=fk-1(y)是不可行的。(3)存在k，已知k時,對給定的任何y，若相應的x存在，則計算x使fk-1(y)是容易的。101公鑰密碼基于的數(shù)學難題背包問題大整數(shù)分解問題(TheIntegerFactorizationProblem)RSA體制離散對數(shù)問題有限域的乘法群上的離散對數(shù)問題(TheDiscreteLogarithmProblem)——ElGamal定義在有限域的橢圓曲線上的離散對數(shù)問題(TheEllipticCurveDiscreteLogarithmProblem)——ECDSA102數(shù)論基礎(1)模運算

a=qn+r;{0≤r<n,且q和n為整數(shù)}; 定義amodn為a除以n的余數(shù)； 例：11mod7=4，-11mod7=3；

若a=b+kn對某整數(shù)k成立

則a

b(modn) 稱b為a模n的余數(shù)，或a與b是模n的同余； 例：734mod23，21-9mod10；103數(shù)論基礎模運算操作[(amodn)+(bmodn)]modn

(a+b)modn;[(amodn)-(bmodn)]modn

(a-b)modn;[(amodn)×(bmodn)]modn

(a×b)modn;例：11mod8

3，15mod8

7；1.[(11mod8)+(15mod8)]mod8

10mod8

2(11+15)mod8

26mod8

2;2.[(11mod8)×(15mod8)]mod8

21mod8

5(11×15)mod8

165mod8

5;104數(shù)論基礎(2)素數(shù)一個只能被1和它本身整除的正整數(shù)。如以下各數(shù)為素數(shù)：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,…,2521,2365347734339,2756839-1等都是素數(shù)。105數(shù)論基礎(3)兩數(shù)互素兩個數(shù)的最大公因子為1，則兩數(shù)互素。gcd(a,n)=1,a和n互素例：15與28互素，13與500互素，而15與27不是互素；一個素數(shù)與它的倍數(shù)以外的任何其它數(shù)都是互素的。106數(shù)論基礎(4)因子分解對于一個數(shù)進行因子分解，就是找出其各個素數(shù)因子，如：15=3

5，80=2

2

2

2

5，252601=41

61

101等。在數(shù)論中，因子分解是一個古老的問題。分解一個數(shù)很簡單，但其過程很費時。107數(shù)論基礎目前最好的因子分解算法有:數(shù)域篩選法：對大于110位字長的數(shù)，數(shù)域篩選法是已知的最快的因子分解算法。二次篩選法：對于低于110位的十進制數(shù)，二次篩選法是已知的最快算法，且已得到廣泛應用。橢圓曲線法：該算法曾用于尋找43位長數(shù)字的因子，對于更大的數(shù)是無用的。108數(shù)論基礎(5)求模逆元在模運算領域，如果a×b

1(modn),就稱為a和b對于模n的乘法互為逆元。也可以寫作：b

a-1(modn)例如：5模14的逆元是3 5×31(mod14)

53-1(mod14)109數(shù)論基礎(6)費馬定理如果p是素數(shù)，a是不能被p整除的正整數(shù)，則：ap-11modp或

apamodp；例如：a=7，p=19；

72=4911mod19，741217mod19， 784911mod19，7161217mod19， ap-1=718=716×727×111mod19110數(shù)論基礎(7)歐拉函數(shù)Eular函數(shù)

(n)

：小于n且與n互素的正整數(shù)的個數(shù)。對素數(shù)p，

(p)＝p–1；假設n的素數(shù)因子為p和q，即n=pq，則(n)=

(pq)=

(p)×

(q)=(p-1)×(q-1);例如：

(21)=

(3)×

(7)=2×6=12111公鑰密碼的經(jīng)典算法Diffie-Hellman密鑰交換算法背包算法RSA算法EIGamal算法橢圓曲線密碼算法ECC112Diffie-Hellman密鑰交換算法第一個公鑰方案，Diffie&Hellman于1976年提出密鑰交換方案不能用于交換任意信息允許兩個用戶可以安全地建立一個秘密信息，用于后續(xù)的通訊過程該秘密信息僅為兩個參與者知道算法的安全性依賴于有限域上計算離散對數(shù)的難度在美國的專利1997年4月29日到期113Diffie-Hellman密鑰交換算法算法選擇可公開的系統(tǒng)參數(shù)：素數(shù)p以及p的一個原根

（素數(shù)p的原根定義：如果a是素數(shù)p的原根，則數(shù)

amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整數(shù)的某種排列。

）對于一個整數(shù)b和素數(shù)p的一個原根

，可找到惟一的指數(shù)i，使得：b=imodp，其中0≤i≤(p-1);

指數(shù)i稱為b的以

為基數(shù)的模p的離散對數(shù)或指數(shù)， 記為：ind

,p

(b)。

注：由已知的b、p和

，找出離散對數(shù)i是非常困難的。114Diffie-Hellman密鑰交換算法算法（續(xù)）用戶A:選擇一個隨機數(shù)Xa<p，計算Ya=

Xamodp用戶B:選擇一個隨機數(shù)Xb<p，計算Yb=

Xbmodp每一方保密X值，而將Y值交換給對方用戶A計算出K=YbXamodp用戶B計算出K=YaXbmodp雙方獲得一個共享密鑰：

XaXbmodp115對DH算法的中間人攻擊正常的DH交換Ya=

XamodpYb=

Xbmodp計算K=YbXamodp=

XbXa計算K=YaXbmodp=

XaXb116對DH算法的攻擊攻擊Ya=

XamodpYc=

XcmodpYb=

XbmodpYc=

Xcmodp計算K=YcXamodp=

XcXa計算K=YcXbmodp=

XcXb計算K=YbXcmodp=

XbXc計算K=YaXcmodp=

XaXc117RSA算法1977年由RonRivest、AdiShamir和LenAdleman發(fā)明，1978年公布是一種分組加密算法。明文和密文在0~n-1之間，n是一個正整數(shù)應用最廣泛的公鑰密碼算法在美國申請的專利已于2000年9月到期118RSA算法安全性基于大整數(shù)因子分解問題設n是一個大整數(shù)，有兩個素因子p和q容易：已知p和q

計算n=pq困難：已知n

對n進行因子分解，得到其素因子p和q119RSA算法RSA算法用到的元素： 兩個素數(shù)p和q(保密的，選定的)n=pq(公開的，計算得出的)e,gcd(

(n),e)=1;1<e<

(n)(公開的，選定的)

其中

(n)是Euler函數(shù)，即小于n的且與n互素的正整數(shù)的個數(shù)。對于素數(shù)p和q，有

(pq)=(p-1)(q-1)d

e-1mod

(n)(保密的，計算得出的)120RSA算法密鑰生成選擇p和q(都是素數(shù)，且pq)計算n=pq，計算

(n)=(p-1)(q-1)選擇整數(shù)e,{gcd(

(n),e)=1;1<e<

(n)}計算d：d

e-1mod

(n)計算公鑰KU={e,n}，私鑰KV={d,n}加密對于明文M<n，密文C=Me(modn)解密對密文C的解密：P=Cd(modn)121RSA算法RSA算法的加密密鑰Ke是公開的，而解密密鑰Kd是保密的。假設用戶A要對發(fā)送給B的數(shù)據(jù)加密，則可根據(jù)以下步驟選擇密鑰和進行密碼變換：122RSA算法(1)隨機地選取兩個不同的大素數(shù)p和q(一般為100位以上的十進制數(shù))予以保密；(2)計算n=p·q，作為A的公開模數(shù)；(3)計算Euler函數(shù)

(n)=(p-1)·(q-1)(4)隨機地選取一個與(p-1)·(q-1)互素的整數(shù)e，作為A的公開密鑰；123RSA算法(5)用歐幾里德算法，計算滿足同余方程

e·d

1(mod

(n))

的解d，作為A的保密密鑰；(6)任何向A發(fā)送明文的用戶，均可用A的公開密鑰e和公開模數(shù)n，根據(jù)式

C=Me

(modn)

得到密文C124RSA算法(7)用戶A收到密文C后，可利用自己的保密密鑰d，根據(jù)

M=Cd(modn)

得到明文M。125RSA算法舉例對消息“HI”進行加密：(1)選密鑰

設p=5,q=11，則n=p·q=55,

(n)=40,

取與

(n)互素的數(shù)e=3,(公鑰)

求e模

(n)的逆元d,則d=27(mod40),(私鑰)3·271(mod40)126RSA算法舉例(2)加密設明文編碼為：空格=00,A=01,B=02,…I=09,…,Z=26則明文HI=0809C1=(08)3=512

17(mod55)C2=(09)3=729

14(mod55)N=14,Q=17所以，密文為QN127RSA算法舉例(3)恢復明文M1=Cd=(17)27

08(mod55)M2=Cd=(14)27

09(mod55)因此明文為“HI”。128RSA的安全性RSA的安全性依賴于分解大整數(shù)的難度1999.8.22，荷蘭H.Riele領導的來自6個國家的研究人員組成的團隊找到了一個512-bitRSA密鑰的一個素因子。存在專門針對RSA的攻擊，這些攻擊不攻擊基本的算法，而是攻擊協(xié)議129DES和RSA算法的特點和比較(1)DES的特點可靠性較高(16輪變化，增大了混淆性和擴散性，輸出不殘存統(tǒng)計信息)；加密/解密速度快；算法容易實現(xiàn)(可由軟件和硬件實現(xiàn)，硬件實現(xiàn)速度快)，通用性強；算法具有對稱性，密鑰位數(shù)少，存在弱密鑰和半弱密鑰，便于窮盡攻擊；密鑰管理復雜。130DES和RSA算法的特點和比較(2)RSA算法的特點密鑰管理簡單(網(wǎng)上每個用戶僅保密一個密鑰，且不需密鑰配送)；便于數(shù)字簽名；可靠性較高(取決于分解大素數(shù)的難易程度)；算法復雜，加密/解密速度慢,難于實現(xiàn)。131混合加密方法

對稱密鑰密碼算法的特點是算法簡單，加/解密運算速度快；但其密鑰管理復雜，不便于數(shù)字簽名。而公開密鑰密碼算法的特點是密鑰管理簡單，便于數(shù)字簽名；但算法的理論復雜，加/解密運算速度慢。兩者的優(yōu)缺點互補。132在實際應用中，公開密鑰密碼系統(tǒng)并沒有完全取代對稱密鑰密碼系統(tǒng)。而是采用對稱密鑰加密方法與公