第6講-經(jīng)典密碼學(xué)分析課件

第6講經(jīng)典密碼學(xué)古典加密算法分組加密算法第6講經(jīng)典密碼學(xué)古典加密算法1密碼學(xué)相關(guān)術(shù)語(yǔ)密碼編碼學(xué)(cryptography)是密碼體制的設(shè)計(jì)學(xué)，而密碼分析學(xué)(cryptanalysis)則是在未知密鑰的情況下從密文推演出明文或密鑰的技術(shù)。密碼編碼學(xué)與密碼分析學(xué)合起來(lái)即為密碼學(xué)(cryptology)。如果不論截取者獲得了多少密文，但在密文中都沒有足夠的信息來(lái)惟一地確定出對(duì)應(yīng)的明文，則這一密碼體制稱為無(wú)條件安全的，或稱為理論上是不可破的。如果密碼體制中的密碼不能被可使用的計(jì)算資源破譯，則這一密碼體制稱為在計(jì)算上是安全的。密碼學(xué)相關(guān)術(shù)語(yǔ)密碼編碼學(xué)(cryptography)是密碼體2基本術(shù)語(yǔ)使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)（cryptography），從事此行業(yè)的叫做密碼編碼者（cryptographer），密碼分析者（cryptanalyst）是從事密碼分析的專業(yè)人員，密碼分析學(xué)（cryptanalysis）就是破譯密文的科學(xué)和技術(shù)。密碼學(xué)（cryptology）作為數(shù)學(xué)的一個(gè)分支，包括密碼編碼學(xué)和密碼分析學(xué)兩部分。基本術(shù)語(yǔ)使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)（cryptog3基本術(shù)語(yǔ)(續(xù))消息被稱為明文(Plaintext)，用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密(Encrtption)，被加密的消息稱為密文(Ciphertext)，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密(Decryption)

密碼算法(CryptographyAlgorithm):是用于加密和解密的數(shù)學(xué)函數(shù)發(fā)送者對(duì)明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm)接收者對(duì)密文解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm)基本術(shù)語(yǔ)(續(xù))消息被稱為明文(Plaintext)，用某種方4加解密過程示意圖加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的,分別稱為加密密鑰(EncryptionKey)

和解密密鑰(DecryptionKey)明文明文密文加密算法解密算法加密密鑰解密密鑰加解密過程示意圖加密和解密算法的操作通常都是在一組密鑰的控5一般的數(shù)據(jù)加密模型E加密算法D解密算法加密密鑰K解密密鑰K明文X明文X密文Y=EK(X)截取者截獲篡改密鑰源安全信道一般的數(shù)據(jù)加密模型ED加密密鑰K解密密鑰K明文X明文6密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）*（4）任意k∈K,有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函數(shù)，滿足dk(ek(x))=x,這里x∈P。密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條7密碼分析密碼分析學(xué)，是攻擊者在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。對(duì)密碼進(jìn)行分析的嘗試稱為攻擊（Attack)。攻擊密碼的方法：窮舉法，又稱強(qiáng)力法（Brute-force）分析法密碼分析密碼分析學(xué)，是攻擊者在不知道密鑰的情況下，恢復(fù)出明文8密碼分析Kerchkhoff原則假設(shè)攻擊者是在已經(jīng)密碼體制的前提下來(lái)破譯密碼系統(tǒng)的密鑰；最常見的破解類型如下：唯密文攻擊：攻擊者有一些密文，它們是使用同一加密算法和同一密鑰加密的；已知明文攻擊：攻擊者不但得到一些密文，而且能夠得到這些密文對(duì)應(yīng)的明文；密碼分析Kerchkhoff原則9密碼分析3選擇明文攻擊：攻擊者不僅得到一些密文和明文，而且能選擇用于加密的明文；4選擇密文攻擊：攻擊者可以選擇不同的密文來(lái)解密，并能夠得到解密后的明文；這一切的目的都是：破譯出密鑰一般說來(lái)：密碼系統(tǒng)應(yīng)該經(jīng)得起已知明文的攻擊。如果攻擊者無(wú)論得到多少密文，都沒有足夠的信息去恢復(fù)明文，則密碼系統(tǒng)是無(wú)條件安全的。理論上，只有一次一密的系統(tǒng)才能真正實(shí)現(xiàn)。密碼分析3選擇明文攻擊：10古典密碼--信息隱藏Youcan'tunderstandYoucan'tunderstandSteganography也稱隱寫術(shù)：將秘密消息隱藏在其他消息中。隱形墨水，字符上的針眼，手寫字符的差異，字符上的鉛筆記號(hào)等圖象中隱寫：用消息位代替圖象的每個(gè)字節(jié)的最不重要的位，而肉眼無(wú)法看出差異；隱寫術(shù)不使用算法或者密鑰古典密碼--信息隱藏Youcan'tunderstand11Steganography(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.Steganography(a)Threezebras121.移位密碼體制(單字母)設(shè)P=C=K=Z/(26),對(duì),定義同時(shí)dk(y)=y-k(mod26)注1*：26個(gè)英文字母與模26剩余類集合{0,….,25}建立一一對(duì)應(yīng)：ABCDEFGHIJKLMNOPQRSTUVWXYZ012345678910111213141516171819202122232425

