第四講常規(guī)加密的現(xiàn)代技術(shù)

第四講常規(guī)加密的現(xiàn)代技術(shù)第一頁，共八十三頁，編輯于2023年，星期一第四講-常規(guī)加密的現(xiàn)代技術(shù)分組密碼原理S-DES加密算法Feistel網(wǎng)絡(luò)結(jié)構(gòu)DES的產(chǎn)生和應(yīng)用DES的算法結(jié)構(gòu)分組密碼的操作方式第二頁，共八十三頁，編輯于2023年，星期一分組密碼原理分組密碼是將明文消息編碼表示后的數(shù)字（簡稱明文數(shù)字）序列，劃分成長度為n的組（可看成長度為n的矢量），每組分別在密鑰的控制下變換成等長的輸出數(shù)字（簡稱密文數(shù)字）序列。第三頁，共八十三頁，編輯于2023年，星期一分組密碼原理分組密碼中密文輸出中每一位數(shù)字都與該數(shù)字所在組塊的n位明文數(shù)字有關(guān)，密鑰不變時，分組密碼對長度為n的明文所實施的變換是一樣的，分組密碼本質(zhì)上是長度為n的數(shù)字序列的變換問題第四頁，共八十三頁，編輯于2023年，星期一抵御統(tǒng)計分析密碼系統(tǒng)統(tǒng)計分析：在已知明文信息的某些統(tǒng)計特征的前提下，分析這些統(tǒng)計特征在密文中的反映，從而推測或推導(dǎo)可能的密鑰或包含密鑰的可能子集。信息論創(chuàng)始人Shannon提出為了抵御對密碼系統(tǒng)的統(tǒng)計分析，設(shè)計密碼系統(tǒng)的基本方法是擴散和擾亂。第五頁，共八十三頁，編輯于2023年，星期一密碼系統(tǒng)基本設(shè)計原理擴散（Diffusion):將明文的統(tǒng)計特征擴散到密文中,使得明文和密文之間的統(tǒng)計關(guān)系盡量復(fù)雜方法：使明文中的每一位數(shù)字影響密文中多位的值，或者說使密文中的一位依賴于明文中的多位數(shù)字例：對英文消息M=c1c2…cn…中字符Cn的加密操作：第六頁，共八十三頁，編輯于2023年，星期一密碼系統(tǒng)基本設(shè)計原理擾亂(confusion)：使得密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡量復(fù)雜方法：替換，線性變換無法起到有效的擾亂效果第七頁，共八十三頁，編輯于2023年，星期一現(xiàn)代分組密碼設(shè)計原則分組長度足夠大：使得分組替換字母表中的元素個數(shù)2n足夠大，可有效的防止對明文實施窮舉攻擊。密鑰空間要足夠大,盡可能消除弱密鑰并且使所有密鑰的加密強度相同。保證足夠強的密碼算法復(fù)雜度，充分實現(xiàn)明文于密文的擴散和擾亂，能夠抗擊各種密碼分析攻擊第八頁，共八十三頁，編輯于2023年，星期一現(xiàn)代分組密碼設(shè)計原則加解密運算簡單,盡量采用子塊和簡單運算：子塊的長度適應(yīng)軟件編程要求，通常長度取2的冪，密碼運算盡量采用簡單運算，如加法、與、或、異或、移位等。硬件實現(xiàn):最好加密與解密具有相似性，以便采用同樣的器件來實現(xiàn)加密和解密，節(jié)省費用和體積。盡量采用標(biāo)準(zhǔn)的組件結(jié)構(gòu)，以便能適應(yīng)于在超大規(guī)模集成電路中實現(xiàn)第九頁，共八十三頁，編輯于2023年，星期一DES加密算法的背景發(fā)明人：美國IBM公司W(wǎng).Tuchman和C.Meyer1971-1972年研制成功?；A(chǔ)：1967年美國HorstFeistel提出的理論產(chǎn)生：美國國家標(biāo)準(zhǔn)局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經(jīng)評選從一大批算法中采納了IBM的LUCIFER方案。標(biāo)準(zhǔn)化：DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標(biāo)準(zhǔn)局頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)（DataEncryptionStandard），于1977年7月15日生效第十頁，共八十三頁，編輯于2023年，星期一DES加密算法的背景美國國家安全局（NSA,NationalSecurityAgency)參與了美國國家標(biāo)準(zhǔn)局制定數(shù)據(jù)加密標(biāo)準(zhǔn)的過程。NBS接受了NSA的某些建議，對算法做了修改，并將密鑰長度從LUCIFER方案中的112位壓縮到56位。1979年，美國銀行協(xié)會批準(zhǔn)使用DES。1980年，DES成為美國標(biāo)準(zhǔn)化協(xié)會(ANSI)標(biāo)準(zhǔn)。1984年2月，ISO成立的數(shù)據(jù)加密技術(shù)委員會(SC20)在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標(biāo)準(zhǔn)工作。第十一頁，共八十三頁，編輯于2023年，星期一DES的產(chǎn)生1973年5月15日,NBS開始公開征集標(biāo)準(zhǔn)加密算法,并公布了它的設(shè)計要求:(1)算法必須提供高度的安全性(2)算法必須有詳細(xì)的說明,并易于理解(3)算法的安全性取決于密鑰,不依賴于算法(4)算法適用于所有用戶(5)算法適用于不同應(yīng)用場合(6)算法必須高效、經(jīng)濟(7)算法必須能被證實有效(8)算法必須是可出口的第十二頁，共八十三頁，編輯于2023年，星期一DES的產(chǎn)生1974年8月27日,NBS開始第二次征集,IBM提交了算法LUCIFER，該算法由IBM的工程師在1971~1972年研制1975年3月17日,NBS公開了全部細(xì)節(jié)1976年,NBS指派了兩個小組進(jìn)行評價1976年11月23日，采納為聯(lián)邦標(biāo)準(zhǔn)，批準(zhǔn)用于美國政府的非密級政府通信1977年1月15日,“數(shù)據(jù)加密標(biāo)準(zhǔn)”FIPSPUB46發(fā)布第十三頁，共八十三頁，編輯于2023年，星期一DES的應(yīng)用1979年，美國銀行協(xié)會批準(zhǔn)使用1980年，美國國家標(biāo)準(zhǔn)局（ANSI）贊同DES作為私人使用的標(biāo)準(zhǔn),稱之為DEA（ANSIX.392）

