第二講：密碼學(xué)基礎(chǔ)

2024/5/91第二講：密碼學(xué)基礎(chǔ)

主講:張修軍Email:woodszhang@電話:88195226密碼學(xué)基礎(chǔ)教學(xué)目的通過本講的學(xué)習(xí)，應(yīng)能了解密碼學(xué)的基本概念及簡單加解密算法。教學(xué)重點(diǎn)

1、密碼系統(tǒng)模型，密碼系統(tǒng)的基本特性

2、對稱/非對稱密鑰系統(tǒng)3、簡單加解密算法及詞頻分析破解方法4、加密強(qiáng)度教學(xué)難點(diǎn)

1、對稱/非對稱密鑰系統(tǒng)2、簡單加解密算法及詞頻分析破解方法3、加密強(qiáng)度一、密碼學(xué)的基本概念密碼學(xué)(Cryptology)：研究信息系統(tǒng)安全保密的科學(xué)。它包含兩個(gè)分支，

密碼編碼學(xué)(Cryptography)，對信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的一門學(xué)問

密碼分析學(xué)(Cryptanalytics)，研究分析破譯密碼的學(xué)問。2024/5/93

幾個(gè)概念（一）2024/5/94

明文(消息)(Plaintext)：被隱蔽消息。密文(Ciphertext)或密報(bào)(Cryptogram)：明文經(jīng)密碼變換成的一種隱蔽形式。加密(Encryption)：將明文變換為密文的過程。解密(Decryption)：加密的逆過程，即由密文恢復(fù)出原明文的過程。加密員或密碼員(Cryptographer)：對明文進(jìn)行加密操作的人員。

幾個(gè)概念（二）2024/5/95

加密算法(Encryptionalgorithm)：密碼員對明文進(jìn)行加密時(shí)所采用的一組規(guī)則。(替換法,變換法)接收者(Receiver)：傳送消息的預(yù)定對象。解密算法：接收者對密文進(jìn)行解密時(shí)所采用的一組規(guī)則。密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機(jī)密信息。幾個(gè)概念（三）2024/5/96

密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。密碼分析員(Cryptanalyst)：從事密碼分析的人。被動攻擊(Passiveattack)：對一個(gè)保密系統(tǒng)采取截獲密文進(jìn)行分析的攻擊。主動攻擊(Activeattack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達(dá)到利已害人的目的。保密系統(tǒng)模型2024/5/97信源Mm加密器解密器接收者m非法接入者搭線信道（主動攻擊）C’搭線信道（被動攻擊）密碼分析員m‘密鑰源K1k1密鑰源K2k2密鑰信道

保密系統(tǒng)應(yīng)當(dāng)滿足的要求系統(tǒng)即使達(dá)不到理論上是不可破的，即pr{m’=m}=0，也應(yīng)當(dāng)為實(shí)際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計(jì)算上是不可行的。系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。加密和解密算法適用于所有密鑰空間中的元素。系統(tǒng)便于實(shí)現(xiàn)和使用。2024/5/98認(rèn)證與認(rèn)證系統(tǒng)認(rèn)證系統(tǒng)(Authenticationsystem)

防止消息被竄改、刪除、重放和偽造的一種有效方法,使發(fā)送的消息具有被驗(yàn)證的能力，使接收者或第三者能夠識別和確認(rèn)消息的真?zhèn)?。?shí)現(xiàn)這類功能的密碼系統(tǒng)稱作認(rèn)證系統(tǒng)保密性

保密性是使截獲者在不知密鑰條件下不能解讀密文的內(nèi)容。認(rèn)證性使任何不知密鑰的人不能構(gòu)造一個(gè)密報(bào)，使意定的接收者解密成一個(gè)可理解的消息(合法的消息)。2024/5/99安全認(rèn)證系統(tǒng)應(yīng)滿足下述條件意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性和真實(shí)性。消息的發(fā)送者對所發(fā)送的消息不能抵賴。除了合法消息發(fā)送者外，其它人不能偽造合法的消息。而且在已知合法密文c和相應(yīng)消息m下，要確定加密密鑰或系統(tǒng)地偽造合法密文在計(jì)算上是不可行的。必要時(shí)可由第三者作出仲裁。2024/5/910完整性(integrity)