2*.當(dāng)k=3時(shí)，為Caesar密碼：若明文：caesarcipher

密文：FDHVDUFLSKHU

實(shí)際算法為：有

同時(shí)有，d3(y)=y-3(mod26)1.移位密碼體制(單字母)設(shè)P=C=K=Z/(26),對(duì)133*.一個(gè)密碼體制要是實(shí)際可用必須滿足的特性每一個(gè)加密函數(shù)ek和每一個(gè)解密函數(shù)dk都能有效地計(jì)算。破譯者取得密文后，將不能在有效的時(shí)間內(nèi)破解出密鑰k或明文x。一個(gè)密碼體制是安全的必要條件窮舉密鑰搜索將是不可行的，即密鑰空間將是非常大的。3*.一個(gè)密碼體制要是實(shí)際可用必須滿足的特性每一個(gè)加密函數(shù)e14移位密碼移位密碼(substitutioncipher)的原理可用一個(gè)例子來(lái)說明。（密鑰是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文c變成了密文F移位密碼移位密碼(substitutioncipher)的15移位密碼移位密碼(substitutioncipher)的原理可用一個(gè)例子來(lái)說明。（密鑰是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文a變成了密文D移位密碼移位密碼(substitutioncipher)的16移位密碼移位密碼(substitutioncipher)的原理可用一個(gè)例子來(lái)說明。（密鑰是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文e變成了密文H移位密碼移位密碼(substitutioncipher)的17凱撒密碼的改進(jìn)凱撒密碼只有25個(gè)密鑰k，非常不安全；若有意改變字母的排列順序，可增大密鑰空間；例如：使用密鑰KeyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopgrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectacularbdfghijkmnoqvwxyz泄露給破譯者的信息更少；凱撒密碼的改進(jìn)凱撒密碼只有25個(gè)密鑰k，非常不安全；182.替換密碼體制設(shè)P=C=Z/(26)，K是由26個(gè)符號(hào)0，1,..,25的所有可能置換組成。任意，定義

dπ(y)=-1(y)=x,π-1是π的逆置換。

注：1*.置換π的表示：

2*密鑰空間K很大，|K|=26!≈4×1026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計(jì)的方式破譯它。3*移位密碼體制是替換密碼體制的一個(gè)特例，它僅含26個(gè)置換做為密鑰空間2.替換密碼體制設(shè)P=C=Z/(26)，K是由26個(gè)符號(hào)0，193.仿射密碼體制替換密碼的另一個(gè)特例就是仿射密碼。加密函數(shù)取形式為

