第2講-密碼學的基本概念和理論基礎課件

第2講

密碼學的基本概念和理論基礎案例：莫爾斯電碼里的愛情

早已被新科技所取代的莫爾斯密碼，卻在中國的互聯網世界里演繹了一段費盡周折的愛情猜謎傳奇。一男子向一女子表白，女子卻給了一段莫爾斯密碼，以及很少的提示，并表示，破譯這個密碼，才答應和他約會。男子死活不得求解，又在百度貼吧里將密碼貼出以求助網友。電碼如下：“****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/”

“她唯一給我的提示就是這個是5層加密的密碼，也就是說要破解5層密碼才是答案。最終語言是英語。

”網友貼出了莫爾斯密碼對照表，然后發(fā)現相應密碼對應的數字組合和英文字母組合分別是：“4194418141634192622374”、“daiddahadafcdaibfbbcgd”網友“片羿天使”將莫爾斯密碼對應的數字“4194418141634192622374”轉換成了手機鍵盤字母,以41為例，它對應的就是傳統(tǒng)手機鍵盤上的“4”的第一個字母，“94”則是“9”的第4個字母。這樣片羿天使得到了第二步的答案：“GZGTGOGXNCS”。

片羿天使說“因為QWE的格式是被世人所認可的，也就有可能成為密碼的碼表。碼表QWE=ABC依次類推?！卑凑者@樣的次序，上面的來自于手機鍵盤的字母，就轉換到了第三步答案：“OTOEOIOUYVL”。案例：莫爾斯電碼里的愛情

在第四步中，片羿天使用了包括凱撒、乘法等等方法，對第三步幾乎可以看出來的答案進行了進一步的解碼，最后發(fā)現只有柵欄密碼才能讀得通。片羿天使將這組字母分成了“OTOEOI”和“OUYVL”兩排，然后對插重組得到第四步的字母排列：“OOTUOYEVOLI”。第五步于是變得最為簡單起來，那便是將“OOTUOYEVOLI”倒序排列，即“ILOVEYOUTOO”。案例：莫爾斯電碼里的愛情

2.1

基本概念2.1.1什么是密碼學密碼學是研究密碼系統(tǒng)或通信安全的一門學科，分為密碼編碼學和密碼分析學。密碼編碼學是使得消息保密的學科密碼分析學實際要研究加密消息破譯的學科密碼學的發(fā)展歷史第1階段：1949年以前。