在有自然和人為干擾條件下，系統(tǒng)保持檢測錯(cuò)誤和恢復(fù)消息和原來發(fā)送消息一致性的能力。實(shí)際中常常借助于糾、檢錯(cuò)技術(shù)和雜湊技術(shù)來保證消息的完整性。2024/5/911二、密碼體制分類密碼體制有2大類：單鑰體制(One-keysystem)：加密密鑰和解密密鑰相同。雙鑰體制(Twokeysystem)：加密密鑰和解密密鑰不同。2024/5/912密碼體制分類單鑰體制2024/5/913加密器EK解密器DK密文明文明文K密鑰產(chǎn)生器K密碼體制分類單鑰體制單鑰體制主要研究問題：密鑰產(chǎn)生(Keygeneration)，密鑰管理(Keymanagement)。分類：流密碼(Streamcipher)分組密碼(Blockcipher)單鑰體制不僅可用于數(shù)據(jù)加密，也可用于消息的認(rèn)證。2024/5/914密碼體制分類雙鑰體制雙鑰體制或公鑰體制(Publickeysystem)(Diffie和Hellman,1976)

每個(gè)用戶都有一對選定的密鑰(公鑰k1；私鑰k2)，公開的密鑰k1可以像電話號碼一樣進(jìn)行注冊公布。2024/5/915公鑰體制的主要特點(diǎn)加密和解密能力分開可以實(shí)現(xiàn)多個(gè)用戶加密的消息只能由一個(gè)用戶解讀（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）只能由一個(gè)用戶加密消息而使多個(gè)用戶可以解讀（可用于認(rèn)證系統(tǒng)中對消息進(jìn)行數(shù)字簽字）。無需事先分配密鑰。2024/5/916三、密碼分析

2024/5/917截收者在不知道解密密鑰及通信者所采用的加密體制的細(xì)節(jié)條件下，對密文進(jìn)行分析，試圖獲取機(jī)密信息。研究分析解密規(guī)律的科學(xué)稱作密碼分析學(xué)。密碼分析在外交、軍事、公安、商業(yè)等方面都具有重要作用，也是研究歷史、考古、古語言學(xué)和古樂理論的重要手段之一。密碼分析

2024/5/918密碼設(shè)計(jì)和密碼分析是共生的、又是互逆的，兩者密切有關(guān)但追求的目標(biāo)相反。兩者解決問題的途徑有很大差別

密碼設(shè)計(jì)是利用數(shù)學(xué)來構(gòu)造密碼密碼分析除了依靠數(shù)學(xué)、工程背景、語言學(xué)等知識外，還要靠經(jīng)驗(yàn)、統(tǒng)計(jì)、測試、眼力、直覺判斷能力……，有時(shí)還靠點(diǎn)運(yùn)氣。密碼分析方法--窮舉破譯法

2024/5/919

對截收的密報(bào)依次用各種可解的密鑰試譯，直到得到有意義的明文；或在不變密鑰下，對所有可能的明文加密直到得到與截獲密報(bào)一致為止，此法又稱為完全試湊法(Completetrial-and-errorMethod)。只要有足夠多的計(jì)算時(shí)間和存儲容量，原則上窮舉法總是可以成功的。但實(shí)際中，任何一種能保障安全要求的實(shí)用密碼都會設(shè)計(jì)得使這一方法在實(shí)際上是不可行的。

密碼分析方法—分析法

2024/5/920