要求唯一解的充要條件是gcd(a,26)=1

該體制描述為：

設(shè)P=C=Z/(26)

對(duì)

定義ek(x)=ax+b(mod26)

dk(y)=a-1(y-b)(mod26)

3.仿射密碼體制替換密碼的另一個(gè)特例就是仿射密碼。20例子，設(shè)k＝（7，3），注意到7-1(mod26)=15,加密函數(shù)是ek(x)=7x+3,相應(yīng)的解密函數(shù)是dk(y)=15(y-3)=15y-19,易見dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先轉(zhuǎn)換字母h,o,t成為數(shù)字7,14,19,然后加密：解密：例子，設(shè)k＝（7，3），注意到7-1(mod26)=15,21英文中字母的使用頻率02468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ頻率E使用最多；然后是TRNIOAS其他字母使用較少最少的是JKQXZ英文中字母的使用頻率02468101214ABCDEFGH224.維吉尼亞密碼(Vigenere,多字母)設(shè)m為一固定的正整數(shù)，定義P=C=K=(Z/(26))m,對(duì)一個(gè)密鑰K＝（k1,k2,…,km),定義ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y

dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=x這里的所有的運(yùn)算都是在（mod26)中進(jìn)行的。4.維吉尼亞密碼(Vigenere,多字母)設(shè)m為一固定的23維基尼亞密碼（Vigenere）-示例若密鑰字為deceptive，即m=9明文wearediscoveredsav的加密過程：明文：wearediscoeredsav密鑰：deceptivedeceptive密文：ZICVTWQNGRZGVTWAVZ密鑰字母d對(duì)應(yīng)數(shù)字3，因而明文字母w在密鑰字母d的作用下向后移位3，得到密文字母Z。依次類推；維基尼亞密碼（Vigenere）-示例若密鑰字為decept24維基尼亞密碼（Vigenere）維基尼亞密碼是多表替換體制，分析起來(lái)更加困難。密鑰空間大，可能的密鑰字達(dá)26m

如果秘要字的長(zhǎng)度是m，明文中的一個(gè)字母能夠映射成這m個(gè)可能的字母中的一個(gè)；例如，當(dāng)m=5，密鑰空間所含密鑰的數(shù)量是>1.1x107

明文和密文的字母頻率分布相同，仍然能使用統(tǒng)計(jì)分析破譯維基尼亞密碼（Vigenere）維基尼亞密碼是多表替換體制，255.Hill密碼體制設(shè)ｍ為某個(gè)固定的正整數(shù)，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩陣}對(duì)每一個(gè),定義ek(x)=xk(mod26)和dk(y)=yk-1(mod26)注：明文與密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)為同余類環(huán)。在這個(gè)環(huán)上的可逆矩陣Amxm,是指行列式detAmxm的值∈Z*/(26),它為Z/(26)中全體可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，

Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}例子：當(dāng)m=2時(shí)，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

k

