第2講密碼學(xué)與PGP和社會工程學(xué)密碼分析器課件

第2講密碼學(xué)及其工具2.1密碼學(xué)基本概念2.2古典密碼2.3DES與RSA2.4PGP2.5社會工程學(xué)密碼分析器第2講密碼學(xué)及其工具2.1密碼學(xué)基本概念12.1密碼學(xué)基本概念2.1.1密碼體制2.1.2密碼分析2.1.3密碼學(xué)的理論基礎(chǔ)2.1密碼學(xué)基本概念2.1.1密碼體制2密碼學(xué)(Cryptology)是一門古老的科學(xué)。大概自人類社會出現(xiàn)戰(zhàn)爭便產(chǎn)生了密碼，以后逐漸形成了一門獨立的學(xué)科。在密碼學(xué)形成和發(fā)展歷程中，科學(xué)技術(shù)的發(fā)展和戰(zhàn)爭的刺激都起了積極的推動作用。電子計算機一出現(xiàn)便被用于密碼破譯，使密碼進入電子時代，其后有幾個值得關(guān)注的里程碑：1949年香農(nóng)發(fā)表《保密系統(tǒng)的通信理論》，把密碼學(xué)置于堅實的數(shù)學(xué)基礎(chǔ)上，標(biāo)志著密碼學(xué)作為一門科學(xué)的形成；1976年W.Diffie和M.Hellman提出公開密鑰密碼，從而開創(chuàng)了一個密碼新時代；1977年美國聯(lián)邦政府頒布數(shù)據(jù)加密標(biāo)準(zhǔn)DES；1994年美國聯(lián)邦政府頒布密鑰托管加密標(biāo)準(zhǔn)EES，同年頒布數(shù)字簽名標(biāo)準(zhǔn)DSS，2001年頒布高級加密標(biāo)準(zhǔn)AES；目前，量子密碼因其具有可證明的安全性，同時還能對竊聽行為進行檢測，從而研究廣泛；生物信息技術(shù)的發(fā)展也推動了DNA計算機和DNA密碼的研究密碼學(xué)(Cryptology)是一門古老的科學(xué)。大概自人類社3自古以來，密碼主要用于軍事、政治、外交等要害部門，因而密碼學(xué)的研究工作本身也是秘密進行的。后來，隨著計算機網(wǎng)絡(luò)的普及，電子政務(wù)、電子商務(wù)和電子金融等對確保信息安全的需求的增加，民間出現(xiàn)了一些不從屬于保密機構(gòu)的密碼學(xué)者。實踐證明，正是這種公開研究和秘密研究相結(jié)合的局面促進了今天密碼學(xué)得空前繁榮。研究密碼編制的科學(xué)稱為密碼編制學(xué)(Cryptography)；研究密碼破譯的科學(xué)稱為密碼分析學(xué)(Cryptannalysis)；密碼編制學(xué)和密碼分析學(xué)共同組成密碼學(xué)(Cryptology)。自古以來，密碼主要用于軍事、政治、外交等要害部門，因而密碼學(xué)4密碼學(xué)的基本思想是偽裝信息，使未授權(quán)者不能理解它的真實含義。所謂偽裝就是對數(shù)據(jù)進行一組可逆的數(shù)學(xué)變換。偽裝前的原始數(shù)據(jù)稱為明文(Plaintext)，偽裝后的數(shù)據(jù)稱為密文(Ciphertext)，偽裝的過程稱為加密(Encryption)。加密在加密密鑰(Key)的控制下進行。用于對數(shù)據(jù)加密的一組數(shù)學(xué)變換稱為加密算法發(fā)信者將明文數(shù)據(jù)加密成密文，再將密文數(shù)據(jù)送入網(wǎng)絡(luò)傳輸或存入計算機文件，而且只給合法收信者分配密鑰。合法收信者接收到密文后，施行與加密變換相逆的變換，去掉密文的偽裝恢復(fù)出明文，這一過程稱為解密(Decryprion)。解密在解密密鑰的控制下進行。用于解密的一組數(shù)學(xué)變換稱為解密算法，而且解密算法是加密算法的逆。密碼學(xué)的基本思想是偽裝信息，使未授權(quán)者不能理解它的真實含義。52.1.1密碼體制明文加密算法信道明文解密算法MM攻擊者CC加密密鑰加密密鑰安全信道密鑰KKeKd2.1.1密碼體制明加信明解MM攻擊者CC加密密鑰加密密6一個密碼系統(tǒng)通常簡稱為密碼體制(Cryptosystem)，由五部分組成：①明文空間M，它是全體明文的集合；②密文空間C，它是全體密文的集合；③密鑰空間K，它是全體密鑰的集合。其中，每一個密鑰K均由加密密鑰Ke和解密密鑰Kd組成，即K=<Ke,Kd>④加密算法E，它是一族由M到C的加密變換；⑤解密算法D，它是一族由C到M的解密變換。對于明文空間M中的每個明文，加密算法E在密鑰Ke的控制下將明文M加密為密文C：C=E(M,Ke)(2-1)而解密算法D在密鑰Kd的控制下，解密C成明文M:M=D(C,Kd)=D(E(M,Ke),Kd)(2-2)一個密碼系統(tǒng)通常簡稱為密碼體制(Cryptosystem)，7如果一個密碼體制的Ke=Kd，或者由其中一個很容易推出另一個，則稱該密碼體制為單密鑰密碼體制或?qū)ΨQ密碼體制或傳統(tǒng)密碼體制，否則稱雙密鑰密碼體制。進而，如果在計算上Kd不能由Ke推出，這樣，將Ke公開也不會損害Kd的安全，于是便可將Ke公開。這種密碼體制稱為公開密鑰密碼體制，簡稱公開密碼體制。根據(jù)明密文的劃分和密鑰的使用不同，可將密碼體制分為分組密碼和序列密碼體制。設(shè)M為明文，分組密碼將M劃分稱一系列的明文塊Mi，通常每塊包含若干位或字符，并且每一塊Mi都用同一個密鑰Ke進行加密，即M=(M1,M2,…,Mn) C=(C1,C2,…,Cn)其中，Ci=E(Mi,Ke)(i=1,2,…,n)如果一個密碼體制的Ke=Kd，或者由其中一個很容易推出另一個8而序列密碼將明文和密鑰都劃分成為或字符的序列，并且對明文序列中的每一個位或字符都用密鑰序列中的對應(yīng)分量進行加密，即M=(m1,m2,…,mn) Ke=(ke1,ke2,…,ken) C=(c1,c2,…,cn)其中，ci=E(mi,kei)(i=1,2,…,n)分組密碼每一次加密一個明文塊，而序列密碼每一次加密一位或一個字符。序列密碼是要害部門使用的主流密碼，而商用領(lǐng)域則多用分組密碼。根據(jù)加密算法在使用過程中是否變化，可將密碼體制分為固定算法密碼體制和演化密碼體制。固定算法密碼體制的加解密算法固定不變；而演化密碼體制將密碼學(xué)和演化計算相結(jié)合，使得在加密過程中加密算法也不斷演化。而序列密碼將明文和密鑰都劃分成為或字符的序列，并且對明文序列9

2.1.2密碼分析如果能夠根據(jù)密文系統(tǒng)地確定出明文或密鑰，或者能夠根據(jù)明文-密文對系統(tǒng)地確定出密鑰，則稱這個密碼是可破譯的。研究密碼破譯的科學(xué)稱為密碼分析學(xué)。密碼分析者攻擊密碼的方法主要有三種：1）窮舉攻擊窮舉攻擊是指密碼分析者采用依次試遍所有可能的密鑰對所獲得的密文進行解密，直至得到正確的明文；或者用一個確定的密鑰對所有可能的明文進行加密，直至得到所獲得的密文。理論上，對于任何使用密碼只要有足夠的資源都可以用窮舉攻擊將其攻破。從平均角度講，采用窮舉攻擊破譯一個密碼必須試遍所有可能密鑰的一半。窮舉攻擊所花費的時間等于嘗試次數(shù)乘以一次解密或加密所需的時間?？梢酝ㄟ^增大密鑰量或加大解密或加密算法的復(fù)雜性來對抗窮舉攻擊。

