第三章 數(shù)據(jù)加密技術(shù)

第三章數(shù)據(jù)加密技術(shù)學習內(nèi)容要求數(shù)據(jù)加密技術(shù)基本概念密碼算法概述DES算法RSA算法1數(shù)據(jù)加密技術(shù)基本概念1.1密碼學密碼編碼學密碼編碼學密碼分析學密碼體制的設(shè)計密碼體制的破譯密碼學密碼學的主要作用提供機密性鑒別:消息的接收者應該能夠確認消息的來源；入侵者不可能偽裝成他人。完整性:消息的接收者應該能夠驗證在傳送過程中消息沒有被修改；入侵者不可能用假消息代替合法消息?？沟仲?消息的發(fā)送者事后不可能虛假地否認他發(fā)送的消息。1.2密碼學專業(yè)術(shù)語明文信息的原始形式稱為明文（plaintext）。明文用M或P表示。明文的形式可能是：位序列、文本文件、位圖、數(shù)字化語音序列、數(shù)字化視頻圖像等、對于計算機，明文指二進制數(shù)據(jù)。密文明文經(jīng)過加密變換后的形式稱為密文（ciphertext）。密文用C表示。對于計算機，密文是二進制數(shù)據(jù)。加密由明文變成密文的過程稱為加密(enciphering)。通常記作E。加密函數(shù)E作用于M得到密文C?？捎脭?shù)學公式表示：E(M)=C解密由密文變成明文的過程稱為解密(deciphering)。通常記作D。解密函數(shù)D作用于C得到明文M。可用數(shù)學公式表示：D(C)=M加密和解密的過程可以表示為：加密加密解密明文密文原始明文先加密再解密，原始明文將恢復。故等式D(E(M))=M必須成立算法算法是用于加密和解密的數(shù)學函數(shù)。如果算法的保密性是基于保持算法的秘密，這種算法稱為受限制的算法。受限制的算法流行于低密級的應用。密鑰密鑰是參與加密或解密變換的參數(shù)(key)。通常用K表示。通過引入密鑰，算法的安全性依賴于密鑰的安全性，而不是算法細節(jié)的安全性。密鑰的引入使得算法可以公開，或被分析，并使大量生產(chǎn)使用某一算法的產(chǎn)品成為可能。引入密鑰后，加密和解密的過程可以表示為：加密加密解密明文密文原始明文加密密鑰解密密鑰加密函數(shù)為：加密函數(shù)為：DK2(EK1(M))=M并滿足：EK1(M)=C解密函數(shù)為：DK2(C)=M密碼體制通常一個完整的密碼體制包括如下五個要素:M可能明文的有限集，稱為明文空間。C可能密文的有限集，稱為密文空間。K一切可能密鑰的有限集，稱為密鑰空間。E加密函數(shù)D解密函數(shù)對于密鑰空間的任一密鑰，有一個加密算法和相應的解密算法，使得加密函數(shù)EK:M->C和解密函數(shù)DK:C->M滿足：DK(EK(x))=x,這里x€M1.3密碼學的發(fā)展第一階段：傳統(tǒng)密碼學主要加密對象是文字書信第二階段：計算機密碼學主要加密對象是二進制數(shù)據(jù)2密碼算法概述2.1經(jīng)典密碼算法2.1.1代替密碼代替密碼就是明文中每一個字符被替換成密文中的另外一個字符。接收者對密文進行逆替換就恢復明文。簡單代替密碼多名碼代替密碼多字母代替密碼多表代替密碼簡單代替密碼明文的一個字符用相應的一個密文字符代替。例：凱撒（Caser）密碼將每一個明文字符用它右邊的第3個字母代替。簡單代替密碼由于使用從明文到密文的單一映射，所以明文字母的單字母出現(xiàn)頻率與密文中相同。多名碼代替密碼多名碼代替密碼單個字符明文可以映射成密文的幾個字符之一。多字母代替密碼字符塊被成組加密。多表代替密碼由多個簡單的代替密碼構(gòu)成。它有多個單字母密鑰，每一個密鑰被用來加密一個明文字母。2.1.2換位密碼在換位密碼中，明文的字母保持相同，但順序被打亂。列換位法矩陣換位法簡單的縱行換位密碼示例：明文:COMPUTERGRAPHICSMAYBESLOWBUTATLEASTEXPENSIVE將明文以固定寬度水平寫在圖表紙上：COMPUTERGRAPHICSMAYBESLOWBUTATLEASTEXPENSIVE密文按垂直方向讀出：CAELSOPSEIMHLAVPIOSEUCWTTSBEEMUXRATPGYAERBTN2.1.3一次一密亂碼本一次一密亂碼本是一個大的不重復的真隨機密鑰字母集，這個密鑰字母集被寫在幾張紙上，并被粘成一個亂碼本。發(fā)送者用亂碼本中的每一密鑰字母加密一個明文字符。加密使用明文字符和一次一密亂碼本密鑰字符的模26加法。若明文：ONETIMEPAD亂碼本的密鑰序列是：TBFRGFARFM由：(O+T)mod26=I(N+B)mod26=P(E+F)mod26=K…則密文是：IPKLPSFHGQ一次一密密碼體制的特點：￠每個密鑰僅對一個消息使用一次￠密鑰以隨機方式產(chǎn)生?！槊荑€長度等于明文長度?！榘l(fā)送者和接收者必須完全同步?！槭俏ㄒ贿_到理論不可破譯的密碼體制。對稱算法又叫：在大多數(shù)對稱算法中，加密密鑰和解密密鑰是相同的。對稱算法又叫：在大多數(shù)對稱算法中，加密密鑰和解密密鑰是相同的。對稱算法中，加密密鑰能夠從解密密鑰中推算出來，反之也成立。2.2對稱算法（symmetricalgorithm）傳統(tǒng)密碼算法秘密密鑰算法單密鑰算法對稱算法的安全性依賴于密鑰。對稱算法的加密和解密可表示為：EK(M)=CDK(C)=M使用對稱密碼系統(tǒng)通信的過程可以描述如下：1）Alice和Bob協(xié)商用同一密碼系統(tǒng)。2）Alice和Bob協(xié)商用同一密鑰。3）Alice用加密算法和選取的密鑰加密明文，得到密文。4）Alice發(fā)送密文給Bob。5）Bob用同樣的算法和密鑰解密密文，然后讀出明文。對稱密碼算法存在的缺點：1）通信雙方事先必須約定密鑰。2）密鑰必須秘密分配。3）如果密鑰泄密，攻擊者可以冒充協(xié)議發(fā)送方，產(chǎn)生虛假加密消息。4）對于一個完備的通信網(wǎng)，需要的密鑰數(shù)量非常大。3）不具備數(shù)字簽名功能，不能保證消息的完整性和不可否認性。2.32.3公開密鑰算法（public-keyalgorithm）公開密鑰算法中，加密密鑰不同于解密密鑰，并且解密密鑰不能根據(jù)加密密鑰計算出來。在公開密鑰算法中，加密密鑰可以公開，即陌生者可以用加密密鑰加密信息，但只有用相應的解密密鑰才能解密信息。加密密鑰叫公開密鑰（public-key，簡稱公鑰）解密密鑰叫私人密鑰（private-key，簡稱私鑰）相應的加密過程可表示為：EK(M)=C用相應的私鑰解密過程可表示為：DK(C)=M公開密鑰算法廣泛用于數(shù)字簽名。在數(shù)字簽名中，用私鑰加密，而用公鑰解密。公開密鑰算法也叫非對稱算法。使用公開密碼系統(tǒng)通信的過程可以描述如下：1）Alice和Bob選用一個公開密碼系統(tǒng)。2）Bob將他的公開密鑰傳送給Alice。3）Alice用Bob的公開密鑰加密她的消息，然后傳送給Bob。4）Bob用他的私人密鑰解密Alice的密文。公開密碼體制具有如下優(yōu)點：1）密鑰分發(fā)簡單。2）秘密保存的密鑰量減少3）在互不信任的通信雙方之間，可以相互驗證對方身份。4）可以實現(xiàn)數(shù)字簽名。2.4混合密碼系統(tǒng)混合密碼系統(tǒng)中，公開密鑰密碼用來保護和分發(fā)密鑰。這些會話密鑰用在對稱算法中，對通信消息進行保密。使用混合密碼系統(tǒng)的優(yōu)勢：1）把公開密鑰密碼用于密鑰分2）公開密鑰算法比對稱算法慢。配解決了對稱密碼系統(tǒng)的密鑰管理問題。使用混合密碼系統(tǒng)進行加密通信的過程如下：1）Bob將他的公開密鑰發(fā)給A2）Alice產(chǎn)生隨機會話密鑰K，用Bob的公開密鑰加密，并把加密的密鑰EB（K）送給Bob。lice。3）Bob用他的私人密鑰解密Alice的消息，恢復出會話密鑰：EB（EB（K））=K。4）雙方用同一會話密鑰對他們的消息進行加密。密碼分析學是在不知道密碼的情況下，恢復出明文的科學。分組密碼將明文分成固定長度的組，用同一密鑰和算法對每一塊加密。密碼分析學是在不知道密碼的情況下，恢復出明文的科學。分組密碼將明文分成固定長度的組，用同一密鑰和算法對每一塊加密?，F(xiàn)代計算機密碼算法的典型分組長度為64位。序列密碼每次加密一位或一字節(jié)的明文，也可稱為流密碼。2.5加密模式對稱算法有兩種加密模式：序列密碼分組密碼2.6算法的安全性2.6.1密碼分析密碼分析的一個基本假設(shè)：秘密必須全寓于密鑰中。即密碼分析者了解加密算法的全部知識。對密碼進行分析的嘗試稱為攻擊。常用的密碼分析攻擊：1）唯密文攻擊（ciphertext-onlyattack）密碼分析者有一些消息的密文，這些消息都用同一加密算法加密。密碼分析者的任務是：恢復盡可能多的明文，或能夠推算出加密消息的密鑰，以便可采用相同的密鑰解出其他被加密的消息。已知：C1=EK(P1),C2=EK(P2),…,Ci=EK(Pi)推導出：P1，P2,…,Pi；或者K2）已知明文攻擊（known-plaintextattack）密碼分析者不僅有一些消息的密文，而且也知道這些消息的明文。密碼分析者的任務是：用加密信息推算出加密消息的密鑰，或?qū)С鲆粋€算法，此算法可以對用同一密鑰加密的任何新的消息進行解密。已知：P1,C1=EK(P1),P2,C2=EK(P2),…,Pi,Ci=EK(Pi)推導出：密鑰K；或者從Ci+1=EK(Pi+1)推導出Pi+1的算法。3）選擇明文攻擊（chose-plaintextattack）密碼分析者不僅有一些消息的密文和明文，而且也可選擇被加密的明文。密碼分析者的任務是：推出加密消息的密鑰，或?qū)С鲆粋€算法，此算法可以對用同一密鑰加密的任何新的消息進行解密。已知：P1,C1=EK(P1),P2,C2=EK(P2),…,Pi,Ci=EK(Pi)，其中P1，P2,…,Pi可以由密碼分析者選擇。推導出：密鑰K；或者從Ci+1=EK(Pi+1)推導出Pi+1的算法。選擇明文攻擊比已知明文攻擊更有效。因為密碼分析者能夠選擇特定的明文塊加密，那些塊可能產(chǎn)生更多的關(guān)于密鑰的信息。4）自適應選擇明文攻擊（adaptive-chosen-plaintextattack）密碼分析者不僅能選擇被加密的明文，而且也能基于以前加密的結(jié)果修正這個選擇。自適應選擇明文攻擊是選擇明文攻擊的特殊情況。在自適應選擇明文攻擊中，密碼分析者可以選取較小的明文塊，然后再基于第一塊的結(jié)果選擇另一明文塊。而在選擇明文攻擊中，密碼分析者可以選取一大塊被加密的明文。5）選擇密文攻擊（chosen-ciphertextattack）密碼分析者可選擇不同的被加密的密文，并可得到對應的解密的明文。密碼分析者的任務是：推出加密消息的密鑰。已知：C1,P1=DK(C1),C2,P2=DK(C2),…,Ci,Pi=DK(Ci)，推導出：密鑰K選擇密文攻擊主要用于公開密鑰算法。6）軟磨硬泡攻擊（rubber-keyattack）密碼分析者通過威脅等手段，迫使密碼知情人給出密鑰。6）軟磨硬泡攻擊（rubber-keyattack）密碼分析者通過威脅等手段，迫使密碼知情人給出密鑰。2.6.2算法的安全性根據(jù)被破譯的難易程度，不同的密碼算法具有不同的安全等級。（1）全部破譯（totalattack）。密碼分析者找出密鑰K，這樣DK（C）=P。（2）全盤推導（globaldeduction）。密碼分析者找到一個代替算法A，在不知道密鑰K的情況下，等價于DK（C）=P。（3）實例（或局部）推導（instance(orlocal)deduction）。密碼分析者從截獲的密文中找出明文。（4）信息推導（informationdeduction）。密碼分析者獲得一些有關(guān)密鑰或明文的信息。這些信息可能是密鑰的幾個位，有關(guān)明文格式的信息等。如果不論密碼分析者有多少密文，都沒有足夠的信息恢復出明文，那么這個算法就是無條件保密的。只有一次一密亂碼本才是不可破的?！樾U力攻擊：只要簡單地一個接一個地去試每種可能的密鑰，并且檢查所的明文是否有意義，就可破譯除一次一密亂碼本以外的所有其他密碼系統(tǒng)。所有其他密碼系統(tǒng)在唯密文攻擊中都是可破的密碼學更關(guān)心在計算上不可破譯的密碼系統(tǒng)。如果一個算法用可得到的資源都不能破譯，這個算法則被認為在計算上是安全的?？捎觅Y源就是公開數(shù)據(jù)的分析整理?？捎貌煌绞胶饬抗舴椒ǖ膹碗s性：1）數(shù)據(jù)復雜性：用作攻擊輸入所需的數(shù)據(jù)量。2）處理復雜性：完成攻擊所需要的時間。3）存儲需求：進行攻擊所需要的存儲量。攻擊的復雜性取三個因數(shù)的最小值。一個算法的復雜性即運行它所需的計算能力。復雜性用數(shù)量級表示。如果算法的處理復雜性是2128，那么破譯這個算法需要2128次運算。假設(shè)有足夠的計算速度完成每秒鐘100萬次運算，并且用100萬個并行處理器完成這個任務，仍需花費1019年（宇宙年齡的10億倍）以上才能找出密鑰。當攻擊的復雜性是常數(shù)時，則破譯算法的難度只取決于計算能力。DES算法數(shù)據(jù)加密標準DES，DataEncryptionStandardDES背景3.1.1標準的開發(fā)1972年美國國家標準局（NBS）擬訂了一個旨在保護計算機和通信數(shù)據(jù)的計劃。開發(fā)一個單獨的標準密碼算法是該計劃的一部分。1973年5月15日美國國家標準局（NBS）發(fā)布征集標準密碼算法公告。NBS確定了一系列設(shè)計準則：￠算法必須提供較高的安全性。￠算法必須完全確定且易于理解?！樗惴ǖ陌踩员仨氁蕾囉诿荑€，而不應依賴于算法。￠算法必須對所有的用戶都有效?！樗惴ū仨氝m用于各種應用?！橛靡詫崿F(xiàn)算法的電子器件必須很經(jīng)濟?！樗惴ū仨毮苡行褂??！樗惴ū仨毮茯炞C?！樗惴ū仨毮艹隹?。1974年8月27日美國國家標準局（NBS）第二次發(fā)布征集標準密碼算法公告。采納候選算法，由IBM公司1970年初開發(fā)的一個算法基礎(chǔ)上發(fā)展而成。1975年NBS公布該算法細節(jié)。1976年NBS成立專題小組評估提出的整個標準。1976年11月23日采納IBM公司的設(shè)計方案為聯(lián)邦標準，并授權(quán)在非密級的政府通信中使用。1977年1月15日FIPSPUB46（DES標準的正式文本）公布，并在六個月后生效。1980年FIPSPUB81（DES工作方式）公布。1981年公布FIPSPUB74（實現(xiàn)和使用DES的指南）DES算法是第一個公布的NSA（美國國家安全局）執(zhí)行算法。3.1.2標準的采用1981年美國國家標準研究所（ANSI）批準DES為私營部門的標準，并將其稱為DEA。1987年國際標準化組織（ISO）下屬國際銷售金融標準組在國際認證標準中使用DES。其它美國財政部制訂政策，要求所有電子資金轉(zhuǎn)賬電文使用DES鑒別。美國總務署負責制訂聯(lián)邦電信標準期間，發(fā)布了三個基于DES的標準。3.2DES算法描述1）分組加密算法：以64位為分組。64位一組的明文從算法一端輸入，64位密文從另一端輸出。2）對稱算法：加密和解密用同一密鑰。3）有效密鑰長度為56位。密鑰通常表示為64位數(shù)，但每個第8位用作奇偶校驗，可以忽略。4）代替和置換DES算法只是兩種加密技術(shù)的組合：混亂和擴散。先代替后置換。5）易于實現(xiàn)DES算法只是使用了標準的算術(shù)和邏輯運算，其作用的數(shù)最多也只有64位，因此用70年代末期的硬件技術(shù)很容易實現(xiàn)。算法的重復特性使得它可以非常理想地用在一個專用芯片中。DES算法的總體過程：在初始置換IP后，明文組被分為左右兩部分，每部分32位，以L0，R0表示。經(jīng)過16輪運算（|），將數(shù)據(jù)和密鑰結(jié)合。16輪后，左、右兩部分連接在一起。經(jīng)過末置換（初始置換的逆置換）。算法完成。64位明文初始置換64位明文初始置換IP+k1+k2+k16IP-1L0R0L1=R0R1=L0(RO,K1)L2=R1R2=L1(R1,K2L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位密文3.2.13.2.1初始置換初始置換在第一輪運算之前進行。對輸入分組實施如表3-1所示的變換。表3-1初始置換58，50，42，34，26，18，10，2，60，52，44，36，28，20，12，4，62，54，46，38，30，22，14，6，64，56，48，40，32，24，16，8，57，49，41，33，25，17，9，1，59，51，43，35，27，19，11，3，61，53，45，37，29，21，13，5，63，55，47，39，31，23，15，7表3-1應從左向右，從上向下讀。例如，初始置換將明文的第58位換到第1位第50位換到第2位第42位換到第3位初始置換和對應的末置換并不影響DES的安全性。其主要目的是為了更容易地將明文和密文數(shù)據(jù)以字節(jié)大小放入DES芯片中。由于這種位方式的置換用軟件實現(xiàn)很困難，很多DES的軟件實現(xiàn)方式刪去了初始置換和末置換。這些新的算法安全性不比DES差，但并未遵循DES標準，故而不應叫做DES。3.2.23.2.2迭代過程經(jīng)過初始置換后，進行16輪完全相同的運算。這些運算被稱為，在運算過程中數(shù)據(jù)與密鑰結(jié)合。+k1L0R0L1=R0R1=L0(RO,K1)函數(shù)的輸出經(jīng)過一個異或運算，和左半部分結(jié)合，其結(jié)果成為新的右半部分，原來的右半部分成為新的左半部分。假設(shè)Li和Ri是第i次迭代結(jié)果的左半部分和右半部分，Ki是第i輪的48位密鑰，則每一輪迭代過程可以表示為：KiKi48bitLi-1(32bit)Ri-1(32bit)擴展置換ES盒代替P-盒置換Ri(32bit)Li(32bit)Ri=Li-1(Ri-1,Ki-1)Li=Ri-132位48位48位32位32位32位函數(shù)|由四步運算構(gòu)成：￠密鑰置換