第二講____古典密碼學(xué)

1、第二講第二講 古典密碼學(xué)古典密碼學(xué) 2022-5-12第二講的主要內(nèi)容第二講的主要內(nèi)容經(jīng)典密碼經(jīng)典密碼n替代技術(shù)替代技術(shù)n置換技術(shù)置換技術(shù)分組密碼的原理分組密碼的原理nFeistelFeistel密碼密碼DESDESnDESDES加密加密nDESDES分析分析分組密碼的設(shè)計準(zhǔn)則分組密碼的設(shè)計準(zhǔn)則 2022-5-13加密與信息隱藏加密與信息隱藏信息隱藏：不知道信息存在于傳輸介質(zhì)信息隱藏：不知道信息存在于傳輸介質(zhì)的何處。的何處。(Information Hiding)(Information Hiding)加密：知道信息在何處，卻不能理解信加密：知道信息在何處，卻不能理解信息的意義。息的意義。 2

2、022-5-14信息隱藏的框架信息隱藏的框架MarkingalgorithmMarkedMediaStego-MediaMarkSecret/Public keyoralgorithmSecret/Public keyMarkingMark and/or original MediaMarked-MediaMarkconfidence measure 2022-5-15信息隱藏的媒體信息隱藏的媒體純文本純文本格式文本格式文本多媒體介質(zhì)，如圖像，音頻，視頻多媒體介質(zhì)，如圖像，音頻，視頻 2022-5-16信息隱藏的范圍信息隱藏的范圍InformationHidingChannelsCovertS

3、teganographyAnonymityCopyrightMarkingLinguisticSteganographyTechnicalSteganographyRobust Copyright MarkingMarkingFragileWatermarkingFingerprintingWatermarkingImperceptibleVisibleWatermarking 2022-5-17信息隱藏的例子信息隱藏的例子第二次世界大戰(zhàn)從日本戰(zhàn)俘營寄給美國聯(lián)第二次世界大戰(zhàn)從日本戰(zhàn)俘營寄給美國聯(lián)邦調(diào)查局的明信片：邦調(diào)查局的明信片：Dscf0053.jpg 2022-5-18信息隱藏的例子信息隱

4、藏的例子小時候玩的游戲：小時候玩的游戲：老板催我早一點決定畢業(yè)去向的時候，已是初老板催我早一點決定畢業(yè)去向的時候，已是初夏樹，我還是感到一陣陣涼意。看著老板已經(jīng)夏樹，我還是感到一陣陣涼意。看著老板已經(jīng)斑白的頭發(fā)，心里不禁酸楚?？蛇@畢竟掩蓋不斑白的頭發(fā)，心里不禁酸楚?？蛇@畢竟掩蓋不了心底的無奈和郁悶，不過我知道我終究改變了心底的無奈和郁悶，不過我知道我終究改變不了什么，我清楚老板很器重我，私下里常對不了什么，我清楚老板很器重我，私下里常對他朋友說我是他最得意的弟子，是最有可能繼他朋友說我是他最得意的弟子，是最有可能繼承他衣缽的人?？墒抢习迥锔矚g文國，因為承他衣缽的人。可是老板娘更喜歡文國，因為

5、他既將成為她的愛婿。我和文國都是老板今年他既將成為她的愛婿。我和文國都是老板今年要畢業(yè)的研究生，老板只能從兩人中留下一個，要畢業(yè)的研究生，老板只能從兩人中留下一個，老板說會為我努力。今天看到他從院長辦公室老板說會為我努力。今天看到他從院長辦公室出來的神色，一切都清楚地寫在臉上，我已經(jīng)出來的神色，一切都清楚地寫在臉上，我已經(jīng)沒有什么機會了。沒有什么機會了。 2022-5-19信息隱藏的例子信息隱藏的例子藏頭詩：藏頭詩：神神箭一飛入藍(lán)天，箭一飛入藍(lán)天，舟舟中載人國力顯。中載人國力顯。五五岳三山河九曲，岳三山河九曲，號號子響徹長江邊。子響徹長江邊。揚揚眉吐氣歌且舞，眉吐氣歌且舞，我我握巨筆作詩篇。握