1983年，國際化標(biāo)準(zhǔn)組織ISO贊同DES作為國際標(biāo)準(zhǔn)，稱之為DEA-1該標(biāo)準(zhǔn)規(guī)定每五年審查一次，計劃十年后采用新標(biāo)準(zhǔn)最近的一次評估是在1994年1月，已決定1998年12月以后，DES將不再作為聯(lián)邦加密標(biāo)準(zhǔn)。第十四頁，共八十三頁，編輯于2023年，星期一DES的應(yīng)用1997年一個研究小組進(jìn)過4個月努力，在Internet上搜索了3x1016個密鑰，找到了DES的密鑰1998年5月美國研究機構(gòu)ETF用一臺價值20萬美元的計算機改裝的專用解密系統(tǒng)，花費56小時破譯了56位密鑰的DES2000年10月，美國國家標(biāo)準(zhǔn)局公布了新的AES，DES作為標(biāo)準(zhǔn)正式結(jié)束。第十五頁，共八十三頁，編輯于2023年，星期一S-DES加密算法S-DES：1)用于教學(xué)目的的簡化的DES加密算法2)以10位密鑰和8位明文分組作為輸入，產(chǎn)生8位密文分組輸出。3)解密使用相同密鑰第十六頁，共八十三頁，編輯于2023年，星期一S-DES加密算法加密步驟：1)對輸入的8位明文分組m執(zhí)行初始置換IP(m)2)執(zhí)行一個包含替換、置換操作且依賴于密鑰的變換fk3)將數(shù)據(jù)進(jìn)行左右4位兩半部分交換操作SW4)再執(zhí)行一次fk5)執(zhí)行逆置換IP-1產(chǎn)生密文輸出第十七頁，共八十三頁，編輯于2023年，星期一S-DES加密算法第十八頁，共八十三頁，編輯于2023年，星期一