確定性分析法利用一個(gè)或幾個(gè)已知量(比如，已知密文或明文-密文對)用數(shù)學(xué)關(guān)系式表示出所求未知量(如密鑰等)。已知量和未知量的關(guān)系視加密和解密算法而定，尋求這種關(guān)系是確定性分析法的關(guān)鍵步驟。

統(tǒng)計(jì)分析法利用明文的已知統(tǒng)計(jì)規(guī)律進(jìn)行破譯的方法。密碼破譯者對截收的密文進(jìn)行統(tǒng)計(jì)分析，總結(jié)出其間的統(tǒng)計(jì)規(guī)律，并與明文的統(tǒng)計(jì)規(guī)律進(jìn)行對照比較，從中提取出明文和密文之間的對應(yīng)或變換信息。

密碼可能經(jīng)受的攻擊攻擊類型攻擊者擁有的資源惟密文攻擊加密算法截獲的部分密文已知明文攻擊加密算法，截獲的部分密文和相應(yīng)的明文選擇明文攻擊加密算法加密黑盒子，可加密任意明文得到相應(yīng)的密文選擇密文攻擊加密算法解密黑盒子，可解密任意密文得到相應(yīng)的明文2024/5/921無條件安全和計(jì)算安全

2024/5/922無條件安全

如果算法產(chǎn)生的密文不能給出唯一決定相應(yīng)明文的足夠信息，無論截獲多少密文，花費(fèi)多少時(shí)間都不能解密密文。

Shannon指出，僅當(dāng)密鑰至少和明文一樣長時(shí)達(dá)到無條件安全（即一次一密）

計(jì)算安全

破譯密文的代價(jià)超過被加密信息的價(jià)值破譯密文所花時(shí)間超過信息的有效期替換加密方法愷撒加密法朱利葉斯.愷撒發(fā)明的。每一個(gè)字母用字母表中的該字母后的第三個(gè)字母代替愷撒移位密碼舉例明文：ILOVEYOU密文：LORYHBRX改進(jìn)的愷撒加密法可以后面1-25個(gè)字母進(jìn)行替換，不一定是3個(gè)字母。破解只要嘗試26次就能實(shí)現(xiàn)進(jìn)一步改進(jìn)愷撒加密法單字母替換密碼（單碼加密法）例如明碼表ABCDEFGHIJKLMNOPQRSTUVWXYZ

密碼表QWERTYUIOPASDFGHJKLZXCVBNM

明文FOREST

密文YGKTLZ

單碼加密的破解從數(shù)學(xué)上來將26*25*24*…*2*1種組合破解計(jì)算量非常大有沒有其他辦法？單碼加密的破解詞頻分析法9世紀(jì)的科學(xué)家阿爾·金迪在《關(guān)于破譯加密信息的手稿》“如果我們知道一條加密信息所使用的語言，那么破譯這條加密信息的方法就是找出同樣的語言寫的一篇其他文章，大約一頁紙長，然后我們計(jì)算其中每個(gè)字母的出現(xiàn)頻率。我們將頻率最高的字母標(biāo)為1號，頻率排第2的標(biāo)為2號，第三標(biāo)為3號，依次類推，直到數(shù)完樣品文章中所有字母。然后我們觀察需要破譯的密文，同樣分類出所有的字母，找出頻率最高的字母，并全部用樣本文章中最高頻率的字母替換。第二高頻的字母用樣本中2號代替，第三則用3號替換，直到密文中所有字母均已被樣本中的字母替換?！?/p>