5.Hill密碼體制設(shè)ｍ為某個(gè)固定的正整數(shù)，P=C=(Z/(26事實(shí)上yi為x1,x2的線性組合，y1=11x1+3x2;y2=8x1+7x2，一般，將取m×m的矩陣K作為我們的密鑰：有

y=(y1,y2,…,ym,)=(x1,x2,…,

xm)

換言之，y=xK;且有x=yK-1若K=,可得K-1=若對(duì)明文july加密，它分成2個(gè)元素（j,u),(l,y),分別對(duì)應(yīng)于（9,20）,（11,24）,有事實(shí)上yi為x1,x2的線性組合，y1=11x1+3x2;y27（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是對(duì)july加密的結(jié)果為DELW。為了解密，Bob計(jì)算

且因此，得到了正確的明文“july”

（9,20）＝（99＋60,72＋140286.置換密碼體制

設(shè)m為固定的正整數(shù)，P=C=(Z/(26))m,K是由{1,2,..,m}的所有置換構(gòu)成，對(duì)一個(gè)密鑰π∈K，定義eπ(x1,x2,..,xm)=(xπ(1),,..,xπ(m))和

dπ(y1,y2,..,ym)=(yπ(1),,..,yπ(m))這里π－1為π的逆置換。注：這里的加密與解密僅僅用了置換，無(wú)代數(shù)運(yùn)算。例子：設(shè)m=6,取密鑰

而6.置換密碼體制 設(shè)m為固定的正整數(shù)，P=C=(Z/(2629若給定的明文是：cryptography首先找分成6個(gè)字母長(zhǎng)的明文組：crypto|graphy求得的密文是：YTCOPRAHGYPR注：事實(shí)上，置換密碼是Hill密碼的特例。給定一個(gè)集合{1,2,..,m}的置換矩陣

(置換矩陣是每一行和每一列剛好在一個(gè)“1”，而其余元素為“0”的矩陣。)請(qǐng)同學(xué)們驗(yàn)證若給定的明文是：cryptography首先找分成6個(gè)字母30對(duì)上面例子決定的置換π對(duì)應(yīng)：對(duì)上面例子決定的置換π對(duì)應(yīng)：31CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc32CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc33CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc34CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc35CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc36CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc37CIPHER145326attackbeginsatfour密文的得出密鑰順序明文先讀順序?yàn)?的明文列，即aba

CIPHER密文的得出密鑰先讀順序?yàn)?的明文列，即ab38CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即cnu

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即cn39CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即aio

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即ai40CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即tet

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即te41CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即tgf

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即tg42CIPHER145326attackbeginsatfour密文的得出密鑰順序明文最后讀順序?yàn)?的明文列，即ksr

因此密文就是：abacnuaiotettgfksr

CIPHER密文的得出密鑰最后讀順序?yàn)?的明文列，即k43CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文先寫下第1列密文aba

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列寫下密鑰先寫下第1列密文44CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第2列密文cnu

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列寫下密鑰再寫下第2列密文45CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第3列密文aio

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列寫下密鑰再寫下第3列密文46CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第4列密文tet

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列寫下密鑰再寫下第4列密文47CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第5列密文tgf

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列寫下密鑰再寫下第5列密文48CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文最后寫下第6列密文ksr

收到的密文：abacnuaiotettgfksr

CIPHER接收端收到密文后按列寫下密鑰最后寫下第6列密49CIPHER145326attackbeginsatfour接收端從密文解出明文密鑰順序明文最后按行讀出明文收到的密文：abacnuaiotettgfksr

CIPHER接收端從密文解出明文密鑰最后按行讀出明文收到的密50CIPHER145326attackbeginsatfour接收端從密文解出明文密鑰順序明文最后按行讀出明文收到的密文：abacnuaiotettgfksr

CIPHER接收端從密文解出明文密鑰最后按行讀出明文收到的密51CIPHER145326attackbeginsatfour接收端從密文解出明文密鑰順序明文最后按行讀出明文收到的密文：abacnuaiotettgfksr

得出明文：attackbeginsatfour

CIPHER接收端從密文解出明文密鑰最后按行讀出明文收到的密527.置換密碼(柵欄技術(shù))最簡(jiǎn)單的例子是柵欄技術(shù)：按照對(duì)角線的順序?qū)懭朊魑?，而按行的順序讀出作為密文。明文：meetmeaftertheparty寫為：mematrhpryetefeteat密文：mematrhpryetefeteat7.置換密碼(柵欄技術(shù))最簡(jiǎn)單的例子是柵欄技術(shù)：按照對(duì)角線的53古典密碼小結(jié)研究古典密碼原理，對(duì)于理解、構(gòu)造和分析現(xiàn)代密碼是十分有益的。古典密碼小結(jié)54序列密碼與分組密碼序列碼體制是將明文X看成是連續(xù)的比特流(或字符流)x1x2…，并且用密鑰序列