S-DES的密鑰生成第十九頁，共八十三頁，編輯于2023年，星期一S-DES的密鑰生成P10:10階置換,定義為

設(shè)10bit的密鑰為k=(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)P10(k)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)LS為循環(huán)左移:LS-1循環(huán)左移1位,LS-2循環(huán)左移2位P8:10位轉(zhuǎn)8位變換

P8=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K10)=(K6,K3,K7,K4,K8,K5,K10,K9)第二十頁，共八十三頁，編輯于2023年，星期一S-DES的密鑰生成例：若K選為(1010000010),產(chǎn)生的兩個子密鑰分別為

K1=(10100100)K2=(01000011)1)進(jìn)行P10置換,m1=P10(1010000010)=(1000001100)2)循環(huán)左移m2=LS-1(m1L)||LS-1(m1R)==LS-1(10000)||LS-1(01100)=(0000111000)第二十一頁，共八十三頁，編輯于2023年，星期一S-DES的密鑰生成3)P8變換K1=P8(0000111000)=(10100100)4)循環(huán)左移m3=LS-2(m2L)||LS-2(m2R)=LS-2(00001)||LS-2(11000)=(0010000011)5)P8變換K2=P8(0010000011)=(01000011)第二十二頁，共八十三頁，編輯于2023年，星期一S-DES的加密運算初始置換用IP函數(shù):末端置換為IP的逆置換:易見IP-1(IP(X))=X第二十三頁，共八十三頁，編輯于2023年，星期一第二十四頁，共八十三頁，編輯于2023年，星期一S-DES的加密運算E/P變換：一個4位到8位的擴展變換，將輸入字節(jié)的右半4位擴展為8位E/P(b1,b2,b3,b4)=(b4,b1,b2,b3,b2,b3,b4,b1,):按位異或運算S0,S1:4位到2位的變換盒,S0作用于E/P變換輸出的左4位，S1作用于右4位輸出為Sij,i由4位輸入的0,3位確定,j由4位輸入的1，2位確定第二十五頁，共八十三頁，編輯于2023年，星期一S-DES的加密運算例：S0(1110)=S23=3=(11)P4:4位置換P4(b1,b2,b3,b4)=(b2,b4,b3,b1)第二十六頁，共八十三頁，編輯于2023年，星期一Feistel密碼結(jié)構(gòu)思想基本思想：用簡單算法的乘積來近似表達(dá)大尺寸的替換變換多個簡單算法的結(jié)合得到的加密算法比任何一個部分算法都要強交替使用替換和置換應(yīng)用擾亂(confusion)和擴散(diffusion)的概念第二十七頁，共八十三頁，編輯于2023年，星期一Feistel加密過程輸入：

長為2w比特的明文分組

密鑰k輸出：長為2w比特的密文分組第二十八頁，共八十三頁，編輯于2023年，星期一Feistel密碼結(jié)構(gòu)特點明文分組分為：L0，R0，數(shù)據(jù)的這兩部分通過n次循環(huán)處理后，再結(jié)合起來生成密文分組每i次循環(huán)都以上一循環(huán)產(chǎn)生的Li-1和Ri-1和K產(chǎn)生的子密鑰Ki作為輸入。一般說來，子密鑰Ki與K不同，相互之間也不同，它是用子密鑰生成算法從密鑰生成的第二十九頁，共八十三頁，編輯于2023年，星期一Feistel結(jié)構(gòu)特點所有循環(huán)的結(jié)構(gòu)都相同替換：在數(shù)據(jù)的左半部分進(jìn)行，其方法是先對數(shù)據(jù)的右半部分應(yīng)用循環(huán)函數(shù)F，然后對函數(shù)輸出結(jié)果和數(shù)據(jù)的左半部分取異或(XOR)置換操作：數(shù)據(jù)左右兩個部分互換循環(huán)函數(shù)對每次循環(huán)都有相同的通用結(jié)構(gòu)，但由循環(huán)子密鑰Ki來區(qū)分在置換之后，執(zhí)行由數(shù)據(jù)兩部分互換構(gòu)成的交換第三十頁，共八十三頁，編輯于2023年，星期一Feistel密碼結(jié)構(gòu)加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)第三十一頁，共八十三頁，編輯于2023年，星期一Feistel密碼結(jié)構(gòu)解密過程：以密文作為輸入，以相反次序使用子密鑰解密:

Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)第三十二頁，共八十三頁，編輯于2023年，星期一第三十三頁，共八十三頁，編輯于2023年，星期一Feistel解密LD1=RD0=LE16=RE15