第2階段：從1949年到1975年。標志：1949年Shannon發(fā)表的《保密系統(tǒng)的信息理論》一文。第3階段：1976年至今。標志：1976年Diffie和Hellman發(fā)表了《密碼學新方向》一文。Shannon模型X,明文（plain-text）：作為加密輸入的原始信息。Y,密文（cipher-text）：對明文變換的結果。E,加密（encrypt）：是一組含有參數的變換。D,解密（decrypt）：加密的逆變換。Z,密鑰（key）：是參與加密解密變換的參數。密碼系統(tǒng)（Cryptosystem）定義:(密碼體制）它是一個五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構成的有限集；（密鑰空間）*（4）任意,有一個加密算法和相應的解密算法，使得和分別為加密解密函 數，滿足。密碼體制的分類幾種不同的分類標準按操作方式進行分類操作方式：是明文變換成密文的方法。替代操作、置換操作、復合操作。按照使用密鑰的數量進行分類對稱密鑰（單密鑰）。公開密鑰（雙密鑰）。按照對明文的處理方法進行分類流密碼。分組密碼。柯克霍夫斯(Kerckhoffs)假設假定：密碼分析者知道對方所使用的密碼系統(tǒng)包括明文的統(tǒng)計特性、加密體制（操作方式、處理方法和加/解密算法）、密鑰空間及其統(tǒng)計特性。不知道密鑰。密碼體制的安全性僅應依賴于對密鑰的保密，而不應依賴于對算法的保密。只有在假設攻擊者對密碼算法有充分的研究，并且擁有足夠的計算資源的情況下仍然安全的密碼才是安全的密碼系統(tǒng)。一切秘密寓于密鑰之中

密碼分析密碼分析：從密文推導出明文或密鑰。密碼分析：常用的方法有以下4類：惟密文攻擊（cybertextonlyattack）：密碼分析者有一個或更多的用同一個密鑰加密的密文，通過對這些截獲的密文進行分析得出明文或密鑰已知明文攻擊（knownplaintextattack）：除要破譯的密文外，密碼分析者有一些明文和用同一密鑰加密這些明文所對應的密文。選擇明文攻擊（chosenplaintextattack）：密碼分析者可得到所需要的任何明文所對應的密文，這些密文與要破譯的密文是用同一個密鑰加密得來的選擇密文攻擊（chosenciphertextattack）：密碼分析者可得到所需要的任何密文所對應的明文，解密這些密文所使用的密鑰與要破譯的密文的密鑰是相同的密碼分析

密碼系統(tǒng)一個好的密碼系統(tǒng)應滿足：系統(tǒng)理論上安全，或計算上安全；系統(tǒng)的保密性是依賴于密鑰的，而不是依賴于對加密體制或算法的保密；加密和解密算法適用于密鑰空間中的所有元素；系統(tǒng)既易于實現又便于使用。加密的功能保密性：基本功能，使非授權者無法知道消息的內容。鑒別：消息的接收者應該能夠確認消息的來源。完整性：消息的接收者應該能夠驗證消息在傳輸過程中沒有被改變。不可否認性：發(fā)送方不能否認已發(fā)送的消息。古典加密技術從古到今有無數種加密方法，但歸類起來，古代主要是代替密碼、置換密碼以及兩者的結合。代替密碼簡單代替密碼多碼代替密碼多字母代替密碼多表代替密碼置換密碼：換位密碼2.2

傳統(tǒng)密碼及其破譯Scytale密碼和愷撒密碼最先有意識的使用一些技術的方法來加密信息的可能是公元前500年的古希臘人。他們使用的是一根叫scytale的棍子。送信人先繞棍子卷一張紙條，然后把要寫的信息打縱寫在上面，接著打開紙送給收信人。如果不知道棍子的粗細是不可能解密里面的內容的，如下圖所示。公元前50年，著名的愷撒大帝發(fā)明了一種密碼叫做愷撒密碼。在愷撒密碼中，每個字母都與其后第三位的字母對應，然后進行替換。如果到了字母表的末尾，就回到開始，如此形成一個循環(huán)。當時羅馬的軍隊就用愷撒密碼進行通信。愷撒密碼明文字母表：ABCDEFG…XYZ愷撒密碼密文字母表：DEFGHIJ…ABC26個字符代表字母表的26個字母，從一般意義上說，也可以使用其它字符表，一一對應的數字也不一定要是3，可以選其它數字。Caesar密碼乘數密碼算法加密函數取形式為e(x)=ax(mod26)，

a∈Z26

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

該算法描述為：

設P=C=Z26，K={a∈Z26|gcd(a,26)=1},對k=a∈K,

定義ek(x)=ax(mod26)和dk(y)=a-1(y)(mod26)，x,y∈Z26例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

cipher=>SUFLKX乘數密碼分析對于乘數密碼，當且僅當a與26互素時，加密變換才是一一映射的，因此a的選擇有11種：

a=3,5,7,9,11,15,17,19,21,23,25可能嘗試的密鑰只有11個柵欄密碼所謂柵欄密碼，就是把要加密的明文分成N個一組，然后把每組的第i個字連起來，形成一段無規(guī)律的話。就是組成柵欄的字母一般不會太多。（一般不超過30個）一般比較常見的是2欄的柵欄密碼。比如明文：THEREISACIPHER去掉空格后變?yōu)椋篢HEREISACIPHER兩個一組，得到：THEREISACIPHER先取出第一個字母：TEESCPE再取出第二個字母：HRIAIHR連在一起就是：TEESCPEHRIAIHR解密的時候，我們先把密文從中間分開，變?yōu)閮尚校?/p>

TEESCPE

HRIAIHR再按上下上下的順序組合起來：

THEREISACIPHER分出空格，就可以得到原文了：

THEREISACIPHER柵欄密碼仿射密碼仿射密碼是一種替換密碼。它是一個字母對一個字母的。它的加密函數是

，其中

a和m互質。

m是字母的數目。解密函數為：例設k＝（7，3），注意到7-1(mod26)=15,加密函數是ek(x)=7x+3，相應的解密函數是dk(y)=15(y-3)=15y-19,易見dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先轉換字母h,o,t成為數字7,14,19,然后加密：解密：希爾密碼希爾密碼（HillPassword）是運用基本矩陣論原理的多字母代換密碼，由LesterS.Hill在1929年發(fā)明。每個字母當作26進制數字：A=0,B=1,C=2...一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。注意用作加密的矩陣（即密匙）是可逆的，否則就不可能譯碼。只有矩陣的行列式和26互質，才是可逆的。其中所有的運算都是在中進行。例假定密鑰K是，則K-1=。現在我們加密明文july分為兩個明文組（9，20）（相應于ju）和（11，24）（相應于ly）。計算如下：因此，july的加密是DELW。同理，可使用K-1進行解密。Vigenère密碼構成明文：每個字符惟一對應一個0~25間的數字。密鑰：一個字符串，其中每個字符同明文一樣對應一個數字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密過程：將明文數字串依據密鑰長度分段，并逐一與密鑰數字串相加（模26），得到密文數字串；最后，將密文數字串轉換為字母串。例

