第四講常規(guī)加密的現(xiàn)代技術(shù)詳解演示文稿

第四講常規(guī)加密的現(xiàn)代技術(shù)詳解演示文稿當(dāng)前1頁，總共81頁。（優(yōu)選）第四講常規(guī)加密的現(xiàn)代技術(shù)當(dāng)前2頁，總共81頁。分組密碼原理分組密碼是將明文消息編碼表示后的數(shù)字（簡稱明文數(shù)字）序列，劃分成長度為n的組（可看成長度為n的矢量），每組分別在密鑰的控制下變換成等長的輸出數(shù)字（簡稱密文數(shù)字）序列。當(dāng)前3頁，總共81頁。分組密碼原理分組密碼中密文輸出中每一位數(shù)字都與該數(shù)字所在組塊的n位明文數(shù)字有關(guān)，密鑰不變時，分組密碼對長度為n的明文所實施的變換是一樣的，分組密碼本質(zhì)上是長度為n的數(shù)字序列的變換問題當(dāng)前4頁，總共81頁。抵御統(tǒng)計分析密碼系統(tǒng)統(tǒng)計分析：在已知明文信息的某些統(tǒng)計特征的前提下，分析這些統(tǒng)計特征在密文中的反映，從而推測或推導(dǎo)可能的密鑰或包含密鑰的可能子集。信息論創(chuàng)始人Shannon提出為了抵御對密碼系統(tǒng)的統(tǒng)計分析，設(shè)計密碼系統(tǒng)的基本方法是擴散和擾亂。當(dāng)前5頁，總共81頁。密碼系統(tǒng)基本設(shè)計原理擴散（Diffusion):將明文的統(tǒng)計特征擴散到密文中,使得明文和密文之間的統(tǒng)計關(guān)系盡量復(fù)雜方法：使明文中的每一位數(shù)字影響密文中多位的值，或者說使密文中的一位依賴于明文中的多位數(shù)字例：對英文消息M=c1c2…cn…中字符Cn的加密操作：當(dāng)前6頁，總共81頁。密碼系統(tǒng)基本設(shè)計原理擾亂(confusion)：使得密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡量復(fù)雜方法：替換，線性變換無法起到有效的擾亂效果當(dāng)前7頁，總共81頁?，F(xiàn)代分組密碼設(shè)計原則分組長度足夠大：使得分組替換字母表中的元素個數(shù)2n足夠大，可有效的防止對明文實施窮舉攻擊。密鑰空間要足夠大,盡可能消除弱密鑰并且使所有密鑰的加密強度相同。保證足夠強的密碼算法復(fù)雜度，充分實現(xiàn)明文于密文的擴散和擾亂，能夠抗擊各種密碼分析攻擊當(dāng)前8頁，總共81頁?，F(xiàn)代分組密碼設(shè)計原則加解密運算簡單,盡量采用子塊和簡單運算：子塊的長度適應(yīng)軟件編程要求，通常長度取2的冪，密碼運算盡量采用簡單運算，如加法、與、或、異或、移位等。硬件實現(xiàn):最好加密與解密具有相似性，以便采用同樣的器件來實現(xiàn)加密和解密，節(jié)省費用和體積。盡量采用標(biāo)準(zhǔn)的組件結(jié)構(gòu)，以便能適應(yīng)于在超大規(guī)模集成電路中實現(xiàn)當(dāng)前9頁，總共81頁。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日生效當(dāng)前10頁，總共81頁。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)工作。當(dāng)前11頁，總共81頁。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)算法必須是可出口的當(dāng)前12頁，總共81頁。DES的產(chǎn)生1974年8月27日,NBS開始第二次征集,IBM提交了算法LUCIFER，該算法由IBM的工程師在1971~1972年研制1975年3月17日,NBS公開了全部細(xì)節(jié)1976年,NBS指派了兩個小組進行評價1976年11月23日，采納為聯(lián)邦標(biāo)準(zhǔn)，批準(zhǔn)用于美國政府的非密級政府通信1977年1月15日,“數(shù)據(jù)加密標(biāo)準(zhǔn)”FIPSPUB46發(fā)布當(dāng)前13頁，總共81頁。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)。當(dāng)前14頁，總共81頁。DES的應(yīng)用1997年一個研究小組進過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é)束。當(dāng)前15頁，總共81頁。S-DES加密算法S-DES：1)用于教學(xué)目的的簡化的DES加密算法2)以10位密鑰和8位明文分組作為輸入，產(chǎn)生8位密文分組輸出。3)解密使用相同密鑰當(dāng)前16頁，總共81頁。S-DES加密算法加密步驟：1)對輸入的8位明文分組m執(zhí)行初始置換IP(m)2)執(zhí)行一個包含替換、置換操作且依賴于密鑰的變換fk3)將數(shù)據(jù)進行左右4位兩半部分交換操作SW4)再執(zhí)行一次fk5)執(zhí)行逆置換IP-1產(chǎn)生密文輸出當(dāng)前17頁，總共81頁。S-DES加密算法當(dāng)前18頁，總共81頁。