RD1=LD0

F(RD0,K16)=RE16

F(RE15,K16)=(LE15F(RE15,K16))F(RE15,K16)=LE15第三十四頁，共八十三頁，編輯于2023年，星期一Feistel網(wǎng)絡(luò)的設(shè)計特點分組大?。狠^大的分組意味著較強的安全性，但會降低加密解密速度。64位的分組大小是合理的折中，幾乎所有的分組設(shè)計中都使用它密鑰大?。狠^大的密鑰意味著較強的安全性，但會降低加密解密速度?，F(xiàn)代算法中最常用的是64位，128位密鑰循環(huán)次數(shù)：本質(zhì)是單一循環(huán)的不足，多重循環(huán)能夠加強安全性。典型的循環(huán)次數(shù)為16子密鑰生成算法：較大復(fù)雜性會增大密鑰分析難度循環(huán)函數(shù)F：較大復(fù)雜性意味著給密碼分析帶來更大難度第三十五頁，共八十三頁，編輯于2023年，星期一數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES概述：分組加密算法：明文和密文為64位分組長度對稱算法：加密和解密除密鑰編排不同外，使用同一算法密鑰長度：56位，但每個第8位為奇偶校驗位，可忽略密鑰可為任意的56位數(shù)，但存在弱密鑰，容易避開采用擾亂和擴散的組合，每個組合先替代后置換，共16輪只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運算，易于實現(xiàn)第三十六頁，共八十三頁，編輯于2023年，星期一DES加密算法的一般描述第三十七頁，共八十三頁，編輯于2023年，星期一輸入64比特明文數(shù)據(jù)初始置換IP在密鑰控制下16輪迭代初始逆置換IP-1輸出64比特密文數(shù)據(jù)交換左右32比特DES加密過程DES利用56比特串長度的密鑰K來加密長度為64位的明文，得到長度為64位的密文第三十八頁，共八十三頁，編輯于2023年，星期一第三十九頁，共八十三頁，編輯于2023年，星期一令i表示迭代次數(shù),表示逐位異或,f為加密函數(shù)DES加密過程第四十頁，共八十三頁，編輯于2023年，星期一DES解密過程令i表示迭代次數(shù),表示逐位模2求和,f為加密函數(shù)第四十一頁，共八十三頁，編輯于2023年，星期一輸入（64位）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157輸出（64位）L0（32位）R0（32位）初始置換IP第四十二頁，共八十三頁，編輯于2023年，星期一置換碼組輸入（64位）40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725輸出（64位）逆置換IP—1第四十三頁，共八十三頁，編輯于2023年，星期一DES的一輪迭代第四十四頁，共八十三頁，編輯于2023年，星期一選擇運算E32位輸入321234545678989101112131213141516171617181920212021222324252425262728292829303132148位輸出選擇擴展運算第四十五頁，共八十三頁，編輯于2023年，星期一擴展置換Ｅ-盒－32位擴展到48位擴展第四十六頁，共八十三頁，編輯于2023年，星期一選擇壓縮運算第四十七頁，共八十三頁，編輯于2023年，星期一S盒第四十八頁，共八十三頁，編輯于2023年，星期一S盒