2.1.2密碼分析如果能夠根據(jù)密文系統(tǒng)地確定出明文或密102）統(tǒng)計分析攻擊統(tǒng)計分析攻擊是指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。統(tǒng)計分析攻擊在歷史上為破譯古典密碼作出過很大貢獻。對抗統(tǒng)計分析攻擊的方法是設(shè)法使明文的統(tǒng)計特性不帶入密文。這樣，密文不帶有明文的痕跡，從而使統(tǒng)計分析攻擊成為不可能。3）數(shù)學(xué)分析攻擊數(shù)學(xué)分析攻擊是指密碼分析者對加解密算法的數(shù)學(xué)基礎(chǔ)和某些密碼學(xué)特性，通過數(shù)學(xué)求解的方法來破譯密碼。數(shù)學(xué)分析攻擊是對基于數(shù)學(xué)難題的各種密碼的主要威脅，為此，應(yīng)當(dāng)選用具有堅實數(shù)學(xué)基礎(chǔ)和足夠復(fù)雜的加解密算法。2）統(tǒng)計分析攻擊11此外，根據(jù)密碼分析者可利用的數(shù)據(jù)資源來分類，可將攻擊密碼的類型分為以下四種：1）僅知密文攻擊僅知密文攻擊是指密碼分析者僅根據(jù)截獲的密文來破譯密碼。2）已知明文攻擊已知明文攻擊是指密碼分析者根據(jù)已知的某些明文-密文對來破譯密碼。3）選擇明文攻擊選擇明文攻擊是指密碼分析者能夠選擇明文并獲得相應(yīng)的密文。4）選擇密文攻擊選擇密文攻擊是指密碼分析者能夠選擇密文并獲得相應(yīng)的明文。這種攻擊主要攻擊公開密鑰密碼體制，特別是攻擊其數(shù)字簽名。此外，根據(jù)密碼分析者可利用的數(shù)據(jù)資源來分類，可將攻擊密碼的類12一個密碼，如果無論密碼分析者截獲多少密文和用什么技術(shù)方法進行攻擊都不能被攻破，則稱該密碼是絕對不可破譯的。絕對不可破譯的密碼在理論上是存在的，這就是著名的“一次一密”密碼。但是，由于密鑰管理上的困難，“一次一密”密碼是不實用的。理論上，如果能夠獲得足夠的資源，那么任何實際可使用的密碼又都是可破譯的。如果一個密碼，不能被密碼分析者根據(jù)可利用的資源所破譯，則稱其是計算上不可破譯的。因為任何秘密都有其時效性，因此，對我們更有意義的是在計算上不可破譯的密碼。一個密碼，如果無論密碼分析者截獲多少密文和用什么技術(shù)方法進行132.1.3密碼學(xué)的理論基礎(chǔ)1949年，shannon發(fā)表的《保密系統(tǒng)的通信理論》從信息論的角度對信息源、密鑰、加密和密碼分析進行了數(shù)學(xué)分析，用不確定性和唯一解距離來度量密碼體制的安全性，闡明了密碼體制、完善保密、純密碼、理論保密和實際保密等重要概念，把密碼置于堅實的數(shù)學(xué)基礎(chǔ)之上，標(biāo)志著密碼學(xué)作為一門獨立學(xué)科的形成。從此，信息論成為密碼學(xué)重要的理論基礎(chǔ)之一。Shannon建議采用擴散、混淆和乘積迭代的方法設(shè)計密碼，并且以“揉面團”的過程形象地比喻擴散、混淆和乘積迭代的概念。所謂擴散就是將每一位明文和密鑰數(shù)字的影響擴散到盡可能多得密文數(shù)字中。理想狀態(tài)下，明文和密鑰的每一位都影響密文的每一位，一般稱這種情形達到“完備性”。所謂混淆就是是密文和密鑰之間的關(guān)系復(fù)雜化。密文和密鑰之間的關(guān)系越復(fù)雜，則密文和明文之間、密文和密鑰之間的統(tǒng)計相關(guān)性越小，從而使統(tǒng)計分析不能奏效。設(shè)計一個復(fù)雜密碼一般是比較困難的，利用乘積迭代方法對簡單密碼進行組合迭代，可以得到理想的擴散和混淆，從而可以得到安全的密碼。2.1.3密碼學(xué)的理論基礎(chǔ)1949年，shannon發(fā)表14計算復(fù)雜性理論是密碼學(xué)的另一個理論基礎(chǔ)。為計算求解一類問題，總需要一定量的時間資源和空間資源。消耗資源的多少取決于要求解問題的規(guī)模大小。設(shè)要求解的問題規(guī)模（如，輸入變量的個數(shù)或輸入長度）為n，若對于所有的n和所有長度為n的輸入，計算最多要用f(n)步完成，則稱該問題的計算復(fù)雜度為f(n)。若f(n)為n的多項式，則稱其為多項式復(fù)雜度。粗略的講，計算機可以在多項式時間復(fù)雜度內(nèi)解決的問題稱為P類問題；否則，為NP類問題。P類問題是計算機可計算的，而NP問題是計算機不可計算的困難問題。NP問題中最難得問題稱為NP完全問題，即NPC問題。Shannon指出設(shè)計一個安全的密碼本質(zhì)上就是要尋找一個難解的問題。這樣，計算復(fù)雜性理論的發(fā)展將直接影響密碼的安全。此外，密碼的設(shè)計應(yīng)該遵循公開設(shè)計原則。密碼體制的安全僅依賴于密鑰的保密，而不應(yīng)依賴于對算法的保密。當(dāng)然，密碼設(shè)計的公開原則并不等于所有的密碼在應(yīng)用時都要公開加密算法。也就是說，在公開的原則下設(shè)計密碼，在實際使用時對算法保密，將會更加安全。計算復(fù)雜性理論是密碼學(xué)的另一個理論基礎(chǔ)。為計算求解一類問題，152.2古典密碼2.2.1置換密碼2.2.2替代密碼2.2.3代數(shù)密碼2.2.4古典密碼的統(tǒng)計分析2.2古典密碼2.2.1置換密碼162.2.1置換密碼把明文中的字母重新排列，字母本身不變，但其位置改變，這樣編成的密碼稱為置換密碼。最簡單的置換密碼是把明文中字母順序顛倒過來，然后截成固定長度的字母組作為密文。例如：明文：明晨5點發(fā)動反攻。 mingchenwudianfadongfangong密文：gnognafgnodafnaiduwnehcgnim倒序的置換密碼顯然是很弱的。另一種置換密碼是把明文按某一順序排成一個矩陣，其中不足部分用Ф填充，而Ф是明文中不會出現(xiàn)的一個符號；然后按另一個順序選出矩陣中的字母以形成密文，最后截成固定長度的字母組作為密文。2.2.1置換密碼把明文中的字母重新排列，字母本身不變，17明文：WHATCANYOULEARNFROMTHISBOOK”明文矩陣：舉例明文WHATCANYOULEARNFROMTHISBOOKФФФФФ選出順序：按列密文：WOROHUOOALMKTETФCAHФARIФNNSФYFBФ可以看出，改變矩陣的大小和選出順序可以得到不同形式的密碼。一種巧妙的方法：首先選一個詞語作為密鑰，去掉重復(fù)字母；然后按字母的字典順序給密鑰字母編號，并按照密鑰的長度把明文排列成矩陣；最后按照數(shù)字序列中的數(shù)字順序按列選出密文明文：WHATCANYOULEARNFROMTHI18密鑰：k=computer明文：WHATCANYOULEARNFROMTHISBOOK”按密鑰排列明文：舉例密鑰COMPUTER順序號14358726明文WHATCANYOULEARNFROMTHISBOOKФФФФФ密文：WORONNSФALMKHUOOTETФYFBФARIФCAHФ密鑰：k=computer舉例密鑰COMPUTER順序號192.2.2替代密碼首先構(gòu)造一個或多個密文字母表，然后用密文字母表中的字母或字母組來替代明文字母或字母組，各字母或字母組的相對位置不變，但其本身改變，這樣編成的密碼稱為替代密碼。按照替代所使用的密文字母表的個數(shù)可將替代密碼分為單表替代密碼、多表替代密碼和多名替代密碼1.單表替代密碼又稱為簡單替代密碼。它只使用一個密文字母表，并且用密文字母表中的一個字母來替代一個明文字母表中的一個字母。設(shè)A={a0,a1,…,an-1}; B={b0,b1,…,bn-1}定義一個由A到B的一一映射：f:AB,即f(ai)=bi設(shè)明文M=(m0,m1,…,mn-1)，則密文C=(f(m0),f(m1),…,f(mn-1))2.2.2替代密碼首先構(gòu)造一個或多個密文字母表，然后用密201）加法密碼加法密碼的映射函數(shù)：f(ai)=bi=aj，j=i+kmodn,k是0<k<n的正整數(shù)著名的加法密碼是古羅馬的凱撒大帝使用的密碼Caesar密碼取k=3，因此其密文字母表就是把明文字母表循環(huán)右移3位后得到的字母表。2）乘法密碼乘法密碼的映射函數(shù)：f(ai)=bi=aj，j=ikmodn其中，要求k和n互素。因為僅當(dāng)(k,n)=1時，才存在兩個整數(shù)x,y，使得xk+yn=1，才能有xk=1modn，才有i=xjmodn，密碼才能正確解密。例如，當(dāng)用英文字母表作為明文字母表而取k=13時，因為(13,26)=13≠1，會出現(xiàn)：f(A)=f(C)=f(E)=……=f(Y)=Af(B)=f(D)=f(F)=……=f(Z)=N這樣，密文字母表變?yōu)锽={A,N,A,N,A,N,……A,N}1）加法密碼213）仿射密碼乘法密碼和加法密碼相結(jié)合就構(gòu)成了仿射密碼。仿射密碼的映射函數(shù)：f(ai)=bi=aj，j=ik1+k0modn其中，要求k1和n互素，0<=k0<n,且不允許同時有k1=1k0=0。4）密鑰詞語替代密碼首先隨機選用一個詞組或短語作為密鑰，去掉重復(fù)字母，把結(jié)果作為矩陣的第一行；其次，在明文字母表中去掉矩陣第一行中的字母，并將剩余字母依次寫入矩陣的其余行；最后按某一順序從矩陣中取出字母構(gòu)成密文字母表。例如：密鑰：HONGYE矩陣：HONGYE 選出順序：按列ABCDFIJKLMPQ RSTUVW XZ3）仿射密碼222.多表替代密碼簡單替代密碼很容易被破譯，提高替代密碼強度的一種方法是采用多個密文字母表，使明文中的每個字母都有很多種可能的字母來替代。構(gòu)造d個密文字母表：Bj={bj0,bj1,…,bjn-1},j=0,1,…,d-1定義d個映射：fj:ABj,即fj(ai)=bji設(shè)明文M=(m0,m1,…,md-1,md,…,mn-1)則密文C=(f0(m0),f1(m1),…,fd-1(md-1),fd(md),…)由于加密用到了多個密文字母表，故稱為多表替代密碼。多表替代密碼的密鑰就是這組映射函數(shù)或密文字母表。最著名的多表替代密碼是16世紀(jì)法國密碼學(xué)者Vigenere使用的Vigenere密碼。它依次把明文字母表循環(huán)右移0,1,2,…,25位，獲得26個密文字母表，構(gòu)成Vigenere方陣：2.多表替代密碼23Vigenere方陣明文abcdefghijklmnopqrstuvwxyzaABCDEFGHIJKLMNOPQRSTUVWXYZbBCDEFGHIJKLMNOPQRSTUVWXYZA…eEFGHIJKLMNOPQRSTUVWXYZABCD…sSTUVWXYZABCDEFGHIJKLMNOPQRtTUVWXYZABCDEFGHIJKLMNOPQRS…zZABCDEFGHIJKLMNOPQRSTUVWXYVigenere方陣明文abcdefghijklmnopq24Vigenere密碼設(shè)P=datasecurity，k=best則采用維吉尼亞密碼的加密過程如下：1.按密鑰的長度將P分解若干節(jié)2.對每一節(jié)明文，利用密鑰best進行變換。得到如下密文：C=EEK(P)=EELTTIUNSMLR密鑰best明文datasecurityVigenere密碼設(shè)P=datasecurity，k253.多名替代密碼為了抵抗頻率分析攻擊，希望密文中不殘留明文字母的頻率痕跡。一種明顯的方法是設(shè)法將密文字母的頻率分布拉平。這就是多名替代密碼的出發(fā)點。設(shè)明文字母表A={a0,a1,…,an-1}，對于每一個明文字母ai，作一個與之對應(yīng)的字符集合bi，且使bi中的字符個數(shù)正比于ai在明文中的相對頻率，稱bi為ai的多名字符集。以集合B={Bi|i=0,1,…,n-1}作為密文字母表。定義映射函數(shù)：F:AB f(ai)=bji，而bji∈Bi即映射函數(shù)f將明文字母ai映射到它的一個多名字符bji。設(shè)明文M=(m0,m1,…,mn-1)則密文C=(f(m0),f(m1),…,f(mn-1))=(c0,c1,…,cn-1)，其中ci是根據(jù)映射函數(shù)從多名字符集中隨機選取的一個多名字符。由于多名字符集合中的整數(shù)個數(shù)正比于相應(yīng)字母的相對頻率以及不同的多名字符集合間沒有相同的整數(shù)，而且每個多名字符的選取又是完全隨機的，所以多名替代密碼的密文字符頻率分布是平坦的。這大大增強了密碼的強度。3.多名替代密碼26+2.2.3代數(shù)密碼異或運算（或稱模2加運算）具有如下特點：00=0;01=1;10=1;11=0aa=0;abb=a即兩個運算數(shù)相同，結(jié)果為0；不同，結(jié)果為1。使用簡單異或進行加密，就是將明文與密鑰進行異或運算，解密則是對密文用同一密鑰進行異或運算。即Pk=C；Ck=P1917年美國電話電報公司的GillbertVernam為電報通信設(shè)計的Vernam密碼就是將明文和密鑰進行異或運算而得到密文的密碼。Vernam密碼的突出特點是其加密運算和解密運算相同，都是異或運算。但它經(jīng)不起已知明文攻擊。數(shù)學(xué)上，如果一個變換的正變換和逆變換相同，則稱其為對合運算。對合運算可使加解密公用同一算法，工程實現(xiàn)的工作量減少一半。+++++++++2.2.3代數(shù)密碼異或運算（或稱模2加運算）具有如下特272.2.4古典密碼的統(tǒng)計分析任何自然語言都有許多固有的統(tǒng)計特性。如果自然語言的這種統(tǒng)計特性在密文中有所反映，則密碼分析者便可以通過分析明文和密文的統(tǒng)計規(guī)律而將密碼破譯。1.語言的統(tǒng)計特性英文文獻中，各英文字母的概率分布：A8.167;B1.492;C2.782;D4.253;E12.702;F2.228G2.015;H6.094;I6.966;J0.153;K0.772;L4.025;M2.406;N6.749;O7.507;P1.929;Q0.095;R5.987;S6.327;T9.056;U2.758;V0.978;W2.360;X0.150;Y1.974;Z0.074其中，極高頻率字母為E;次高為TAOINSHR;中等為DL;低頻率為CUMWFGYPB;基低頻率為VKJXQZ2.2.4古典密碼的統(tǒng)計分析任何自然語言都有許多固有的統(tǒng)28不僅單字母以相對穩(wěn)定的頻率出現(xiàn)，而且雙字母組和三字母組同樣如此。這些統(tǒng)計數(shù)據(jù)，對密碼分析者都是十分重要的信息。此外，密碼分析者的文學(xué)、歷史、地理等方面的知識對于破譯密碼也是十分重要的因素。2.古典密碼分析以簡單替代密碼為例。對于加法密碼，密鑰整數(shù)k只是n-1個不同的取值。對于明文字母表以英文字母表的情況，k只有25中可能的取值。即使是對于明文字母表以8位擴展ASCII碼而言，k也只有255中可能的取值。因此，只要對k的可能取值逐一窮舉就可破譯加法密碼。乘法密碼比加法密碼更容易破譯。因為密鑰整數(shù)k要滿足條件(n,k)=1，因此k只有Ф(n)(即，n的歐拉函數(shù))個不同的取值。去掉k=1這一恒等情況，k的取值只有Ф(n)-1種。對于明文字母表為英文字母表的情況，k只能取3、5、7、9、11、15、17、19、21、23、25共11種不同的取值，比加法密碼弱得多。不僅單字母以相對穩(wěn)定的頻率出現(xiàn)，而且雙字母組和三字母組同樣如29仿射密碼的保密性能好些。其可能的密鑰也只有nФ(n)-1種。對于明文字母表為英文字母表的情形，可能的密鑰只有26*12-1=311種。如果用計算機破譯，則完全可以非常方便地破譯出來。本質(zhì)上，密文字母表實際上是明文字母表的一種排列。設(shè)明文字母表含n個字母，則共有n!種排列，對于明文字母表為英文字母表的情況，可能的密文字母表有26!≈4×1026種。由于密鑰詞組代替密碼的密鑰詞組可以隨意選擇，故這26!種不同的排列中的大部分被用作密文字母表也是不可能的。即使使用計算機，企圖用窮舉一切密鑰的方法來破譯密鑰詞組替代密碼也是不可能的。那么，密鑰詞組替代密碼是不是牢不可破呢？其實不然，因為窮舉并不是攻擊密碼的唯一方法。這種密碼僅在傳輸短的消息時是保密的，一旦消息足夠長，密碼分析者便可利用其他的統(tǒng)計分析方法迅速破解之。仿射密碼的保密性能好些。其可能的密鑰也只有nФ(n)-1種。30字母和字母組的統(tǒng)計數(shù)據(jù)對于密碼分析者來說是十分重要的。因為它們可以提供有關(guān)密鑰的許多信息。例如，由于字母E比其他字母的概率要高得多，如果是簡單替代密碼，那么可以預(yù)計大多密文都將包含一個頻率比其他字母都高的字母。當(dāng)出現(xiàn)這種情況時，完全可以猜測這個字母對應(yīng)的明文字母就是E。一般，破譯單替代密碼的大致過程：首先，統(tǒng)計密文的各種統(tǒng)計特征，如果密文量比較多，則完成這步后便可確定出大部分密文字母；其次，分析雙字母、三字母密文組，以區(qū)分元音和輔音字母；最后，分析字母較多的密文，在這一過程中大膽使用猜測的方法，如果猜對一個或幾個詞，就會大大加快破譯過程。字母和字母組的統(tǒng)計數(shù)據(jù)對于密碼分析者來說是十分重要的。因為它312.3DES和RSA2.3.1數(shù)據(jù)加密標(biāo)準(zhǔn)DES2.3.2公開密鑰密碼的基本概念2.3.3RSA密碼2.3DES和RSA2.3.1數(shù)據(jù)加密標(biāo)準(zhǔn)DES322.3.1數(shù)據(jù)加密標(biāo)準(zhǔn)DES為適應(yīng)社會對計算機數(shù)據(jù)安全保密越來越高的需求，美國國家標(biāo)準(zhǔn)局NBS于1973年開始公開征集，并于1977年1月5號采納IBM的加密算法作為數(shù)據(jù)加密標(biāo)準(zhǔn)的DES加密算法。DES的設(shè)計目標(biāo)：用于加密保護靜態(tài)存儲和傳輸信道中的數(shù)據(jù)，安全使用10-15年。DES綜合利用了置換、替代、代數(shù)等多種密碼技術(shù)。它設(shè)計精巧、實現(xiàn)容易、使用方便，堪稱是適應(yīng)計算機環(huán)境的近代傳統(tǒng)密碼的一個典范。DES的設(shè)計充分體現(xiàn)了Shannon信息保密理論所闡述的設(shè)計密碼的思想，標(biāo)志著密碼的設(shè)計與分析達到了一個新的水平。DES是一種分組密碼。明文、密文和密鑰的分組長度都是64位。DES是面向二進制的密碼算法，因而能夠加解密任何形式的計算機數(shù)據(jù)。DES是對合運算，因而加密和解密共用同一算法，從而使工程實現(xiàn)的工作量減半。2.3.1數(shù)據(jù)加密標(biāo)準(zhǔn)DES為適應(yīng)社會對計算機數(shù)據(jù)安全保33DES算法的特點1）對稱算法：既可用于加密，也可用于解密。不同之處在于解密時用了16個子密鑰的順序和加密時所用的16個子密鑰的順序是顛倒的2）64位的密鑰，使用長度為56位（64位明文中，有8位用于奇偶校驗）。3）加密算法是混淆與擴散的結(jié)合，或者說是換位與置換的結(jié)合。4）每個DES都在明文上實施16重相同的組合技術(shù)。這種重復(fù)性可以被非常理想地應(yīng)用到一個專用芯片中。初始換位56位密鑰64位密文組64位明文組16輪加密變換生成16個48位子密鑰壓縮變換逆初始換位56位密鑰DES64位明文組64位密文組56位密鑰DES算法的特點1）對稱算法：既可用于加密，也可用于解密。不34DES加密過程細化初始換位和逆初始換位；將64位明文分為32位的左右兩段：L0和R0；進行16輪相同的迭代運算：混淆+異或+交換；將最后左右兩段合并；生成每一輪的子密鑰。64位明文組初始換位IP得到L0得到R0f+K1L1=R0R1=L0f(R0,K1)f+K2L2=R1R2=L1f(R1,K2)f+L15=R14R15=L14f(R14,K15)fKi+R16=L15f(R15,K16)L16=R15逆初始換位IP-1K1664位密文組++++DES加密過程細化初始換位和逆初始換位；64位明文組初始換位35初始換位IP和逆初始換位IP-1