設m＝6，且密鑰字是k=CIPHER,這相應于密鑰。假定明文串是thiscryptosystemisnotsecure

首先將明文串轉化為數字串，按6個一組分段，然后模26“加”上密鑰字得：相應的密文串將是: VPXZGIAXIVWPUBTTMJPWIZITWZT解密過程與加密過程類似,不同的只是進行模26減,而不是模26加。

置換密碼在簡單的縱行置換密碼中，把明文按列寫入，按行讀出，而密鑰事實上由兩方面信息組成：行寬、列高，讀出順序默認從左到右。一個簡單縱行置換密碼比如：明文：computergraphicsmaybeslow，按照列寬10個字符的方式寫出為：computergraphicsmaybeslow可以得到密文：caeopsmhlpioucwtsemragyrb，下面是一個由密鑰確定讀出順序的例子：如果再加上密鑰：密鑰： 4 3125 6 7明文： a t t a c k p o s t p o n e d u n t i l t w o a m x y z按照密鑰大小的順利，按照列的字符得到密文：TTNAAPTMTSUOAODWCOIXPETZ。置換密碼例

假定m＝6，密鑰是以下置換：；則逆置換為：。給出明文

shesellsseashellsbytheseashore.

首先把明文分為6個字母一組：

shesel

lsseas

hellsb

ytheseashore.

每六個字母按重排，得密文：

EESLSHSALSESLSHBLEHSYEETHRAEOS

用類似地解密。置換密碼置換密碼是Hill密碼的特例。Playfair密碼Playfair在1854年發(fā)明了Playfair密碼。在第一次世界大戰(zhàn)中英國人就使用這種密碼。Playfair將明文中的雙字母組合作為一個單元對待，并將這些單元轉換為密文的雙字母組合。I與J視為同一字符，5×5變換矩陣為

C I P H E R A B D F G K L M N O Q S T U V W X Y Z加密規(guī)則是按成對字母加密，規(guī)則為“相同對中的字母加分隔符(如x)，同行取右邊，同列取下邊，其他取交叉”。明文：balloon單詞中的ll為相同字符，所以分組為：balxloon明文：he，h和e在矩陣中同一行，都取右邊的字符，密文為：EC明文：dm，d和m在矩陣中同一列，都取下面的字符，密文為：MT明文：kt，k和t在矩陣中不同行也不同列，取交叉頂點上的字符，密文為：MQ明文：OD，O和D在矩陣中不同行也不同列，取交叉頂點上的字符，密文為：TR以這個5×5變換矩陣為例，可以對單詞進行加密，加密結果如表2-1所示。表2-1明文分組密文balloonbalxloondbspgs

ugbookbooksr

qgfillfilxlxaespsp一次一密亂碼本如上所述的所有密碼算法均被破解，那么是否存在無法破解的理想加密方案呢？香農證明了一種密碼屬于這種情況，它就是一次一密亂碼本（one-timepad）。一般說來，一次一密亂碼本就是一個大的不重復的真隨機密鑰字母集，發(fā)送者用亂碼本中的每一個密鑰準確地加密一個明文字符，加密是明文字符和密鑰字符進行模26加法。比如：明文： onetimepad密鑰： TBFRGFARFM密文： IPKLPSFHGQ因為： O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，……如果竊聽者不能得到用來加密的一次一密亂碼本，這個方案就是完全保密的。給出的密文消息相當于同樣長度的任何可能的明文消息。隨機密鑰安全強度取決于密鑰的隨機性理論上不可破實際上不可行產生大量的隨機密鑰難密鑰分配與保護更難明文：Tobeornottobethatisthequestion,使用Vigenère加密，密鑰字取為run密鑰：runrunrunrunrunrunrunrunrunrun

明文：tobeornottobethatisthequestion密文：KIOVIEEIGKIOVNURNVJNUVKHVMGZIAKIOV，后一個相當于前一個向后移動了9位；NU，后一個相當于前一個向后移動了6位。重復明文字母串的距離正好是密鑰長度的倍數。Vigenère密碼的密碼分析Vigenère密碼的密碼分析第一步：確定密鑰的長度，主要方法有：Kasiski測試法；

基本原理：對于密鑰長度為d的Vigenère密碼，如果利用給定的密鑰表周期性地對明文字母進行加密，則當明文中有兩個相同的字母組在明文序列中間隔的字母數為d的倍數時，這兩個明文字母組對應的密文字母組一定相同；反之，如果密文中出現兩個相同的字母組，則其對應的明文字母組不一定相同。重合指數法。