第四十九頁，共八十三頁，編輯于2023年，星期一S盒對每個盒，6比特輸入中的第1和第6比特組成的二進(jìn)制數(shù)確定行，中間4位二進(jìn)制數(shù)用來確定列。其中相應(yīng)行、列位置的十進(jìn)制數(shù)的4位二進(jìn)制數(shù)表示作為輸出。例如輸入為101001，則行數(shù)和列數(shù)的二進(jìn)制表示分別是11和0100，即第3行和第4列，其中的第3行和第4列的十進(jìn)制數(shù)為3，用4位二進(jìn)制數(shù)表示為0011，所以的輸出為0011。第五十頁，共八十三頁，編輯于2023年，星期一選擇函數(shù)S1的例子

01234567891011121314150

1441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S1101100

1020010輸入6位：101100輸出4位0110第五十一頁，共八十三頁，編輯于2023年，星期一

置換P盒選擇函數(shù)的輸出（32位）1672021291228171152326518311028241432273919133062211425置換P加密函數(shù)的結(jié)果（32位）第五十二頁，共八十三頁，編輯于2023年，星期一子密鑰的產(chǎn)生第五十三頁，共八十三頁，編輯于2023年，星期一置換選擇157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124密鑰（64位）C0(28位)D0(28位)第五十四頁，共八十三頁，編輯于2023年，星期一Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)置換選擇2第五十五頁，共八十三頁，編輯于2023年，星期一DES安全性討論S盒設(shè)計準(zhǔn)則對S盒的疑義雪崩效應(yīng)弱密鑰與半弱密鑰DES的有效密鑰位數(shù)和迭代次數(shù)缺陷第五十六頁，共八十三頁，編輯于2023年，星期一S-盒的構(gòu)造DES中其它算法都是線性的，而S-盒運算則是非線性的S-盒不易于分析，它提供了更好的安全性所以S-盒是算法的關(guān)鍵所在第五十七頁，共八十三頁，編輯于2023年，星期一S-盒的構(gòu)造準(zhǔn)則沒有一個S盒是它輸入變量的線性函數(shù)S盒的每一行(由輸入比特的最左和最右比特確定)應(yīng)該包含16種比特組合改變S盒的一個輸入位至少要引起兩位的輸出改變?nèi)绻麑盒子的兩個輸入剛好在兩個中間比特上不同，則輸出必須在至少兩個比特上不同如果對S盒子的兩個輸入在它們的前兩位不同而在最后兩位相同，兩個輸出必須不同.第五十八頁，共八十三頁，編輯于2023年，星期一S-盒的構(gòu)造準(zhǔn)則對任何一個S盒，如果固定一個輸入比特，來看一個固定輸出比特的值，這個輸出比特為0的輸入數(shù)目將接近于這個輸出比特為1的輸入數(shù)目S-盒是許多密碼算法的唯一非線性部件,因此,它的密碼強度決定了整個算法的安全強度提供了密碼算法所必須的擾亂作用如何全面準(zhǔn)確地度量S-盒的密碼強度和設(shè)計有效的S-盒是分組密碼設(shè)計和分析中的難題非線性度、差分均勻性、嚴(yán)格雪崩準(zhǔn)則、可逆性、沒有陷門第五十九頁，共八十三頁，編輯于2023年，星期一對DES的S盒疑義DES的半公開性：S盒的設(shè)計原理至今未公布,只公布了設(shè)計準(zhǔn)則S盒可能隱含有陷井（Hiddentrapdoors)S盒是唯一具有差分?jǐn)U散功能的組件第六十頁，共八十三頁，編輯于2023年，星期一DES安全性討論雪崩效應(yīng)：明文或密鑰的一個比特的變化應(yīng)該引起密文許多比特的改變，如果變化太小,就可能找到一種方法減小有待搜索的明文和密鑰空間的大小第六十一頁，共八十三頁，編輯于2023年，星期一雪崩效應(yīng)例：明文:00000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000密鑰：00000011001011010010011000100011100001100000111000110010循環(huán)不同比特的個數(shù)0116221335439534632731第六十二頁，共八十三頁，編輯于2023年，星期一雪崩效應(yīng)明文：01101000 10000101001011100111101000010011011101101110101110100100密鑰：111001011110111101111001100000111010000100011000111011100011001011110111101111001100000111010000100011000111011100循環(huán)不同比特的個數(shù)0012214328432530632735第六十三頁，共八十三頁，編輯于2023年，星期一弱密鑰當(dāng)k1=k2=…=k16時，滿足DESk(m)=DESk-1(m)或者DESk(DESk(m))=m的密鑰稱為弱密鑰。第六十四頁，共八十三頁，編輯于2023年，星期一半弱密鑰半弱密鑰:若存在k或k’,使得DESk(m)=DESk’-1(m)或DESk(DESk’(m))=m,則k和k’構(gòu)成半弱密鑰。半弱密鑰將導(dǎo)致通過密鑰k’能夠破解有密鑰k加密的信息。第六十五頁，共八十三頁，編輯于2023年，星期一半弱密鑰半弱密鑰：DES至少有12個半弱密鑰,成對構(gòu)成k’-k第六十六頁，共八十三頁，編輯于2023年，星期一密鑰長度關(guān)于DES算法的另一個最有爭議的問題就是擔(dān)心實際56比特的密鑰長度不足以抵御窮舉式攻擊，因為密鑰量只有個早在1977年，Diffie和Hellman已建議制造一個每秒能測試100萬個密鑰的VLSI芯片。每秒測試100萬個密鑰的機器大約需要一天就可以搜索整個密鑰空間。他們估計制造這樣的機器大約需要2000萬美元。第六十七頁，共八十三頁，編輯于2023年，星期一

