《密碼學(xué)基礎(chǔ)》課件 （張薇） 第1、2章 古典密碼、分組密碼與DES

——密碼的歷史及古典密碼傳統(tǒng)加密技術(shù)4學(xué)時密碼的起源和發(fā)展密碼學(xué)的基本概念古典密碼初等密碼分析主要內(nèi)容了解密碼的產(chǎn)生和發(fā)展歷史掌握密碼學(xué)的基本概念理解古典密碼的加密思想，掌握基本的加密方法：置換和代替掌握密碼體制的分類方法理解初等密碼分析的思想教學(xué)目的古代——近代——現(xiàn)代

一、密碼的起源和發(fā)展19491976隱寫術(shù)Staganography

由希臘詞Steganos（覆蓋）和Graphein（寫）派生而來。密碼術(shù)Cryptography

由希臘詞Kryptos（隱藏）派生而來。密碼的起源希波戰(zhàn)爭，漏格板希斯塔亞烏斯，在奴隸頭皮上寫字中國古代，蠟封小球公元一世紀，普林尼，隱形墨水一、密碼的起源和發(fā)展密碼技術(shù)的發(fā)展15世紀，意大利建筑師利昂．阿爾伯提設(shè)計的密碼盤密碼技術(shù)的發(fā)展?jié)摲嚓P(guān)影視作品例：

愷撒《高盧記》——將羅馬字母用希臘字母替換蘇托尼厄斯《愷撒傳》——愷撒密碼一、密碼的起源和發(fā)展兩種基本加密方法代替——對標(biāo)準書寫符號的修改Substitution機械密碼大行其道Enigma，Hagelin密碼機密碼破譯成果輝煌紫密，圖靈炸彈，中途島新技術(shù)的大量使用微粒照片，圖靈機一、密碼的起源和發(fā)展二戰(zhàn)中的密碼特點機械密碼：用機器實現(xiàn)代替與置換三種有代表性的密碼機：

Enigma（德、意、日軍方）

Lorenz（德國高層）Hagelin（盟國：美、英、法等）

二戰(zhàn)中的密碼一、密碼的起源和發(fā)展三、古典密碼（Classical

Ciphers）Enigma三、古典密碼（Classical

Ciphers）Hagelin1912年，美國人愛德華.休.赫本(EdwardHughHebern)發(fā)明了可以通過”移動字母板”加密的打字機，并申請專利。1918年，德國人阿瑟．謝爾比斯為Enigma申請專利。瑞典人鮑里斯.愷撒.威廉.哈格林（BorisCaesarWilhelmHagelin），靠密碼機發(fā)財?shù)谝蝗?/p>

三、古典密碼（Classical

Ciphers）機械密碼轉(zhuǎn)輪機(RotorMachine)

大量裝備、參加實戰(zhàn)、遭到破譯、徹底曝光

1918年，德國發(fā)明家阿瑟．謝爾比斯為Enigma申請專利，并與理查德．里特建立了謝爾比斯＆里特公司，出售Enigma，售價為今天的3萬$/臺困境：賣不出去采取措施：拼命改進轉(zhuǎn)機：1922年，丘吉爾出版《第一次世界大戰(zhàn)回憶錄》

Enigma納粹德國的四大軍事象征

普魯士之鷹鐵十字EnigmaEnigma英國組織破譯（布萊切利莊園）圖靈發(fā)明BombeEnigma破譯Enigma的意義：波蘭人，Bomba，機械化密碼分析時代的到來英國Bombe，證明了機械化密碼分析手段在破解機械化密碼時的極端必要性波蘭和英國專家能手工破譯，說明了密碼破譯歸根結(jié)底是人類智慧的勝利。Enigma密碼學(xué)(Cryptology):

研究信息系統(tǒng)安全保密的科學(xué)，包括密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)(Cryptography):