詞頻分析法設(shè)密者后來針對頻率分析技術(shù)對以前的設(shè)密方法做了些改進(jìn)，比如說引進(jìn)空符號等，目的是為了打破正常的字母出現(xiàn)頻率。但是小的改進(jìn)已經(jīng)無法掩蓋單字母替換法的巨大缺陷了。到16世紀(jì)，最好的密碼破譯師已經(jīng)能夠破譯當(dāng)時(shí)大多數(shù)的加密信息。詞頻分析法的局限性短文可能嚴(yán)重偏離標(biāo)準(zhǔn)頻率，加入文章少于100個(gè)字母，那么對它的解密就會比較困難。不是所有文章都適用標(biāo)準(zhǔn)頻度1969年，法國作家喬治斯·佩雷克寫了一部200頁的小說《逃亡》，其中沒有一個(gè)含有字母e的單詞。更令人稱奇的是英國小說家和拼論家吉爾伯特·阿代爾成功地將《逃亡》翻譯成英文，而且其中也沒有一個(gè)字母e。阿代爾將這部譯著命名為《真空》。如果這本書用單密碼表進(jìn)行加密，那么頻度分析破解它會受到很大的困難。

多密碼表加密法為了解決詞頻分析問題維熱納爾(BlaisedeVigenere)于16世紀(jì)末確立其密碼不再用一個(gè)密碼表來加密，而是使用了26個(gè)不同的密碼表變換加密技術(shù)對明文進(jìn)行某種置換柵欄加密技術(shù)明文“Comehometomorrow”Cmhmtmrooeoeoorw密文”Cmhmtmrooeoeoorw”Cmhmtmrooeoeoorw簡單分欄式變換加密技術(shù)基本方法一行行寫，一列列讀明文“Comehometomorrow”密文”Cmroermtoeowhmoo”如果列讀的順序再變一下，352146得密文“mtohmoerCmreowoo”很容易破解第一列第二列第三列第四列第五列第六列Comehometomorrow多輪簡單分欄變換加密技術(shù)簡單分欄變換加密變換多次，從而增加復(fù)雜性明文“Comehometomorrow”352146得密文“mtohmoerCmreowoo”以“mtohmoerCmreowoo”為明文再做若干次。第一列第二列第三列第四列第五列第六列Comehometomorrow多輪簡單分欄變換加密技術(shù)第二輪明文“mtohmoerCmreowoo”352146得密文“oComrtrwmeohmooe”以“oComrtrwmeohmooe”為明文再做若干次。輪次越多，復(fù)雜度越高第一列第二列第三列第四列第五列第六列mtohmoerCmreowooVernam加密Vernam加密法也稱一次性板(One-Time-Pad)，用隨機(jī)的非重復(fù)的字符集合作為輸出密文。1.明文:

H

O

W

A

R

E

Y

O

U

7

14

22

0

17

4

24

14

20

+

2.密鑰

N

C

B

T

Z

Q

A

R

X

13

2

1

19

25

16

0

17

23

3.初始和

20

16

23

19

42

20

24

31

43

4.大于25則減去26

20

16

23

19

16

20

24

5

17

5.密文

U

Q

X

T

Q

U

Y

F

R

由于一次性板用完就要放棄,因此這個(gè)技術(shù)相當(dāng)安全,適合少量明文消息,但是對大消息是行不通的(一次性板稱為密鑰(Key),并且明文有多長,密鑰就有多長,因此對于大消息行不通).Vernam加密法最初是AT&T公司借助所謂的Vernam機(jī)實(shí)現(xiàn)的.