6、巨筆作詩篇。國國運昌盛民安樂，運昌盛民安樂，威威龍狂舞萬萬年。龍狂舞萬萬年。 2022-5-110替代和置換替代和置換(易位易位)替代技術(shù)替代技術(shù) 明文字母由其他字母或數(shù)字或符號所代替，明文字母由其他字母或數(shù)字或符號所代替，進行逆運算恢復(fù)明文。進行逆運算恢復(fù)明文。置換技術(shù)置換技術(shù) 對明文字母的某種置換取得一種類型完全對明文字母的某種置換取得一種類型完全不同的映射，即明文中字母重新排列，本不同的映射，即明文中字母重新排列，本身未變，位置發(fā)生改變。身未變，位置發(fā)生改變。 2022-5-1111.單表替換單表替換n移位替換移位替換n乘法密碼乘法密碼n放射變換放射變換n密鑰短語密碼密鑰短語密碼2.多表

7、代替多表代替nVigenere密碼密碼nVername密碼密碼nHill密碼密碼 2022-5-112單表替換對明文中胡所有字符都使用一個固定胡對明文中胡所有字符都使用一個固定胡映射，即：映射，即：,.,110naaaA,.,110nbbbBiibafBAf)(,: 2022-5-113移位密碼之愷撒密碼愷撒密碼把字母表中的每個字母用該字母愷撒密碼把字母表中的每個字母用該字母后面第三個字母進行代替后面第三個字母進行代替n明文：明文：n密文：密文：一個例子：一個例子：n明文：明文：we are studentswe are studentsn密文：密文：zh duh vwxghqwvzh duh

8、 vwxghqwv愷撒密碼的數(shù)學(xué)表示愷撒密碼的數(shù)學(xué)表示 c = E(m,k) = (m + k) mod q m = D(c,k) = (c - k) mod q 2022-5-114愷撒密碼對愷撒密碼進行強行攻擊密碼分析對愷撒密碼進行強行攻擊密碼分析n加密和解密算法已知加密和解密算法已知n密鑰空間大小為密鑰空間大小為25，為什么，為什么n明文容易識別攻擊明文容易識別攻擊增大愷撒密碼的密鑰空間增大愷撒密碼的密鑰空間n隨機替換，密鑰空間隨機替換，密鑰空間26!，為什么，為什么利用語言的規(guī)律性利用語言的規(guī)律性 2022-5-115密碼分析人類語言有冗余度人類語言有冗余度字母使用頻率不相同字母使用頻

9、率不相同在英文中，在英文中，e的使用率最高的使用率最高其次，其次，T,R,N,I,O,A,S其他字母使用頻率較低其他字母使用頻率較低密文反應(yīng)了明文字母出現(xiàn)的規(guī)律性密文反應(yīng)了明文字母出現(xiàn)的規(guī)律性 2022-5-116英文字母使用頻率 2022-5-117英文字母中常見的組合 2022-5-118愷撒密碼的分析方法首先單字頻率確定首先單字頻率確定e，t的范圍。的范圍。然后使用雙字頻率。然后使用雙字頻率。如有可能還可以使用如有可能還可以使用3字頻率，字頻率，the。 2022-5-119乘法密碼加密變換為：加密變換為：解密變換為：解密變換為：其中其中，例如：英文字母表例如：英文字母表n=26,選擇密

10、鑰選擇密鑰k=9,則則k-1=3,明文字母到秘文字母替換為下明文字母到秘文字母替換為下表：表：1),(mod,)(nknikjaaEjik1),(mod,)(nknikjaaEjiknkjiaaDijkmod.,)(1)(mod1.11nkkkk的逆，為 2022-5-120ABCDE FGHIJKLMAJSBK TCLUDM VENOPQR STUVW XYZNW FOX GPYHQZIR0 1 2 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 20 21 22 23 24 25 2022-5-121密鑰短語密碼選擇一個英文短語作為密鑰，去掉其中選擇一

11、個英文短語作為密鑰，去掉其中重復(fù)胡字母，得到一個無重復(fù)的字母串，重復(fù)胡字母，得到一個無重復(fù)的字母串，依次寫在明文字母表下，而后在將字母依次寫在明文字母表下，而后在將字母表中未出現(xiàn)胡字母依次寫于此短語之后，表中未出現(xiàn)胡字母依次寫于此短語之后，構(gòu)造一個字母替換表。構(gòu)造一個字母替換表。例如：例如： 2022-5-122例例 短語：短語：happy new year hapynewr明文：明文：persion abcde fghijklmhapyn ew rbcdfgnopqrstuvw xyzijklm oqstuvxz 2022-5-123單表密碼安全性分析密鑰量小密鑰量小詞頻特性詞頻特性沒將明文

12、字母出現(xiàn)胡概率掩蔽起來。沒將明文字母出現(xiàn)胡概率掩蔽起來。 2022-5-124二 多表代替單表是明文字母與密文字母一一對應(yīng)，單表是明文字母與密文字母一一對應(yīng)，明文中字母統(tǒng)計特性在密文中沒有得到明文中字母統(tǒng)計特性在密文中沒有得到改變，所以容易破譯。改變，所以容易破譯。多表定義：以一系列代替表依次對明文多表定義：以一系列代替表依次對明文消息的字母進行替換的加密算法。消息的字母進行替換的加密算法。 2022-5-125Vigenere密碼 2022-5-126Vigenere密碼Vigenere加密加密n密鑰密鑰 deceptivedeceptivedecepitven明文明文 wearedicov

13、eredsaveyourselfn密文密文 zicvtwqngrzgvtwavzhcqyglmgj 2022-5-127Vigenere密碼密碼分析密碼分析n猜測關(guān)鍵字長度猜測關(guān)鍵字長度w兩個相同明文字母序列出現(xiàn)在一定距離里，該距離是關(guān)鍵字長度的整數(shù)倍，那么它們將產(chǎn)生相同的密文序列n分割分割vigenere密碼為單字母密碼密碼為單字母密碼w密鑰以關(guān)鍵字長度為周期改進改進n消除關(guān)鍵字的周期性消除關(guān)鍵字的周期性wAT&T的工程師設(shè)計一個使用非常長的密鑰工作的系統(tǒng)w只要有足夠的密文，或已知明文仍能夠破譯一次一密方案一次一密方案n使用與消息一樣長的隨機密鑰使用與消息一樣長的隨機密鑰n實際使用困

14、難：發(fā)送者和接收者必須擁有該隨機密鑰實際使用困難：發(fā)送者和接收者必須擁有該隨機密鑰 2022-5-128Playfair密碼：英國陸軍在密碼：英國陸軍在第一次世界第一次世界大戰(zhàn)大戰(zhàn)，美國陸軍美國陸軍在在第二次世界大戰(zhàn)第二次世界大戰(zhàn)期間期間大量使用的一種二字母組代替密碼。密大量使用的一種二字母組代替密碼。密鑰由鑰由26個個英文字母英文字母組成五階方陣。組成五階方陣。 矩陣的構(gòu)造矩陣的構(gòu)造:從左到右、從上到下填入關(guān)從左到右、從上到下填入關(guān)鍵詞的字母（去除重復(fù)字母），然后再鍵詞的字母（去除重復(fù)字母），然后再以以字母表字母表順序?qū)⒂嘞碌淖帜柑钊刖仃囀ｍ樞驅(qū)⒂嘞碌淖帜柑钊刖仃囀Ｓ嗫臻g。余空間。 Play