Kk1k2…中的第i個(gè)元素ki對(duì)明文中的xi進(jìn)行加密，即序列密碼與分組密碼序列碼體制是將明文X看成是連續(xù)的比特55序列密碼體制密鑰序列產(chǎn)生器種子

I0發(fā)端ki密鑰序列產(chǎn)生器種子

I0收端ki密文序列明文序列明文序列xixiyiyi在開始工作時(shí)種子I0對(duì)密鑰序列產(chǎn)生器進(jìn)行初始化。按照模2進(jìn)行運(yùn)算，得出：

(9-1)序列密碼體制密鑰序列產(chǎn)生器種子發(fā)端ki密鑰序列產(chǎn)生器種子收56序列密碼體制密鑰序列產(chǎn)生器種子

I0發(fā)端ki密鑰序列產(chǎn)生器種子

I0收端ki密文序列明文序列明文序列xixiyiyi在收端，對(duì)yi的解密算法為：(9-2)序列密碼又稱為密鑰流密碼。序列密碼體制密鑰序列產(chǎn)生器種子發(fā)端ki密鑰序列產(chǎn)生器種子收57序列密碼體制的保密性序列密碼體制的保密性完全在于密鑰的隨機(jī)性。如果密鑰是真正的隨機(jī)數(shù)，則這種體制就是理論上不可破的。這也可稱為一次一密亂碼本體制。嚴(yán)格的一次一密亂碼本體制所需的密鑰量不存在上限，很難實(shí)用化。密碼學(xué)家試圖模仿這種一次一密亂碼本體制。目前常使用偽隨機(jī)序列作為密鑰序列。關(guān)鍵是序列的周期要足夠長(zhǎng)，且序列要有很好的隨機(jī)性（這很難尋找）。序列密碼體制的保密性序列密碼體制的保密性完全在于密鑰的隨機(jī)58第6講經(jīng)典密碼學(xué)古典加密算法分組加密算法第6講經(jīng)典密碼學(xué)古典加密算法59密碼學(xué)相關(guān)術(shù)語(yǔ)密碼編碼學(xué)(cryptography)是密碼體制的設(shè)計(jì)學(xué)，而密碼分析學(xué)(cryptanalysis)則是在未知密鑰的情況下從密文推演出明文或密鑰的技術(shù)。密碼編碼學(xué)與密碼分析學(xué)合起來(lái)即為密碼學(xué)(cryptology)。如果不論截取者獲得了多少密文，但在密文中都沒有足夠的信息來(lái)惟一地確定出對(duì)應(yīng)的明文，則這一密碼體制稱為無(wú)條件安全的，或稱為理論上是不可破的。如果密碼體制中的密碼不能被可使用的計(jì)算資源破譯，則這一密碼體制稱為在計(jì)算上是安全的。密碼學(xué)相關(guān)術(shù)語(yǔ)密碼編碼學(xué)(cryptography)是密碼體60基本術(shù)語(yǔ)使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)（cryptography），從事此行業(yè)的叫做密碼編碼者（cryptographer），密碼分析者（cryptanalyst）是從事密碼分析的專業(yè)人員，密碼分析學(xué)（cryptanalysis）就是破譯密文的科學(xué)和技術(shù)。密碼學(xué)（cryptology）作為數(shù)學(xué)的一個(gè)分支，包括密碼編碼學(xué)和密碼分析學(xué)兩部分。基本術(shù)語(yǔ)使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)（cryptog61基本術(shù)語(yǔ)(續(xù))消息被稱為明文(Plaintext)，用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密(Encrtption)，被加密的消息稱為密文(Ciphertext)，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密(Decryption)

密碼算法(CryptographyAlgorithm):是用于加密和解密的數(shù)學(xué)函數(shù)發(fā)送者對(duì)明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm)接收者對(duì)密文解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm)基本術(shù)語(yǔ)(續(xù))消息被稱為明文(Plaintext)，用某種方62加解密過程示意圖加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的,分別稱為加密密鑰(EncryptionKey)