基本思想：對于長度分別為n的密文串y=y1y2…yn，將其分為長度為n/d的d個子串Yi（i=1,2,…,d),如果密鑰長度為d，則Ic(Yi)≈0.065(1≤i≤d)，否則，因為采用不同的密鑰依位加密，子串Yi將更為隨機。對于一個完全隨機的密文串，Ic(y)≈26(1/26)2=0.038。由于0.038與0.065的差值足夠大，所以在一般情況下，依據重合指數法能夠判斷出正確的密鑰長度。Vigenère密碼的密碼分析第二步：確定密鑰。通常采用重合互指數法。對于長度分別為n及n′的字母串x=x1x2…xn和y=y1y2…yn，“重合互指數”指的是x的一個隨機元素與y的一個隨機元素相同的概率，記為MIc(x,y)。通過采用重合互指數法，可以獲得任何兩個子串Yi與Yj的相對移位。

古典密碼小結模運算：加法、減法、乘法性質：對稱、傳遞、交換、結合、分配加法逆元、乘法逆元對稱密碼的兩個基本運算代替和置換（Substitution&permutation）密碼分析與Kerckhoff原則多輪加密數據安全基于算法的保密

古典密碼小結2.3Shannon的保密系統(tǒng)信息理論1949年，Shannon發(fā)表了一篇題為《保密系統(tǒng)的信息理論》的論文。用信息論的觀點對信息保密問題進行了全面的闡述。宣告了科學的密碼學時代的到來。什么是信息科學家說：信息是不確定性的減少，是負熵老百姓說：信息是讓你知道些什么的東西安全專家說：信息是一種資產，它意味著一種風險老百姓說：不怕賊偷，就怕賊惦記通信系統(tǒng)模型編碼器信源信道信宿譯碼器干擾器圖2.2通信系統(tǒng)模型加密器信源信道接收者解密器分析者圖2.3保密系統(tǒng)模型密鑰Shannon提出的保密模型無噪信道安全信道密鑰源加密分析者解密接收者發(fā)送者信源圖2.3Shannon的保密系統(tǒng)模型數學模型數學模型樣本空間密鑰空間密文空間概率知識討論在給定密文發(fā)生的條件下，某個明文發(fā)生的條件概率信息量和熵定義

設隨機變量，出現的概率為。則X的不確定性或熵（Entropy）定義為

熵反映了集中事件出現的平均不確定性，或為確定集中出現一個事件平均所需的信息量（觀測之前），或集中每出現一個事件平均給出的信息量（觀測之后）。如果從編碼的角度來考慮，熵也可以理解成用最優(yōu)的二進制編碼形式表示所需的比特數。采用以2為底的對數時，相應的信息單位稱作比特（Bit）。如果集X為均勻分布時，即，則。，當X為確定性的事件時，即X概率分布為，則。例：某地某季節(jié)各種天氣情況出現的概率分別為晴：50%，陰：25%，大雨：12.5%，小雨：12.5%。請問某人聽到一則天氣預報后獲得的信息量是多少？（也可以理解為：這則天氣預報消除了多少人們對天氣情況認識的不確定性？）解：=0.5×log21/0.5+0.25×log21/0.25+0.125×log21/0.125+0.125×log21/0.125=1.75bit

H=∑Pilog2

1Pi

4i=1信息量和熵案例韋小寶賭博：韋小寶擲骰子賭錢十賭九贏。計算包含的信息量？未做手腳情況：等概率事件，不確定性為：

H(S)=-log(pi)=-log(1/6)=2.5850(bit)做手腳情況：某面的概率為0.9，其他5面的概率均為1/50，則不確定性為：

H(S)=-pi

log(pi)=-0.9log(0.9)-5×0.02log(0.02)=0.7012(bit)韋小寶賭博定義設，出現的概率為。，出現的概率為，則聯合事件集，令的概率為，此時。集X和Y的聯合熵定義為集相對于事件yi∈Y的條件熵定義為集相對于集Y的條件熵定義為熵的基本特性定理，當且僅當X和Y獨立時等號成立。定理。推論

，當且僅當X和Y獨立時等號成立。密碼體制的安全性（1）無條件安全或完善保密性（unconditionallysecure）：不論提供的密文有多少，密文中所包含的信息都不足以惟一地確定其對應的明文；具有無限計算資源（諸如時間、空間、資金和設備等）的密碼分析者也無法破譯某個密碼系統(tǒng)。完善保密性一個保密系統(tǒng)（P，C，K，E，D）稱為完善的無條件的保密系統(tǒng)，如果H(P)=H(P|C),其中，P為明文集合，C為密文集合，K為密鑰集合，E為加密算法,D為解密算法,則完善保密系統(tǒng)存在的必要條件是H(P)≤H(K)?？梢?，要構造一個完善保密系統(tǒng)，其密鑰量的對數（密鑰空間為均勻分布的條件下）必須不小