15、fair密碼 2022-5-129構(gòu)造關(guān)鍵字矩陣如下：構(gòu)造關(guān)鍵字矩陣如下：harpsichord HARSPI/JCOBDEFGLMNQUTVWXZYK 2022-5-130Playfair密碼加密規(guī)則加密規(guī)則n加密規(guī)則加密規(guī)則 m1,m2同行：同行：c1,c2在它們右邊；在它們右邊； m1,m2同列：同列：c1,c2在它們下邊；在它們下邊； m1,m2不同行列：不同行列：c1,c2是是m1,m2 組成的長方形組成的長方形的另兩個頂點；的另兩個頂點； m1=m2：在其間插入一無效字母；：在其間插入一無效字母； 明文由奇數(shù)個字母組成，則在明文后加一無效字母明文由奇數(shù)個字母組成，則在明文后加一無效

16、字母 分析分析n2626種字母組合種字母組合n頻率分析變得困難頻率分析變得困難 2022-5-131例：例： M=bookstore M=bo xo ks to re C=id rg lp qd hg 2022-5-132Hill密碼m個連續(xù)明文字母被個連續(xù)明文字母被m個密文字母代替?zhèn)€密文字母代替由由m個線性方程決定替代方法個線性方程決定替代方法m=3時的系統(tǒng)描述：時的系統(tǒng)描述：n編碼（編碼（a=0,b=1,z=25) CKP26mod)(3132121111pkpkpkC26mod)(3232221212pkpkpkC26mod)(3332321313pkpkpkC3213332312322

17、21131211321pppkkkkkkkkkCCC 2022-5-133Hill密碼一個例子：一個例子：n明文為明文為pay more moneyn加密密鑰為加密密鑰為np=15,a=0,y=24nK(15,0,24) mod 26 = (11,13,18)192221182151717K 2022-5-134Hill密碼破解破解Hill密碼？密碼？已知明文攻擊的情況下解線性方程組。已知明文攻擊的情況下解線性方程組。111213123212223123313233(,)( ,)kkkC C CkkkP P Pkkk1CK PKC P 2022-5-135置換技術(shù)柵欄技術(shù)areaer 明文：明

18、文： wait me at the gate 加密：加密： wimateae atethgt 密文：密文： wimateaeatethgt 2022-5-136置換技術(shù)柵欄技術(shù)更為復(fù)雜一些的更為復(fù)雜一些的n密鑰：密鑰：43125674312567n明文：明文： attackpattackp ostponeostpone duntiltduntilt woamxyzwoamxyzn密文：密文：APTMTTNAAODWTSUOCOIXKNLYPETZ 2022-5-137置換技術(shù)-倒置法報文倒置：將報文內(nèi)容按順序依次倒置，并報文倒置：將報文內(nèi)容按順序依次倒置，并截成固定長度的字母組，形成密文。截成

19、固定長度的字母組，形成密文。分組倒置：將明文截成固定長度的字母串，分組倒置：將明文截成固定長度的字母串，將每組字母倒置，形成密文。將每組字母倒置，形成密文。例如：例如：原文原文there was a small attendance at the meeting報文報文gnit eeme htta ecna dnet tall amsa sawe reht分組分組 ereth sasaw allam dnett aecna mehtt nitee g 2022-5-138置換技術(shù)-方格易位法按雙方約定的方格和填寫順序，將原文填入方按雙方約定的方格和填寫順序，將原文填入方格，再按約定的抄寫次序?qū)?/p>