和解密密鑰(DecryptionKey)明文明文密文加密算法解密算法加密密鑰解密密鑰加解密過程示意圖加密和解密算法的操作通常都是在一組密鑰的控63一般的數(shù)據(jù)加密模型E加密算法D解密算法加密密鑰K解密密鑰K明文X明文X密文Y=EK(X)截取者截獲篡改密鑰源安全信道一般的數(shù)據(jù)加密模型ED加密密鑰K解密密鑰K明文X明文64密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）*（4）任意k∈K,有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函數(shù)，滿足dk(ek(x))=x,這里x∈P。密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條65密碼分析密碼分析學(xué)，是攻擊者在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。對(duì)密碼進(jìn)行分析的嘗試稱為攻擊（Attack)。攻擊密碼的方法：窮舉法，又稱強(qiáng)力法（Brute-force）分析法密碼分析密碼分析學(xué)，是攻擊者在不知道密鑰的情況下，恢復(fù)出明文66密碼分析Kerchkhoff原則假設(shè)攻擊者是在已經(jīng)密碼體制的前提下來(lái)破譯密碼系統(tǒng)的密鑰；最常見的破解類型如下：唯密文攻擊：攻擊者有一些密文，它們是使用同一加密算法和同一密鑰加密的；已知明文攻擊：攻擊者不但得到一些密文，而且能夠得到這些密文對(duì)應(yīng)的明文；密碼分析Kerchkhoff原則67密碼分析3選擇明文攻擊：攻擊者不僅得到一些密文和明文，而且能選擇用于加密的明文；4選擇密文攻擊：攻擊者可以選擇不同的密文來(lái)解密，并能夠得到解密后的明文；這一切的目的都是：破譯出密鑰一般說來(lái)：密碼系統(tǒng)應(yīng)該經(jīng)得起已知明文的攻擊。如果攻擊者無(wú)論得到多少密文，都沒有足夠的信息去恢復(fù)明文，則密碼系統(tǒng)是無(wú)條件安全的。理論上，只有一次一密的系統(tǒng)才能真正實(shí)現(xiàn)。密碼分析3選擇明文攻擊：68古典密碼--信息隱藏Youcan'tunderstandYoucan'tunderstandSteganography也稱隱寫術(shù)：將秘密消息隱藏在其他消息中。隱形墨水，字符上的針眼，手寫字符的差異，字符上的鉛筆記號(hào)等圖象中隱寫：用消息位代替圖象的每個(gè)字節(jié)的最不重要的位，而肉眼無(wú)法看出差異；隱寫術(shù)不使用算法或者密鑰古典密碼--信息隱藏Youcan'tunderstand69Steganography(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.(a)Threezebrasandatree.(b)Threezebras,atree,andthecompletetextoffiveplaysbyWilliamShakespeare.Steganography(a)Threezebras701.移位密碼體制(單字母)設(shè)P=C=K=Z/(26),對(duì),定義同時(shí)dk(y)=y-k(mod26)注1*：26個(gè)英文字母與模26剩余類集合{0,….,25}建立一一對(duì)應(yīng)：ABCDEFGHIJKLMNOPQRSTUVWXYZ012345678910111213141516171819202122232425

2*.當(dāng)k=3時(shí)，為Caesar密碼：若明文：caesarcipher

密文：FDHVDUFLSKHU

實(shí)際算法為：有