在CRYPTO’93上，Session和Wiener給出了一個非常詳細(xì)的密鑰搜索機器的設(shè)計方案，這個機器基于并行運算的密鑰搜索芯片，所以16次加密能同時完成。此芯片每秒能測試5000萬個密鑰，用5760個芯片組成的系統(tǒng)需要花費10萬美元，它平均用1.5天左右就可找到DES密鑰。

1997年1月28日，美國的RSA數(shù)據(jù)安全公司在RSA安全年會上公布了一項“秘密密鑰挑戰(zhàn)”競賽，其中包括懸賞1萬美元破譯密鑰長度為56比特的DES。美國克羅拉多洲的程序員Verser從1997年2月18日起，用了96天時間，在Internet上數(shù)萬名志愿者的協(xié)同工作下，成功地找到了DES的密鑰，贏得了懸賞的1萬美元。

第六十八頁，共八十三頁，編輯于2023年，星期一

1998年7月電子前沿基金會（EFF）使用一臺25萬美圓的電腦在56小時內(nèi)破譯了56比特密鑰的DES。1999年1月RSA數(shù)據(jù)安全會議期間，電子前沿基金會用22小時15分鐘就宣告破解了一個DES的密鑰。第六十九頁，共八十三頁，編輯于2023年，星期一雙重DESC=EK2(EK1(P))P=DK1(DK2(C))第七十頁，共八十三頁，編輯于2023年，星期一雙重DES的安全性中間相遇(meet-in-the-middle)攻擊

C=EK2(EK1(P))X=EK1(P)=DK2(C)給定明文密文對(P,C)

對所有256個密鑰,加密P,對結(jié)果排序

對所有256個密鑰,解密C,對結(jié)果排序逐個比較,找出K1,K2使得EK1(P)=DK2(C)第七十一頁，共八十三頁，編輯于2023年，星期一三重DESC=EK3(DK2(EK1(P)))P=DK1(EK2(DK3(C)))第七十二頁，共八十三頁，編輯于2023年，星期一三重DES分析兩個密鑰:C=EK1(DK2(EK1(P))) 三個密鑰:C=EK3(DK2(EK1(P)))三重DES速度慢第七十三頁，共八十三頁，編輯于2