408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757255850423426181026052443628201246254`4638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆初始換位IP-1初始換位IP初始換位IP和逆初始換位IP-1408481656246436DES子密鑰的生成64位密鑰56位密鑰壓縮變換PC-1分割得到C0，D0左移左移壓縮變換PC-2左移左移壓縮變換PC-2左移左移壓縮變換PC-2K1K2K16┇（48位）（48位）（48位）28位28位DES子密鑰的生成64位密鑰56位密鑰壓縮變換PC-1分割得37壓縮變換PC-1與分割得到C0，D0PC-1的作用是去掉奇偶校驗位8，16，24，32，40，48，56，64后，按56位進行換位。C0=k57k49k41…k52k44k36D0=k43k55k47…k20k12k45749413325179158504234261810259514335271911360524436635547393123157625446380221466153453729211352820124壓縮變換PC-1與分割得到C0，D0PC-1的作用是去掉奇偶38密鑰移位——每輪左移位數(shù)壓縮置換PC-2輪數(shù)12345678910111213141516移動位數(shù)11222222122222211417112415328156211023191242681672720132415231374755304051453348444939563453464250362932密鑰移位——每輪左移位數(shù)壓縮置換PC-2輪數(shù)123439DES的f算法F算法的主要組成E-盒S-盒P-盒32位Ri-1+48位KiP-盒置換32位Li-1E-盒擴展置換S-盒替代+32位Ri32位Li48位32位48位32位DES的f算法F算法的主要組成32位Ri-1+48位KiP-40E-盒（ExpansionPermutation,擴展置換）把數(shù)據(jù)明文的右半部分Ri從32位擴展到48位12345678910111213141516輸入12345678910111213141516171819202122232448輸出12345678910111213141516（對應(yīng)輸入）4598131217251632E-盒（ExpansionPermutation,擴展置換41S-盒代換S-盒是進行了壓縮后的密鑰（56位→48位）與擴展后的明文分組（32位→48位）異或后進行的。目的是對48位的輸入替代壓縮成32位的輸出。替代由8個S-盒進行。每個S-盒有6位輸入，4位輸出。S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒848位輸入32位輸出S-盒代換S-盒是進行了壓縮后的密鑰（56位→48位）與擴展42P-盒置換1672021291228171152326518311028241432273919133062211425對S-盒的32位輸出進行一次換位P-盒置換167202129122817115232651843DES的安全性1.對于其設(shè)計目標(biāo)，DES是安全的DES綜合運用了置換、替代和代數(shù)等多種密碼技術(shù)，是一種乘積密碼。DSE算法中除了S盒是非線性變換外，其余變換均為線性變換，所以DES安全的關(guān)鍵是S盒。這個非線性變換的本質(zhì)是數(shù)據(jù)壓縮，它把6位的數(shù)據(jù)壓縮成4位數(shù)據(jù)。S盒為DES提供了多種安全的密碼特性。S盒用來提供混淆，使明文、密鑰、密文之間的關(guān)系錯綜復(fù)雜，而P置換用來提供擴散，把S盒提供的混淆作用充分擴散開來。這樣，S盒和P置換互相配合，形成了很強的抗差分攻擊和抗線性攻擊能力，其中抗差分攻擊能力更強一些。DES的子密鑰產(chǎn)生和使用很有特色，它確保了原密鑰中的各位的使用次數(shù)基本相等。實驗證明，56位密鑰的每一位的使用次數(shù)都在12-15之間。應(yīng)用實踐證明DES作為商用密碼，用于其設(shè)計目標(biāo)是安全的。除因密鑰太短經(jīng)不起當(dāng)今網(wǎng)絡(luò)計算和并行計算的窮舉攻擊外，沒有發(fā)現(xiàn)DES存在其他嚴(yán)重的安全缺陷。DES的安全性1.對于其設(shè)計目標(biāo)，DES是安全的44DES的安全性2.DES存在的安全弱點1）密鑰較短2）存在弱密鑰和半弱密鑰DES存在一些弱密鑰和半弱密鑰。在16次加密迭代中分別使用不同的子密鑰是確保DES安全強度的一種重要措施，但實際上卻存在一些密鑰，由它們產(chǎn)生的16個子密鑰不是互不相同，而是有相重的。產(chǎn)生弱密鑰的原因是子密鑰產(chǎn)生算法中的C和D寄存器中的數(shù)據(jù)在循環(huán)移位下出現(xiàn)重復(fù)所致。據(jù)此，可推出以下四種弱密鑰（十六進制）：01010101010101011F1F1F1F1F1F1F1FE0E0E0E0E0E0E0E0FEFEFEFEFEFEFEFEDES的安全性2.DES存在的安全弱點45DES的安全性此外，DES還存在半弱密鑰。設(shè)k是給定的密鑰，如果由k所產(chǎn)生的子密鑰中存在重復(fù)者，但不是完全相同，則稱k為半弱密鑰。以下半弱密鑰所產(chǎn)生得16個子密鑰中只有兩種不同的子密鑰，每種出現(xiàn)8次：01FE01FE01FE01FEFE01FE01FE01FE011FE01FE01FE01FE0E01FE01FE01FE01F弱密鑰和半弱密鑰的存在無疑是DES的一個不足，但由于它們的數(shù)量與密鑰總數(shù)256相比仍是微不足道的，所以這并不構(gòu)成對DES太大的威脅，只要注意在實際應(yīng)用中不使用它們就可以了。3）存在互補對稱性設(shè)C=DES(M,K),則C’=DES(M’,K’),其中M’,C’,K’表示M,C,K的非，密碼學(xué)上稱這種特性為互補對稱性?；パa對稱性使DES在選擇明文攻擊下所需的工作量減半。DES的安全性此外，DES還存在半弱密鑰。設(shè)k是給定的密鑰，46其他對稱加密算法IDEA（internationaldataencryptionalgorithm，國際數(shù)據(jù)加密算法）分組加密算法，分組長度為64b，密鑰長度128b；核心由8輪迭代和一個輸出變換組成，能使明碼數(shù)據(jù)更好地擴散和混淆；運算過程只需使用下面三種簡單運算：·逐個的位異或；·模216加；·模（216+1）乘。有專利限制。AES（advancedencryptionstandard，高級加密標(biāo)準(zhǔn)）。分組算法，分組大小為128b密鑰長度可以是128b、192b或256b，分別稱為AES-128、AES-192、AES-256。無專利限制其他對稱加密算法IDEA（internationa472.3.2公開密鑰密碼的基本概念使用傳統(tǒng)密碼進行保密通信，通信雙發(fā)必須首先預(yù)約持有相同的密鑰才能進行。而私人和商業(yè)之間想通過通信工具洽談生意又要保持商業(yè)秘密，有時很難做到事先預(yù)約密鑰。另外，對于大型計算機網(wǎng)絡(luò)，設(shè)有n個用戶，任意兩個用戶之間有可能進行通信，共有n(n-1)/2種不同的通信方式，當(dāng)n較大時，這個數(shù)目很大。從安全角度考慮，密鑰應(yīng)當(dāng)經(jīng)常更換，這樣，在網(wǎng)絡(luò)上產(chǎn)生、存儲、分配并管理如此大量的密鑰，其復(fù)雜性和危險性巨大。1.公開密鑰密碼的基本思想將傳統(tǒng)密碼中密鑰k一分為二，分為加密密鑰Ke和解密密鑰Kd，并在計算復(fù)雜度上保證加密密鑰Ke在計算上不能推導(dǎo)出解密密鑰Kd。這樣，即使將公開Ke也不會暴露Kd，也不會損害密碼的安全。如此，就從根本上克服了傳統(tǒng)密碼在密鑰分配上的困難。2.3.2公開密鑰密碼的基本概念使用傳統(tǒng)密碼進行保密通信48一個公開密鑰密碼應(yīng)當(dāng)滿足以下三個條件：①解密算法D與加密算法E互逆，即對于所有明文M都有D(E(M,Ke),Kd)=M②在計算上不能由Ke求出Kd③算法E和D都是高效的條件②是公開密鑰密碼的安全條件，是公開密鑰密碼的安全基礎(chǔ)。而且也是最難滿足的。由于數(shù)學(xué)水平的限制，目前尚不能從數(shù)學(xué)上證明一個公開密鑰密碼完全滿足這一條件，而只能證明不滿足這一條件。條件③是公開密鑰密碼的實用條件，因為只有算法D和E都是高效的，密碼才能實際應(yīng)用。滿足以上三個條件，便可構(gòu)成一個公開密鑰密碼，而且這個密碼可以確保數(shù)據(jù)的秘密性。而如果還要求確保數(shù)據(jù)的真實性，則應(yīng)滿足第四個條件：④對于所有明文M都有E(D(M,Kd),Ke)=M條件④是公開密鑰密碼能夠確保數(shù)據(jù)真實性的基本條件。如果滿足了條件①、②和④，同樣也可構(gòu)成一個公開密鑰密碼，而且可以確保數(shù)據(jù)的真實性。如果同時滿足以上四個條件，則公開密鑰密碼可同時確保數(shù)據(jù)的秘密性和真實性。一個公開密鑰密碼應(yīng)當(dāng)滿足以下三個條件：492.基本工作方式設(shè)M為明文，C為密文，E為加密算法，D為解密算法，Ke為公開的加密密鑰，Kd為保密的解密密鑰，每個用戶都分配一對密鑰，而且將所有用戶的公開的加密密鑰存入共享的密鑰庫PKDB中。再設(shè)用戶A要把數(shù)據(jù)M安全保密地傳送給B，有以下三種通信協(xié)議：1）確保數(shù)據(jù)的秘密性A：從PKDB中查B公開的加密密鑰用B公開的加密密鑰加密M得到密文C把C發(fā)給BB：用自己保密的解密密鑰解密C，得到明文M由于只有用戶B才擁有保密的解密密鑰，而且由公開的加密密鑰在計算上不能推出保密的解密密鑰，所以只有用戶B才能獲得明文M，從而確保了數(shù)據(jù)的秘密性。然而，該通信協(xié)議并不能保證數(shù)據(jù)的真實性。因為PKDB是共享的，任何人都可以查到B公開的加密密鑰，因此任何人都可以冒充A發(fā)送假數(shù)據(jù)給B，而不被B發(fā)現(xiàn)。2.基本工作方式502）確保數(shù)據(jù)的真實性A：用自己保密的解密密鑰解密M，得到密文C

把C發(fā)給BB：從PKDB中查A公開的加密密鑰用A公開的加密密鑰加密C得到密文M由于只有A才擁有保密的解密密鑰，而且由A公開的加密密鑰在計算上不能推出保密的解密密鑰，所以只有用戶A才能發(fā)送數(shù)據(jù)M，任何人都不能冒充A發(fā)送M，從而保證了數(shù)據(jù)的真實性。但是，因為PKDB是共享的，任何人都可以獲得A公開的加密密鑰，所以任何人都可以獲得數(shù)據(jù)M3）同時確保數(shù)據(jù)的秘密性和真實性A：用自己保密的解密密鑰解密M，得到中間密文S

從PKDB中查B公開的加密密鑰用B公開的加密密鑰加密S得到密文C把C發(fā)給BB：用自己保密的解密密鑰解密C，得到中間密文S從PKDB中查A公開的加密密鑰，并用之加密S，得到明文M2）確保數(shù)據(jù)的真實性512.3.3RSA密碼RonaldL.RivestLeonardM.AdlemanRSA（Rivest,Shamir,Adleman）算法是1978年由R.Rivest、A.Shamir和I.Adleman提出的一種基于數(shù)論方法、也是理論上最為成熟的公開密鑰體制，并已經(jīng)得到廣泛應(yīng)用。AdiShamir

2.3.3RSA密碼RonaldL.RivestL52RSA數(shù)學(xué)基礎(chǔ)1.費爾瑪（Fermat）定理描述1：若p是素數(shù)，a是正整數(shù)且不能被p整除，則ap-1≡1modp。描述2：對于素數(shù)p，若a是任一正整數(shù)，則ap≡a（modp）。例2.1設(shè)p=3，a=2，則23-1=4≡1（mod3）或23=8≡2（mod3）。例2.2設(shè)p=5，a=3，則35-1=81≡1（mod5）或35=243≡3（mod5）。RSA數(shù)學(xué)基礎(chǔ)1.費爾瑪（Fermat）定理532.歐拉函數(shù)歐拉（Euler）函數(shù)φ(n)表示小于n，并與n互素的正整數(shù)的個數(shù)。例2.3φ(6)=2{1，5}；φ(7)=6{1，2，3，4，5，6}；φ(9)=6{1，2，4，5，7，8}。3.歐拉（Euler）定理歐拉定理：若整數(shù)a和m互素，則aφ(m)≡1(modm)例2.4設(shè)a=3，m=7，則有φ(7)=6，36=729，729≡1(mod7)例2.5設(shè)a=4，m=5，則有φ(5)=2，42=16，16≡1(mod5)2.歐拉函數(shù)54RSA密鑰的產(chǎn)生基本過程：①選兩個保密的大素數(shù)p和q（保密）。②計算n=pq（公開），φ(n)=(p-1)(q-1)（保密）。③隨機選取一整數(shù)e，滿足1<e<φ(n)且gcd(φ(n),e)=1（公開）。④計算d，滿足de≡1(modφ(n))（保密）。⑤得到一對密鑰：公開密鑰：{e,n}，秘密密鑰：{d,n}。例子：①選擇兩個素數(shù)p=7，q=17②計算n=pq=7×17=119計算n的歐拉函數(shù)φ(n)=(p-1)(q-1)=6×16=96。③從[0，95]間選一個與96互質(zhì)的數(shù)e=5④根據(jù)式5d=1mod96解出d=77，因為ed=5×77=385=4×96+1≡1mod96⑤得到公鑰PK=(e,n)={5,119}，密鑰SK={77,119}。RSA密鑰的產(chǎn)生基本過程：55RSA加密/解密過程基本過程：1）明文數(shù)字化，即將明文轉(zhuǎn)換成數(shù)字串2）分組。將二進制的明文串分成長度小于log2n的分組3）加密算法Ci=Mie（modn）最后得到的密文C由長度相同的分組Ci組成4）解密算法D(C)≡Cd(modn)RSA加密/解密過程基本過程：56RSA加密/解密過程例子：1）產(chǎn)生密鑰設(shè)：p=43,q=59,n=43×59=2537,

φ(n)=42×58=2436取e=13（與φ(n)沒有公因子）解方程de≡（mod2436）,2436=13×187+5,5=2436-13×187：13=2×5+3，3=13-2×51=3-2=3-(5-3)=2×3-5=2×(13-2×5)-5=2×13-5×5=2×13-5×(2436-13×187)=(187×5+2)×13-5×2436=937×13-5×2436即：937×13≡1(mod2436)故e=13，d=9372）加/解密明文：publickeyencryptions明文分組：publickeyencryptions明文數(shù)字化（按字母序，令a=00,b=01,c=02,…，y=24,z=25）：1520011108021004240413021724151908141418加密按照算法Mie（modn）=Ci，如152013（mod2537）=0095得到密文0095164814101299136513792333213217511289解密：按照算法Cie（modn）=Mi，如009513（mod2537）=1520。RSA加密/解密過程例子：57RSA密鑰的安全性小合數(shù)的因子分解是容易的，但大合數(shù)的因子分解卻是十分困難的。密碼分析者攻擊RSA密碼的一種可能的途徑是截獲密文C，從而求出明文M。因為M≡Cd(modn),n是公開的，要從C中求出明文M，必須先求出d，而d是保密。又因為ed≡1(modφ(n)),而e又是公開的，要從中求出d，必須先求出φ(n)，而φ(n)是保密的。又因為φ(n)=(p-1)(q-1)，則要從中求出必須先求出p和q，而p和q是保密的。又因為n=pq，這樣要從n中求出p和q，只有對n進行因子分解。而當(dāng)n足夠大時，這是很困難的RSA密鑰的安全性小合數(shù)的因子分解是容易的，但大合數(shù)的因子分582.4PGP2.4PGP592.5社會工程學(xué)密碼分析器2.5社會工程學(xué)密碼分析器60本講可選題1.古典密碼加解密算法的實現(xiàn)，要求如下：①具有置換密碼、單表替代密碼中的加法密碼、乘法密碼和仿射密碼、Vigenere密碼以及代數(shù)密碼的加密和解密功能；②具有加解密速度統(tǒng)計功能；③具有良好的人機界面。2.古典密碼破譯算法的實現(xiàn)，要求如下：①具有置換密碼、單表替代密碼中的加法密碼、乘法密碼和仿射密碼、Vigenere密碼以及代數(shù)密碼的破解算法；②具有破解速度統(tǒng)計功能；③具有良好的人機界面。3.以DES作為加密算法開發(fā)文件加密軟件系統(tǒng)，軟件要求如下：①具有文件加密和解密功能；②具有加解密速度統(tǒng)計功能；③具有良好的人機界面。本講可選題1.古典密碼加解密算法的實現(xiàn)，要求如下：614.密鑰管理，要求如下：①陳述現(xiàn)有的各種密鑰管理機制，并比較其優(yōu)劣；②陳述正確、條理清晰，具有反映個人思考所得的內(nèi)容。5.數(shù)據(jù)完整性：HASH函數(shù)①陳述數(shù)據(jù)完整性的基本概念，比較各種HASH函數(shù)的優(yōu)劣；②陳述正確、條理清晰，具有反映個人思考所得的內(nèi)容。6.數(shù)字簽名①陳述數(shù)字簽名的基本概念，并在此基礎(chǔ)上陳述如何利用公鑰實現(xiàn)數(shù)字簽名，就不可否認簽名和盲簽名機制進行討論②比較美國數(shù)字簽名標(biāo)準(zhǔn)DSS和俄羅斯數(shù)字簽名標(biāo)準(zhǔn)GOST；③陳述正確、條理清晰，具有反映個人思考所得的內(nèi)容。7.認證①陳述身份認證、站點認證、報文認證的基本知識，并就Kerberos認證系統(tǒng)進行探討；②陳述正確、條理清晰，具有反映個人思考所得的內(nèi)容。4.密鑰管理，要求如下：62演講完畢，謝謝觀看！演講完畢，謝謝觀看！63第2講密碼學(xué)及其工具2.1密碼學(xué)基本概念2.2古典密碼2.3DES與RSA2.4PGP2.5社會工程學(xué)密碼分析器第2講密碼學(xué)及其工具2.1密碼學(xué)基本概念642.1密碼學(xué)基本概念2.1.1密碼體制2.1.2密碼分析2.1.3密碼學(xué)的理論基礎(chǔ)2.1密碼學(xué)基本概念2.1.1密碼體制65密碼學(xué)(Cryptology)是一門古老的科學(xué)。大概自人類社會出現(xiàn)戰(zhàn)爭便產(chǎn)生了密碼，以后逐漸形成了一門獨立的學(xué)科。在密碼學(xué)形成和發(fā)展歷程中，科學(xué)技術(shù)的發(fā)展和戰(zhàn)爭的刺激都起了積極的推動作用。電子計算機一出現(xiàn)便被用于密碼破譯，使密碼進入電子時代，其后有幾個值得關(guān)注的里程碑：1949年香農(nóng)發(fā)表《保密系統(tǒng)的通信理論》，把密碼學(xué)置于堅實的數(shù)學(xué)基礎(chǔ)上，標(biāo)志著密碼學(xué)作為一門科學(xué)的形成；1976年W.Diffie和M.Hellman提出公開密鑰密碼，從而開創(chuàng)了一個密碼新時代；1977年美國聯(lián)邦政府頒布數(shù)據(jù)加密標(biāo)準(zhǔn)DES；1994年美國聯(lián)邦政府頒布密鑰托管加密標(biāo)準(zhǔn)EES，同年頒布數(shù)字簽名標(biāo)準(zhǔn)DSS，2001年頒布高級加密標(biāo)準(zhǔn)AES；目前，量子密碼因其具有可證明的安全性，同時還能對竊聽行為進行檢測，從而研究廣泛；生物信息技術(shù)的發(fā)展也推動了DNA計算機和DNA密碼的研究密碼學(xué)(Cryptology)是一門古老的科學(xué)。大概自人類社66自古以來，密碼主要用于軍事、政治、外交等要害部門，因而密碼學(xué)的研究工作本身也是秘密進行的。后來，隨著計算機網(wǎng)絡(luò)的普及，電子政務(wù)、電子商務(wù)和電子金融等對確保信息安全的需求的增加，民間出現(xiàn)了一些不從屬于保密機構(gòu)的密碼學(xué)者。實踐證明，正是這種公開研究和秘密研究相結(jié)合的局面促進了今天密碼學(xué)得空前繁榮。研究密碼編制的科學(xué)稱為密碼編制學(xué)(Cryptography)；研究密碼破譯的科學(xué)稱為密碼分析學(xué)(Cryptannalysis)；密碼編制學(xué)和密碼分析學(xué)共同組成密碼學(xué)(Cryptology)。自古以來，密碼主要用于軍事、政治、外交等要害部門，因而密碼學(xué)67密碼學(xué)的基本思想是偽裝信息，使未授權(quán)者不能理解它的真實含義。所謂偽裝就是對數(shù)據(jù)進行一組可逆的數(shù)學(xué)變換。偽裝前的原始數(shù)據(jù)稱為明文(Plaintext)，偽裝后的數(shù)據(jù)稱為密文(Ciphertext)，偽裝的過程稱為加密(Encryption)。加密在加密密鑰(Key)的控制下進行。用于對數(shù)據(jù)加密的一組數(shù)學(xué)變換稱為加密算法發(fā)信者將明文數(shù)據(jù)加密成密文，再將密文數(shù)據(jù)送入網(wǎng)絡(luò)傳輸或存入計算機文件，而且只給合法收信者分配密鑰。合法收信者接收到密文后，施行與加密變換相逆的變換，去掉密文的偽裝恢復(fù)出明文，這一過程稱為解密(Decryprion)。解密在解密密鑰的控制下進行。用于解密的一組數(shù)學(xué)變換稱為解密算法，而且解密算法是加密算法的逆。密碼學(xué)的基本思想是偽裝信息，使未授權(quán)者不能理解它的真實含義。682.1.1密碼體制明文加密算法信道明文解密算法MM攻擊者CC加密密鑰加密密鑰安全信道密鑰KKeKd2.1.1密碼體制明加信明解MM攻擊者CC加密密鑰加密密69一個密碼系統(tǒng)通常簡稱為密碼體制(Cryptosystem)，由五部分組成：①明文空間M，它是全體明文的集合；②密文空間C，它是全體密文的集合；③密鑰空間K，它是全體密鑰的集合。其中，每一個密鑰K均由加密密鑰Ke和解密密鑰Kd組成，即K=<Ke,Kd>④加密算法E，它是一族由M到C的加密變換；⑤解密算法D，它是一族由C到M的解密變換。對于明文空間M中的每個明文，加密算法E在密鑰Ke的控制下將明文M加密為密文C：C=E(M,Ke)(2-1)而解密算法D在密鑰Kd的控制下，解密C成明文M:M=D(C,Kd)=D(E(M,Ke),Kd)(2-2)一個密碼系統(tǒng)通常簡稱為密碼體制(Cryptosystem)，70如果一個密碼體制的Ke=Kd，或者由其中一個很容易推出另一個，則稱該密碼體制為單密鑰密碼體制或?qū)ΨQ密碼體制或傳統(tǒng)密碼體制，否則稱雙密鑰密碼體制。進而，如果在計算上Kd不能由Ke推出，這樣，將Ke公開也不會損害Kd的安全，于是便可將Ke公開。這種密碼體制稱為公開密鑰密碼體制，簡稱公開密碼體制。根據(jù)明密文的劃分和密鑰的使用不同，可將密碼體制分為分組密碼和序列密碼體制。設(shè)M為明文，分組密碼將M劃分稱一系列的明文塊Mi，通常每塊包含若干位或字符，并且每一塊Mi都用同一個密鑰Ke進行加密，即M=(M1,M2,…,Mn) C=(C1,C2,…,Cn)其中，Ci=E(Mi,Ke)(i=1,2,…,n)如果一個密碼體制的Ke=Kd，或者由其中一個很容易推出另一個71而序列密碼將明文和密鑰都劃分成為或字符的序列，并且對明文序列中的每一個位或字符都用密鑰序列中的對應(yīng)分量進行加密，即M=(m1,m2,…,mn) Ke=(ke1,ke2,…,ken) C=(c1,c2,…,cn)其中，ci=E(mi,kei)(i=1,2,…,n)分組密碼每一次加密一個明文塊，而序列密碼每一次加密一位或一個字符。序列密碼是要害部門使用的主流密碼，而商用領(lǐng)域則多用分組密碼。根據(jù)加密算法在使用過程中是否變化，可將密碼體制分為固定算法密碼體制和演化密碼體制。固定算法密碼體制的加解密算法固定不變；而演化密碼體制將密碼學(xué)和演化計算相結(jié)合，使得在加密過程中加密算法也不斷演化。而序列密碼將明文和密鑰都劃分成為或字符的序列，并且對明文序列72

2.1.2密碼分析如果能夠根據(jù)密文系統(tǒng)地確定出明文或密鑰，或者能夠根據(jù)明文-密文對系統(tǒng)地確定出密鑰，則稱這個密碼是可破譯的。研究密碼破譯的科學(xué)稱為密碼分析學(xué)。密碼分析者攻擊密碼的方法主要有三種：1）窮舉攻擊窮舉攻擊是指密碼分析者采用依次試遍所有可能的密鑰對所獲得的密文進行解密，直至得到正確的明文；或者用一個確定的密鑰對所有可能的明文進行加密，直至得到所獲得的密文。理論上，對于任何使用密碼只要有足夠的資源都可以用窮舉攻擊將其攻破。從平均角度講，采用窮舉攻擊破譯一個密碼必須試遍所有可能密鑰的一半。窮舉攻擊所花費的時間等于嘗試次數(shù)乘以一次解密或加密所需的時間?？梢酝ㄟ^增大密鑰量或加大解密或加密算法的復(fù)雜性來對抗窮舉攻擊。

2.1.2密碼分析如果能夠根據(jù)密文系統(tǒng)地確定出明文或密732）統(tǒng)計分析攻擊統(tǒng)計分析攻擊是指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。統(tǒng)計分析攻擊在歷史上為破譯古典密碼作出過很大貢獻。對抗統(tǒng)計分析攻擊的方法是設(shè)法使明文的統(tǒng)計特性不帶入密文。這樣，密文不帶有明文的痕跡，從而使統(tǒng)計分析攻擊成為不可能。3）數(shù)學(xué)分析攻擊數(shù)學(xué)分析攻擊是指密碼分析者對加解密算法的數(shù)學(xué)基礎(chǔ)和某些密碼學(xué)特性，通過數(shù)學(xué)求解的方法來破譯密碼。數(shù)學(xué)分析攻擊是對基于數(shù)學(xué)難題的各種密碼的主要威脅，為此，應(yīng)當(dāng)選用具有堅實數(shù)學(xué)基礎(chǔ)和足夠復(fù)雜的加解密算法。2）統(tǒng)計分析攻擊74此外，根據(jù)密碼分析者可利用的數(shù)據(jù)資源來分類，可將攻擊密碼的類型分為以下四種：1）僅知密文攻擊僅知密文攻擊是指密碼分析者僅根據(jù)截獲的密文來破譯密碼。2）已知明文攻擊已知明文攻擊是指密碼分析者根據(jù)已知的某些明文-密文對來破譯密碼。3）選擇明文攻擊選擇明文攻擊是指密碼分析者能夠選擇明文并獲得相應(yīng)的密文。4）選擇密文攻擊選擇密文攻擊是指密碼分析者能夠選擇密文并獲得相應(yīng)的明文。這種攻擊主要攻擊公開密鑰密碼體制，特別是攻擊其數(shù)字簽名。此外，根據(jù)密碼分析者可利用的數(shù)據(jù)資源來分類，可將攻擊密碼的類75一個密碼，如果無論密碼分析者截獲多少密文和用什么技術(shù)方法進行攻擊都不能被攻破，則稱該密碼是絕對不可破譯的。絕對不可破譯的密碼在理論上是存在的，這就是著名的“一次一密”密碼。但是，由于密鑰管理上的困難，“一次一密”密碼是不實用的。理論上，如果能夠獲得足夠的資源，那么任何實際可使用的密碼又都是可破譯的。如果一個密碼，不能被密碼分析者根據(jù)可利用的資源所破譯，則稱其是計算上不可破譯的。因為任何秘密都有其時效性，因此，對我們更有意義的是在計算上不可破譯的密碼。一個密碼，如果無論密碼分析者截獲多少密文和用什么技術(shù)方法進行762.1.3密碼學(xué)的理論基礎(chǔ)1949年，shannon發(fā)表的《保密系統(tǒng)的通信理論》從信息論的角度對信息源、密鑰、加密和密碼分析進行了數(shù)學(xué)分析，用不確定性和唯一解距離來度量密碼體制的安全性，闡明了密碼體制、完善保密、純密碼、理論保密和實際保密等重要概念，把密碼置于堅實的數(shù)學(xué)基礎(chǔ)之上，標(biāo)志著密碼學(xué)作為一門獨立學(xué)科的形成。從此，信息論成為密碼學(xué)重要的理論基礎(chǔ)之一。Shannon建議采用擴散、混淆和乘積迭代的方法設(shè)計密碼，并且以“揉面團”的過程形象地比喻擴散、混淆和乘積迭代的概念。所謂擴散就是將每一位明文和密鑰數(shù)字的影響擴散到盡可能多得密文數(shù)字中。理想狀態(tài)下，明文和密鑰的每一位都影響密文的每一位，一般稱這種情形達到“完備性”。所謂混淆就是是密文和密鑰之間的關(guān)系復(fù)雜化。密文和密鑰之間的關(guān)系越復(fù)雜，則密文和明文之間、密文和密鑰之間的統(tǒng)計相關(guān)性越小，從而使統(tǒng)計分析不能奏效。設(shè)計一個復(fù)雜密碼一般是比較困難的，利用乘積迭代方法對簡單密碼進行組合迭代，可以得到理想的擴散和混淆，從而可以得到安全的密碼。2.1.3密碼學(xué)的理論基礎(chǔ)1949年，shannon發(fā)表77計算復(fù)雜性理論是密碼學(xué)的另一個理論基礎(chǔ)。為計算求解一類問題，總需要一定量的時間資源和空間資源。消耗資源的多少取決于要求解問題的規(guī)模大小。設(shè)要求解的問題規(guī)模（如，輸入變量的個數(shù)或輸入長度）為n，若對于所有的n和所有長度為n的輸入，計算最多要用f(n)步完成，則稱該問題的計算復(fù)雜度為f(n)。若f(n)為n的多項式，則稱其為多項式復(fù)雜度。粗略的講，計算機可以在多項式時間復(fù)雜度內(nèi)解決的問題稱為P類問題；否則，為NP類問題。P類問題是計算機可計算的，而NP問題是計算機不可計算的困難問題。NP問題中最難得問題稱為NP完全問題，即NPC問題。Shannon指出設(shè)計一個安全的密碼本質(zhì)上就是要尋找一個難解的問題。這樣，計算復(fù)雜性理論的發(fā)展將直接影響密碼的安全。此外，密碼的設(shè)計應(yīng)該遵循公開設(shè)計原則。密碼體制的安全僅依賴于密鑰的保密，而不應(yīng)依賴于對算法的保密。當(dāng)然，密碼設(shè)計的公開原則并不等于所有的密碼在應(yīng)用時都要公開加密算法。也就是說，在公開的原則下設(shè)計密碼，在實際使用時對算法保密，將會更加安全。計算復(fù)雜性理論是密碼學(xué)的另一個理論基礎(chǔ)。為計算求解一類問題，782.2古典密碼2.2.1置換密碼2.2.2替代密碼2.2.3代數(shù)密碼2.2.4古典密碼的統(tǒng)計分析2.2古典密碼2.2.1置換密碼792.2.1置換密碼把明文中的字母重新排列，字母本身不變，但其位置改變，這樣編成的密碼稱為置換密碼。最簡單的置換密碼是把明文中字母順序顛倒過來，然后截成固定長度的字母組作為密文。例如：明文：明晨5點發(fā)動反攻。 mingchenwudianfadongfangong密文：gnognafgnodafnaiduwnehcgnim倒序的置換密碼顯然是很弱的。另一種置換密碼是把明文按某一順序排成一個矩陣，其中不足部分用Ф填充，而Ф是明文中不會出現(xiàn)的一個符號；然后按另一個順序選出矩陣中的字母以形成密文，最后截成固定長度的字母組作為密文。2.2.1置換密碼把明文中的字母重新排列，字母本身不變，80明文：WHATCANYOULEARNFROMTHISBOOK”明文矩陣：舉例明文WHATCANYOULEARNFROMTHISBOOKФФФФФ選出順序：按列密文：WOROHUOOALMKTETФCAHФARIФNNSФYFBФ可以看出，改變矩陣的大小和選出順序可以得到不同形式的密碼。一種巧妙的方法：首先選一個詞語作為密鑰，去掉重復(fù)字母；然后按字母的字典順序給密鑰字母編號，并按照密鑰的長度把明文排列成矩陣；最后按照數(shù)字序列中的數(shù)字順序按列選出密文明文：WHATCANYOULEARNFROMTHI81密鑰：k=computer明文：WHATCANYOULEARNFROMTHISBOOK”按密鑰排列明文：舉例密鑰COMPUTER順序號14358726明文WHATCANYOULEARNFROMTHISBOOKФФФФФ密文：WORONNSФALMKHUOOTETФYFBФARIФCAHФ密鑰：k=computer舉例密鑰COMPUTER順序號822.2.2替代密碼首先構(gòu)造一個或多個密文字母表，然后用密文字母表中的字母或字母組來替代明文字母或字母組，各字母或字母組的相對位置不變，但其本身改變，這樣編成的密碼稱為替代密碼。按照替代所使用的密文字母表的個數(shù)可將替代密碼分為單表替代密碼、多表替代密碼和多名替代密碼1.單表替代密碼又稱為簡單替代密碼。它只使用一個密文字母表，并且用密文字母表中的一個字母來替代一個明文字母表中的一個字母。設(shè)A={a0,a1,…,an-1}; B={b0,b1,…,bn-1}定義一個由A到B的一一映射：f:AB,即f(ai)=bi設(shè)明文M=(m0,m1,…,mn-1)，則密文C=(f(m0),f(m1),…,f(mn-1))2.2.2替代密碼首先構(gòu)造一個或多個密文字母表，然后用密831）加法密碼加法密碼的映射函數(shù)：f(ai)=bi=aj，j=i+kmodn,k是0<k<n的正整數(shù)著名的加法密碼是古羅馬的凱撒大帝使用的密碼Caesar密碼取k=3，因此其密文字母表就是把明文字母表循環(huán)右移3位后得到的字母表。2）乘法密碼乘法密碼的映射函數(shù)：f(ai)=bi=aj，j=ikmodn其中，要求k和n互素。因為僅當(dāng)(k,n)=1時，才存在兩個整數(shù)x,y，使得xk+yn=1，才能有xk=1modn，才有i=xjmodn，密碼才能正確解密。例如，當(dāng)用英文字母表作為明文字母表而取k=13時，因為(13,26)=13≠1，會出現(xiàn)：f(A)=f(C)=f(E)=……=f(Y)=Af(B)=f(D)=f(F)=……=f(Z)=N這樣，密文字母表變?yōu)锽={A,N,A,N,A,N,……A,N}1）加法密碼843）仿射密碼乘法密碼和加法密碼相結(jié)合就構(gòu)成了仿射密碼。仿射密碼的映射函數(shù)：f(ai)=bi=aj，j=ik1+k0modn其中，要求k1和n互素，0<=k0<n,且不允許同時有k1=1k0=0。4）密鑰詞語替代密碼首先隨機選用一個詞組或短語作為密鑰，去掉重復(fù)字母，把結(jié)果作為矩陣的第一行；其次，在明文字母表中去掉矩陣第一行中的字母，并將剩余字母依次寫入矩陣的其余行；最后按某一順序從矩陣中取出字母構(gòu)成密文字母表。例如：密鑰：HONGYE矩陣：HONGYE 選出順序：按列ABCDFIJKLMPQ RSTUVW XZ3）仿射密碼852.多表替代密碼簡單替代密碼很容易被破譯，提高替代密碼強度的一種方法是采用多個密文字母表，使明文中的每個字母都有很多種可能的字母來替代。構(gòu)造d個密文字母表：Bj={bj0,bj1,…,bjn-1},j=0,1,…,d-1定義d個映射：fj:ABj,即fj(ai)=bji設(shè)明文M=(m0,m1,…,md-1,md,…,mn-1)則密文C=(f0(m0),f1(m1