20、出規(guī)定長度的密碼。格，再按約定的抄寫次序?qū)懗鲆?guī)定長度的密碼。例如：約定例如：約定5*n方格中，橫向從上到下填寫原方格中，橫向從上到下填寫原文，從左到右寫出長度為文，從左到右寫出長度為4的密碼的密碼明文明文she attended a concert密文密文stdc heae encr adot ten特點：簡單易行，特點：簡單易行， 但經(jīng)不起窮舉試驗但經(jīng)不起窮舉試驗sheattendedaconcert 2022-5-139分組密碼的原理流密碼和分組密碼流密碼和分組密碼當(dāng)前對稱加密算法幾乎都基于當(dāng)前對稱加密算法幾乎都基于Feistel分組密碼分組密碼乘積密碼乘積密碼n連續(xù)執(zhí)行兩個或多個密碼基本

21、運算單元連續(xù)執(zhí)行兩個或多個密碼基本運算單元nFeistel提出用替代和置換交替的方式構(gòu)造密碼提出用替代和置換交替的方式構(gòu)造密碼nShannon提出用擾亂和擴散交替的方式構(gòu)造密碼提出用擾亂和擴散交替的方式構(gòu)造密碼擴散和擾亂擴散和擾亂n目的：挫敗基于統(tǒng)計分析的密碼分析方法目的：挫敗基于統(tǒng)計分析的密碼分析方法n擴散：明文的統(tǒng)計結(jié)構(gòu)擴散到密文中擴散：明文的統(tǒng)計結(jié)構(gòu)擴散到密文中n擾亂：密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡擾亂：密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡可能復(fù)雜可能復(fù)雜 2022-5-140Feistel密碼Feistel加密加密 2022-5-141Feistel密碼變換可以用下列函數(shù)表示