主要研究對信息進行編碼,實現(xiàn)對信息的隱蔽.密碼分析學(xué)(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.二、密碼學(xué)的基本概念密碼體制：是一個五元組（P,C,K,E,D)，滿足條件：（1）P是可能明文的有限集（明文空間）（2）C是可能密文的有限集（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集（密鑰空間）（4）任意k∈K,有一個加密算法ek∈E和相應(yīng)的解密算法dk∈D，使得ek:P→C和dk:C→P分別為加密解密函數(shù)，滿足dk(ek(x))=x,這里x∈P。二、密碼學(xué)的基本概念密碼體制Example明文：Allofgaulisdividedintothreeparts.密文：DOORIJEXOLVGLYLGHGLQWRWKUHHSDUWV代替密碼2.單表代替（MonoalphabeticSubstitution）所有的消息用同一個代替表加密，相同的明文替換為相同的密文。例：

乘法密碼 仿射密碼，多項式代替密碼 密鑰短語密碼（將口令字中的字符無重復(fù)地寫下，再將余下的字符按順序?qū)懞茫⑺鼈兒兔魑淖帜附⒁灰粚?yīng)的關(guān)系。）三、古典密碼（Classical

Ciphers）代替密碼多表代替：1412年，埃及數(shù)學(xué)家艾哈邁德.卡勒卡尚迪(Ahmadal-Qalqashandi)在百科全書中第一次提出。1508年，德國修道院院長約翰內(nèi)斯.特米特里烏斯(HohannesTrithemius)首先構(gòu)造出方表（tableau）——多個代替表1553年，意大利學(xué)者吉奧萬.巴蒂斯塔.貝拉索（GiovanBattistaBellaso）設(shè)計出了密鑰。貝拉索密碼，使用時間較長，美國內(nèi)戰(zhàn)時北軍使用。多表代替1586年，法國外交官布萊斯.德.維吉尼亞（BlaiseDeVigenere）對貝拉索密碼進行改良。Vigenère密碼：1854年，被英國人查理斯.巴貝奇（CharlesBabbage）所破譯查理斯.巴貝奇（1792-1871）：設(shè)計了差分機（differenceengine）和分析機（analyticalengine），是現(xiàn)代計算機的雛形。多表代替二、置換技術(shù)（Permutation）1.柵欄技術(shù)——按列寫入，按行讀出。例：用深度為2的柵欄技術(shù)加密明文“meetmeaftertheparty”

可寫為按行讀出密文為“mematrhtgpryetefeteoaat”2.矩陣密碼——把消息按行寫入，再按列讀出。mematrhtgpryetefeteoaat三、古典密碼（Classical

Ciphers）置換密碼加密部分可分為：多表代替模塊：轉(zhuǎn)輪組單表代替模塊：連接板附加模塊：反射板Enigma破譯或攻擊（Break/Attack）密碼的方法包括窮舉破譯法（ExhaustiveAttack）和分析法兩類。窮舉法，又稱為強力攻擊（Brute-forceMethod），指對截收的密文依次用各種可能的密鑰試譯，直到得到有意義的明文；或者在不變密鑰下，對所有可能的明文加密直到得到與截獲密文一致，這又稱為完全試湊法（CompleteTrial-and-errorMethod）四、初等密碼分析唯密文攻擊（CiphertectOnlyAttak）分析者從僅知道的密文進行分析，試圖得出明文或密鑰。已知明文攻擊（KnowPlaintextAttak）分析者除了有截獲密文外，還有一些已知的明文－密文對。選擇明文攻擊（ChosenPlaintextAttack）分析者可以選定任何明文－密文對進行攻擊，以確定未知密鑰。選擇密文攻擊（ChosenCiphertextAttack）分析者可以利用解密機由他所選的密文解密出相應(yīng)明文，以確定未知密鑰。四、初等密碼分析密碼分析分類分組密碼與數(shù)據(jù)加密標(biāo)準4學(xué)時分組密碼的基本概念數(shù)據(jù)加密標(biāo)準DESDES的產(chǎn)生及使用DES算法細節(jié)DES的安全性分析DES在設(shè)計上的優(yōu)點分組密碼的設(shè)計原理分組密碼的工作方式主要內(nèi)容現(xiàn)代密碼對稱密碼非對稱密碼序列密碼分組密碼對稱密碼非對稱密碼現(xiàn)代密碼的分類加密方式序列密碼（Streamcipher）：也叫流密碼，用隨機的密鑰序列依次對明文字符加密，一次加密一個字符。分組密碼（Blockcipher）：將明文劃分為長度固定的組，逐組進行加密，得到長度固定的一組密文。密文分組中的每一個字符與明文分組的每一個字符都有關(guān)。第一節(jié)分組密碼的基本概念加密算法解密算法明文密鑰密鑰x=(x1,…,xm

)y=(y1,…,yn

)密文第一節(jié)分組密碼的基本概念分組密碼加密框圖分組長度：64bit有效密鑰長度：56bit密鑰生成算法：產(chǎn)生16個48bit的子密鑰解密過程與加密過程相同，所使用的密鑰也相同，但各個子密鑰的使用順序不同。算法的全部的細節(jié)公開，安全性完全依賴于密鑰。第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES基本特征初始置換IP16輪迭代逆初始置換IP-1子密鑰產(chǎn)生算法。