同時(shí)有，d3(y)=y-3(mod26)1.移位密碼體制(單字母)設(shè)P=C=K=Z/(26),對(duì)713*.一個(gè)密碼體制要是實(shí)際可用必須滿足的特性每一個(gè)加密函數(shù)ek和每一個(gè)解密函數(shù)dk都能有效地計(jì)算。破譯者取得密文后，將不能在有效的時(shí)間內(nèi)破解出密鑰k或明文x。一個(gè)密碼體制是安全的必要條件窮舉密鑰搜索將是不可行的，即密鑰空間將是非常大的。3*.一個(gè)密碼體制要是實(shí)際可用必須滿足的特性每一個(gè)加密函數(shù)e72移位密碼移位密碼(substitutioncipher)的原理可用一個(gè)例子來(lái)說明。（密鑰是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文c變成了密文F移位密碼移位密碼(substitutioncipher)的73移位密碼移位密碼(substitutioncipher)的原理可用一個(gè)例子來(lái)說明。（密鑰是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文a變成了密文D移位密碼移位密碼(substitutioncipher)的74移位密碼移位密碼(substitutioncipher)的原理可用一個(gè)例子來(lái)說明。（密鑰是3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文e變成了密文H移位密碼移位密碼(substitutioncipher)的75凱撒密碼的改進(jìn)凱撒密碼只有25個(gè)密鑰k，非常不安全；若有意改變字母的排列順序，可增大密鑰空間；例如：使用密鑰KeyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopgrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectacularbdfghijkmnoqvwxyz泄露給破譯者的信息更少；凱撒密碼的改進(jìn)凱撒密碼只有25個(gè)密鑰k，非常不安全；762.替換密碼體制設(shè)P=C=Z/(26)，K是由26個(gè)符號(hào)0，1,..,25的所有可能置換組成。任意，定義

dπ(y)=-1(y)=x,π-1是π的逆置換。

注：1*.置換π的表示：

2*密鑰空間K很大，|K|=26!≈4×1026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計(jì)的方式破譯它。3*移位密碼體制是替換密碼體制的一個(gè)特例，它僅含26個(gè)置換做為密鑰空間2.替換密碼體制設(shè)P=C=Z/(26)，K是由26個(gè)符號(hào)0，773.仿射密碼體制替換密碼的另一個(gè)特例就是仿射密碼。加密函數(shù)取形式為

要求唯一解的充要條件是gcd(a,26)=1

該體制描述為：

設(shè)P=C=Z/(26)

對(duì)

定義ek(x)=ax+b(mod26)

dk(y)=a-1(y-b)(mod26)

3.仿射密碼體制替換密碼的另一個(gè)特例就是仿射密碼。78例子，設(shè)k＝（7，3），注意到7-1(mod26)=15,加密函數(shù)是ek(x)=7x+3,相應(yīng)的解密函數(shù)是dk(y)=15(y-3)=15y-19,易見dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先轉(zhuǎn)換字母h,o,t成為數(shù)字7,14,19,然后加密：解密：例子，設(shè)k＝（7，3），注意到7-1(mod26)=15,79英文中字母的使用頻率02468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ頻率E使用最多；然后是TRNIOAS其他字母使用較少最少的是JKQXZ英文中字母的使用頻率02468101214ABCDEFGH804.維吉尼亞密碼(Vigenere,多字母)設(shè)m為一固定的正整數(shù)，定義P=C=K=(Z/(26))m,對(duì)一個(gè)密鑰K＝（k1,k2,…,km),定義ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y

dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=x這里的所有的運(yùn)算都是在（mod26)中進(jìn)行的。4.維吉尼亞密碼(Vigenere,多字母)設(shè)m為一固定的81維基尼亞密碼（Vigenere）-示例若密鑰字為deceptive，即m=9明文wearediscoveredsav的加密過程：明文：wearediscoeredsav密鑰：deceptivedeceptive密文：ZICVTWQNGRZGVTWAVZ密鑰字母d對(duì)應(yīng)數(shù)字3，因而明文字母w在密鑰字母d的作用下向后移位3，得到密文字母Z。依次類推；維基尼亞密碼（Vigenere）-示例若密鑰字為decept82維基尼亞密碼（Vigenere）維基尼亞密碼是多表替換體制，分析起來(lái)更加困難。密鑰空間大，可能的密鑰字達(dá)26m