對稱密鑰發(fā)布問題加密和解密密鑰是一樣的如何將解密密鑰安全發(fā)送給接收方？二戰(zhàn)德國在使用ENIGMA密碼機(jī)時(shí)也是對稱密鑰。采用的辦法就是每天更新密碼，在發(fā)送新密電前，用老的密鑰加密新的密鑰。所以盟軍總能收到短的密電，但初期還是沒有辦法破譯對稱密鑰密碼系統(tǒng)的密鑰數(shù)兩個(gè)人——只要一個(gè)密鑰三個(gè)人——要三個(gè)密鑰四個(gè)人——要4*3/2個(gè)五個(gè)人——要5*4*3/2個(gè)N個(gè)人——要個(gè)，即N*(N-1)/2!如果有1000人參加，那么就需要499500個(gè)密鑰。這個(gè)數(shù)字就太大了。Diffie-Hellman密鑰見換協(xié)議/算法為了解決對稱密鑰交換問題WhitefieldDiffie與MartinHellman在1976年提出了這套奇妙的密鑰交換協(xié)議。可以讓需要安全通信的雙方確定對稱密鑰。這個(gè)方法只是為了解決密鑰交換，不能做加/解密。Diffie-Hellman算法描述Alice和Bob兩個(gè)人要確定密鑰Alice發(fā)送兩個(gè)大的素?cái)?shù)n,g給Bob同時(shí)Alice另選擇大隨機(jī)數(shù)x，并計(jì)算Alice將A發(fā)給BobBob選擇大隨機(jī)數(shù)y，并計(jì)算Bob將B發(fā)給AliceAlice計(jì)算密鑰Bob計(jì)算密鑰可證明K1=K2Diffie-Hellman算法舉例Alice選擇n=11,g=7，并將這兩個(gè)數(shù)告訴BobAlice選擇x=3，則Bob選擇y=6，則Alice得到B，并計(jì)算Bob得到A，并計(jì)算Diffie-Hellman算法理論基礎(chǔ)仔細(xì)想想，Alice和Bob交換了什么信息？n,g,A,B而n和g是公開的。只要知道x和y就能求出密鑰。現(xiàn)在的問題是對方還知道A和B需要用A,B,n,g求出下列方程組中的x和y.當(dāng)g,n非常大，要求x,y是非常復(fù)雜的。有多大呢？復(fù)雜度真的那么大嗎?當(dāng)g,n非常大，要求x,y是非常復(fù)雜的。有多大呢？舉例且g,n會非常大!Diffie-Hellman算法問題這個(gè)方法是否萬無一失呢？不是！存在中間人攻擊或桶隊(duì)攻擊可分別計(jì)算各自的A，BAliceTomBobn=11,g=7n=11,g=7n=11,g=7x=3x=8,y=6y=9AliceTomBobA=2B=4A=9B=8Diffie-Hellman算法問題交換A，B分別計(jì)算各自的K產(chǎn)生的結(jié)果，Alice和Bob以為是直接和對方通信，結(jié)果被中間人Tom翻譯了。AliceTomBobA=2B=4A=2B=4A=9B=8A=9B=8AliceTomBobB=4K1=9A=2K1=9B=8K2=5A=9K2=5非對稱密鑰的密鑰數(shù)對稱密鑰的密鑰數(shù)N*(N-1)/2!非對稱密鑰呢?非對稱密鑰就是加密和解密不是同一個(gè)密鑰。加密密鑰可以公開（公鑰），實(shí)際也可做解密解密密鑰不公開（私鑰），當(dāng)然也可以做加密既一個(gè)做加密，一個(gè)就做解密。通常公開的做加密，私有的來解密。這樣其他人就不能解開信息。有N個(gè)人加入通信，非對稱密鑰對為N個(gè)。明顯少得多。夾帶加密法將要保密的信息放在另一個(gè)信息中隱形墨水在某個(gè)字符上加上小標(biāo)記在書寫字符之間稍做變化手寫字符上使用鉛筆標(biāo)記等。圖形夾帶秘密信息將圖形每個(gè)字節(jié)最右邊兩位換成密碼消息位。圖形變化不大。但夾帶了秘密。圖形夾帶信息摘要，驗(yàn)證圖象是否經(jīng)人篡改。密鑰范圍與密鑰長度密碼分析員知道如下信息加/解密算法密文（信道監(jiān)聽得到）密鑰的長度知識（即密鑰的取值范圍，比如0-1000億）如何破解，只要用0-1000億的值做密鑰，通過解密算法計(jì)算明文，如果明文可讀。（暴力破解）最好的情況，最差的情況，平均情況密鑰范圍與密鑰長度如果密鑰的范圍為0-1000億而攻擊者只要五分鐘就破解了密鑰。但你又希望