第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES算法細節(jié)算法構(gòu)成對64bit的明文重新排列，而后分成左右兩段，每段32bit，以L0和R0表示。IP中各列元素位置號數(shù)相差為8，相當(dāng)于將原明文各字節(jié)按列寫出，各列比特經(jīng)過偶采樣和奇采樣置換后，再對各行進行逆序排列，將陣中元素按行讀出，構(gòu)成置換的輸出。第二節(jié)數(shù)據(jù)加密標(biāo)準DES初始置換IP在16圈迭代之后，將左右兩段合并為64bit，進行置換IP-1，得到輸出的64bit密文。第二節(jié)數(shù)據(jù)加密標(biāo)準DES逆初始置換IP和IP-1的輸入與輸出是已知的一一對應(yīng)關(guān)系作用：打亂原來輸入的ASCII碼字劃分，并將原來明文的校驗位（如果有的話）變?yōu)镮P輸出的一個字節(jié)。第二節(jié)數(shù)據(jù)加密標(biāo)準DES逆初始置換將經(jīng)過IP置換后的數(shù)據(jù)分成32bit的左右兩段，進行16圈迭代每次迭代只對右邊的32bit進行一系列的加密變換一輪迭代即將結(jié)束時，將左邊的32bit與右邊進行變換后得到的32bit按位模2加，作為下一輪迭代時右邊的段，并將原來右邊未經(jīng)變換的段直接作為下一輪迭代時左邊的段。

第二節(jié)數(shù)據(jù)加密標(biāo)準DES乘積變換——DES算法的核心64比特初始密鑰經(jīng)過置換選擇PC-1循環(huán)移位置換選擇PC-2產(chǎn)生16次迭代所用的子密鑰ki

初始密鑰的第8、16、24、32、40、48、56、64位為奇偶校驗位，其余56位為有效位，PC-1的目的是從64位中選出56位有效位。第二節(jié)數(shù)據(jù)加密標(biāo)準DES子密鑰生成算法每次移位后，將C和D中的原存數(shù)送給置換選擇PC-2，PC-2將C中第9、18、22、25位和D中第7、9、15、26位刪去，將其余數(shù)字置換位置，輸出48比特，作為子密鑰。第二節(jié)數(shù)據(jù)加密標(biāo)準DES子密鑰生成IP：初始置換ki

：第i次迭代所用的子密鑰Li、Ri：第i次迭代時左邊和右邊的32比特f：每次迭代時對右邊所作的變換：逐位模2加。

第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES算法的數(shù)學(xué)表示符號說明加密過程：64Bit明文64Bit密文（1）（2）第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES算法的數(shù)學(xué)表示解密過程：（64比特明文）（64比特密文）第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES算法的數(shù)學(xué)表示互補對稱性弱密鑰和半弱密鑰對DES的強力攻擊差分分析和線性分析第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES的安全性DES設(shè)計上的優(yōu)點主要體現(xiàn)在以下幾個方面循環(huán)次數(shù)雪崩準則精巧的S盒和P盒第二節(jié)數(shù)據(jù)加密標(biāo)準DESDES在設(shè)計上的優(yōu)點