S-DES的密鑰生成當(dāng)前19頁，總共81頁。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)當(dāng)前20頁，總共81頁。S-DES的密鑰生成例：若K選為(1010000010),產(chǎn)生的兩個子密鑰分別為

K1=(10100100)K2=(01000011)1)進行P10置換,m1=P10(1010000010)=(1000001100)2)循環(huán)左移m2=LS-1(m1L)||LS-1(m1R)==LS-1(10000)||LS-1(01100)=(0000111000)當(dāng)前21頁，總共81頁。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)當(dāng)前22頁，總共81頁。S-DES的加密運算初始置換用IP函數(shù):末端置換為IP的逆置換:易見IP-1(IP(X))=X當(dāng)前23頁，總共81頁。當(dāng)前24頁，總共81頁。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位確定當(dāng)前25頁，總共81頁。S-DES的加密運算例：S0(1110)=S23=3=(11)P4:4位置換P4(b1,b2,b3,b4)=(b2,b4,b3,b1)當(dāng)前26頁，總共81頁。Feistel密碼結(jié)構(gòu)思想基本思想：用簡單算法的乘積來近似表達大尺寸的替換變換多個簡單算法的結(jié)合得到的加密算法比任何一個部分算法都要強交替使用替換和置換應(yīng)用擾亂(confusion)和擴散(diffusion)的概念當(dāng)前27頁，總共81頁。Feistel加密過程輸入：

長為2w比特的明文分組

密鑰k輸出：長為2w比特的密文分組當(dāng)前28頁，總共81頁。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不同，相互之間也不同，它是用子密鑰生成算法從密鑰生成的當(dāng)前29頁，總共81頁。Feistel結(jié)構(gòu)特點所有循環(huán)的結(jié)構(gòu)都相同替換：在數(shù)據(jù)的左半部分進行，其方法是先對數(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)成的交換當(dāng)前30頁，總共81頁。Feistel密碼結(jié)構(gòu)加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)當(dāng)前31頁，總共81頁。Feistel密碼結(jié)構(gòu)解密過程：以密文作為輸入，以相反次序使用子密鑰解密:

Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)當(dāng)前32頁，總共81頁。當(dāng)前33頁，總共81頁。Feistel解密LD1=RD0=LE16=RE15

RD1=LD0

F(RD0,K16)=RE16

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

當(dāng)前49頁，總共81頁。S盒對每個盒，6比特輸入中的第1和第6比特組成的二進制數(shù)確定行，中間4位二進制數(shù)用來確定列。其中相應(yīng)行、列位置的十進制數(shù)的4位二進制數(shù)表示作為輸出。例如輸入為101001，則行數(shù)和列數(shù)的二進制表示分別是11和0100，即第3行和第4列，其中的第3行和第4列的十進制數(shù)為3，用4位二進制數(shù)表示為0011，所以的輸出為0011。當(dāng)前50頁，總共81頁。選擇函數(shù)S1的例子

01234567891011121314150

1441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S1101100

1020010輸入6位：101100輸出4位0110當(dāng)前51頁，總共81頁。

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

在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萬美元。

當(dāng)前68頁，總共81頁。

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

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

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

對所有256個密鑰