22、變換可以用下列函數(shù)表示: L(i) = R(i-1) L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1)R(i) = L(i-1) XOR g(K(i), R(i-1) 求逆很容易求逆很容易 實際中，一些這樣的連續(xù)變換形成完整實際中，一些這樣的連續(xù)變換形成完整密碼變換（典型：密碼變換（典型：16輪）輪） 2022-5-142Feistel密碼的設(shè)計準(zhǔn)則分組大小分組大小n增加分組長度會提高安全性增加分組長度會提高安全性, 但降低了密碼運算速但降低了密碼運算速度度密鑰大小密鑰大小n增加密鑰長度增加密鑰長度,可以提高安全性可以提高安全性(使得窮搜索困難使得窮

23、搜索困難),同樣同樣,降低了密碼速度降低了密碼速度循環(huán)次數(shù)循環(huán)次數(shù)n增加輪數(shù)可以提高安全性增加輪數(shù)可以提高安全性,但降低速度但降低速度子密鑰產(chǎn)生算法子密鑰產(chǎn)生算法n子密鑰生成越復(fù)雜子密鑰生成越復(fù)雜,就越安全就越安全,但降低速度但降低速度Round函數(shù)函數(shù)n復(fù)雜的輪函數(shù)能夠使的密碼分析困難復(fù)雜的輪函數(shù)能夠使的密碼分析困難,但降低速度但降低速度 2022-5-143Feistel密碼的設(shè)計準(zhǔn)則所有問題就是平衡問題所有問題就是平衡問題n設(shè)計設(shè)計”安全安全”的密碼算法并不難的密碼算法并不難,只要使用只要使用足夠多的輪數(shù)就可以足夠多的輪數(shù)就可以,但降低速度但降低速度 快速的軟件加解密快速的軟件加解密便于

24、分析便于分析 2022-5-144Feistel密碼解密Feistel解密解密 2022-5-145（數(shù)據(jù)加密標(biāo)準(zhǔn)）簡介簡介n1977年被美國標(biāo)準(zhǔn)局作為數(shù)據(jù)加密標(biāo)準(zhǔn)年被美國標(biāo)準(zhǔn)局作為數(shù)據(jù)加密標(biāo)準(zhǔn)n64bit分組加密，密鑰長度為分組加密，密鑰長度為56bitn對稱密鑰體制對稱密鑰體制的由來的由來對的評論對的評論n密鑰長度比較短密鑰長度比較短n內(nèi)部結(jié)構(gòu)的設(shè)計標(biāo)準(zhǔn)保密內(nèi)部結(jié)構(gòu)的設(shè)計標(biāo)準(zhǔn)保密 2022-5-146一般描述一般描述 2022-5-147每個每個 循環(huán)的循環(huán)的 詳細(xì)詳細(xì) 過程過程 2022-5-148F（R，K）A=R(32 bits)J=K(48 bits)EE(A)為48 bits+B

25、1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B寫成8個6比特串 2022-5-149S 盒的作用盒的作用n6bit4bitn輸入的第一和最后兩比特決定行輸入的第一和最后兩比特決定行n輸入的中間四比特決定列輸入的中間四比特決定列n被選中的數(shù)字轉(zhuǎn)換成被選中的數(shù)字轉(zhuǎn)換成4比特輸出比特輸出 2022-5-150密鑰的產(chǎn)生密鑰的產(chǎn)生n選擇置換矩陣選擇置換矩陣1n循環(huán)左移一位或兩位循環(huán)左移一位或兩位n選擇置換矩陣選擇置換矩陣2解密解密n逆次使用子密鑰逆次使用子密鑰KPC-1C0 D0LS1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 2022-5-151雪崩效應(yīng)雪崩效應(yīng) 明文或密鑰的一點點變動應(yīng)引起密文發(fā)明文或密鑰的一點點變動應(yīng)引起密文發(fā)生大的變化生大的變化的雪崩效應(yīng)的雪崩效應(yīng) 2022-5-152對的分析密鑰的大小密鑰的大小n的密鑰空間為的密鑰空間為2