如果秘要字的長(zhǎng)度是m，明文中的一個(gè)字母能夠映射成這m個(gè)可能的字母中的一個(gè)；例如，當(dāng)m=5，密鑰空間所含密鑰的數(shù)量是>1.1x107

明文和密文的字母頻率分布相同，仍然能使用統(tǒng)計(jì)分析破譯維基尼亞密碼（Vigenere）維基尼亞密碼是多表替換體制，835.Hill密碼體制設(shè)ｍ為某個(gè)固定的正整數(shù)，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩陣}對(duì)每一個(gè),定義ek(x)=xk(mod26)和dk(y)=yk-1(mod26)注：明文與密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)為同余類環(huán)。在這個(gè)環(huán)上的可逆矩陣Amxm,是指行列式detAmxm的值∈Z*/(26),它為Z/(26)中全體可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，

Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}例子：當(dāng)m=2時(shí)，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

k

5.Hill密碼體制設(shè)ｍ為某個(gè)固定的正整數(shù)，P=C=(Z/(84事實(shí)上yi為x1,x2的線性組合，y1=11x1+3x2;y2=8x1+7x2，一般，將取m×m的矩陣K作為我們的密鑰：有

y=(y1,y2,…,ym,)=(x1,x2,…,

xm)

換言之，y=xK;且有x=yK-1若K=,可得K-1=若對(duì)明文july加密，它分成2個(gè)元素（j,u),(l,y),分別對(duì)應(yīng)于（9,20）,（11,24）,有事實(shí)上yi為x1,x2的線性組合，y1=11x1+3x2;y85（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是對(duì)july加密的結(jié)果為DELW。為了解密，Bob計(jì)算

且因此，得到了正確的明文“july”

（9,20）＝（99＋60,72＋140866.置換密碼體制

設(shè)m為固定的正整數(shù)，P=C=(Z/(26))m,K是由{1,2,..,m}的所有置換構(gòu)成，對(duì)一個(gè)密鑰π∈K，定義eπ(x1,x2,..,xm)=(xπ(1),,..,xπ(m))和

dπ(y1,y2,..,ym)=(yπ(1),,..,yπ(m))這里π－1為π的逆置換。注：這里的加密與解密僅僅用了置換，無(wú)代數(shù)運(yùn)算。例子：設(shè)m=6,取密鑰

而6.置換密碼體制 設(shè)m為固定的正整數(shù)，P=C=(Z/(2687若給定的明文是：cryptography首先找分成6個(gè)字母長(zhǎng)的明文組：crypto|graphy求得的密文是：YTCOPRAHGYPR注：事實(shí)上，置換密碼是Hill密碼的特例。給定一個(gè)集合{1,2,..,m}的置換矩陣

(置換矩陣是每一行和每一列剛好在一個(gè)“1”，而其余元素為“0”的矩陣。)請(qǐng)同學(xué)們驗(yàn)證若給定的明文是：cryptography首先找分成6個(gè)字母88對(duì)上面例子決定的置換π對(duì)應(yīng)：對(duì)上面例子決定的置換π對(duì)應(yīng)：89CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc90CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc91CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc92CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc93CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc94CIPHER145326attackbeginsatfour置換密碼置換密碼(transpositioncipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。密鑰順序明文根據(jù)英文字母在26個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有A和B，因此C為第1。同理，E為第2，H為第3,……，R為第6。于是得出密鑰字母的相對(duì)先后順序?yàn)?45326。CIPHER置換密碼置換密碼(transpositionc95CIPHER145326attackbeginsatfour密文的得出密鑰順序明文先讀順序?yàn)?的明文列，即aba

CIPHER密文的得出密鑰先讀順序?yàn)?的明文列，即ab96CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即cnu

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即cn97CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即aio

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即ai98CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?的明文列，即tet

CIPHER密文的得出密鑰再讀順序?yàn)?的明文列，即te99CIPHER145326attackbeg