現(xiàn)代密碼學(第一章)

第一章：密碼學基礎一、信息安全的基本概念二、密碼體制的分類三、古典密碼四、密碼分析2023/2/21一、信息安全的基本概念信息的載體信息的存放地點稱為媒質(zhì)。通信伙伴之間有一條傳送信息的通道，稱為信道。媒質(zhì)和信道統(tǒng)稱為信息的載體。通常：媒質(zhì)是開放的，共享的，因而是不安全的；信道也是不安全的公共信道。2023/2/22一、信息安全的基本概念對信息的載體存在兩種攻擊：（1）被動攻擊。攻擊者通過各種辦法（如搭線竊聽，電磁竊聽，聲音竊聽，非法訪問等）來非法截收信息。（2）主動攻擊。攻擊者對載體中的信息進行非法篡改（如刪除、增添、重放、偽造等）。2023/2/23一、信息安全的基本概念（為了有效地保護信息，抵抗被動攻擊和主動攻擊，必須使用密碼技術。認識一下名詞）密碼學(Cryptology)：研究信息系統(tǒng)安全保密的科學。它包含兩個分支，密碼編碼學(Cryptography)，對信息進行編碼以保護信息的一門學問。密碼分析學(Cryptanalysis)，研究分析破譯密碼的學問。2023/2/24一、信息安全的基本概念密碼技術分為兩個部分，第一部分是信息保密，第二部分是信息認證。信息保密用來抵抗被動攻擊。信息認證用來抵抗主動攻擊。2023/2/25一、信息安全的基本概念信息保密的功能：信息的加密和解密。（使得除通信伙伴以外的其他人無法獲取信息。）信息認證的功能：對信息的認證，對發(fā)送信息者的身份的認證，對接收信息者的身份的認證。（使得對信息的篡改會被立即發(fā)現(xiàn)。）2023/2/26一、信息安全的基本概念信息保密系統(tǒng)信息保密系統(tǒng)又稱為加密系統(tǒng)。該系統(tǒng)被描述如下。用戶Alice和用戶Bob是一對通信伙伴。Eve是攻擊者（違法入侵者）。2023/2/27一、信息安全的基本概念Alice欲發(fā)送一個消息m給Bob。m稱為明文。Alice使用加密密鑰z，使用加密算法E，對明文m做以下的變換，稱為加密變換：c=E(m,z)c稱為密文。Alice將密文c通過不安全的公共信道發(fā)送給Bob。Bob使用解密密鑰k，使用解密算法D，對密文c做以下的反變換，稱為解密變換：m=D(c,k)于是Bob獲得了明文m。2023/2/28一、信息安全的基本概念參數(shù)與計算的小結明文m，密文c；加密算法E，解密算法D；加密密鑰z，解密密鑰k；加密變換c=E(m,z)，將明文m變?yōu)槊芪腸；解密變換m=D(c,k)，將密文c變?yōu)槊魑膍。2023/2/29一、信息安全的基本概念攻擊者Eve所擁有的基本資源Eve在不安全的公共信道上截獲了密文c。Eve知道加密算法E和解密算法D。攻擊者Eve可能擁有的更多資源Eve可能知道密文c所對應的明文m。（此時所進行的攻擊稱為已知明文攻擊）Eve可能擁有強大的計算能力。Eve可能繳獲了一臺加密機（也稱為加密黑盒子），可以任意地輸入明文，輸出密文。（此時所進行的攻擊稱為選擇明文攻擊）2023/2/210一、信息安全的基本概念攻擊者Eve不可能擁有的資源Eve不知道加密密鑰z和解密密鑰k。（事實上，在進行安全性分析時，有時也假設Eve知道了密鑰的一部分，但決不能全部知道）攻擊者Eve的目的此時Eve是被動攻擊者，他的目的是試圖獲取明文的信息。2023/2/211一、信息安全的基本概念攻擊者Eve攻擊成功的標志Eve的思路是“不拘一格”。只要Eve以某種方式獲取了明文的一定量的信息，就可以算作一種攻擊成功。但“攻擊成功”的程度有高低之分。比如：能夠持續(xù)不斷地直接獲取明文是最高的攻擊成功；掌握在未來獲取明文的技巧則是低一級的攻擊成功；獲得明文的某些統(tǒng)計特性是更低一級的攻擊成功。2023/2/212一、信息安全的基本概念注解一：關于加密算法E和解密算法D從商用的角度出發(fā)，要求加解密算法（E，D）應該是公共的標準算法，是公開的。因此，包括攻擊者Eve在內(nèi)的所有人都知道加解密算法（E，D）。要求安全性不依賴于加解密算法（E，D）是否保密，而僅僅依賴于密鑰是否保密。2023/2/213一、信息安全的基本概念注解二：關于已知明文攻擊如果每一次加密/解密過程，都要選擇一次加解密密鑰（z，k），則加解密方式稱為一次一密的。一次一密的加解密方式通常具有很好的安全性。但是需要頻繁地更換密鑰，每次通信之前都需要通信伙伴之間進行協(xié)商來確定新的密鑰（z，k）。因而一次一密的加解密方式是不實用的。2023/2/214一、信息安全的基本概念如果加解密密鑰（z，k）在多次加密/解密過程中反復地重復使用，則加解密方式稱為多次一密的?，F(xiàn)有的實用加解密方式都是多次一密的。多次一密的加解密方式極大地省卻了通信伙伴的工作量。但同時，多次一密的加解密方式使得攻擊者增加了幾種新的攻擊手段。其中包括：已知明文攻擊。2023/2/215一、信息安全的基本概念設攻擊者Eve截獲了密文c，并且知道了密文c所對應的明文m。（這種情況是怎樣發(fā)生的呢？當明文m是已經(jīng)過期的消息，可能無法再保密，也可能必須將其公開。因此，這種情況是經(jīng)常發(fā)生的）于是：在解密方程m=D(c,k)中，Eve知道m(xù)和c，僅僅不知道解密密鑰k。在加密方程c=E(m,z)中，Eve知道m(xù)和c，僅僅不知道加密密鑰z。2023/2/216一、信息安全的基本概念如果Eve從解密方程m=D(c,k)中計算出解密密鑰k，則Eve今后就可以像Bob一樣對任何密文c’進行解密：m’=D(c’,k)。如果Eve從加密方程c=E(m,z)中計算出加密密鑰z，則Eve今后就可以像Alice一樣對任何明文m’進行加密：c’=E(m’,z)。2023/2/217一、信息安全的基本概念還可以給更加寬松的條件。設攻擊者Eve獲得了以往廢棄的n組明文/密文對：（m1，c1），（m2，c2），…，（mn，cn）。于是Eve獲得了關于解密密鑰k的方程組：m1=D(c1,k)，m2=D(c2,k)，…，mn=D(cn,k)。（n越大，解密密鑰k就越容易確定。）2023/2/218一、信息安全的基本概念以上就是已知明文攻擊。要抵抗已知明文攻擊，必須精心地設計加解密算法（E，D）。（能抵抗已知明文攻擊的加解密算法(E,D)并不是很容易構造的。）例1設：加密密鑰等于解密密鑰：z=k；加密算法為c=m+z；對應的解密算法為m=c-k=c-z。（普通加減法）注意到此時k=c-m。這就是說，只要知道了一組明文/密文對（m，c），就能計算出解密密鑰k。2023/2/219一、信息安全的基本概念例2設：加密密鑰等于解密密鑰，z=(z1,z2)；加密算法為c=z1m+z2

；對應的解密算法為m=(c-z2)/z1。（普通加減乘除法）設攻擊者Eve獲得了以往廢棄的2組明文/密文對：（m1，c1），（m2，c2）。注意到此時c1=z1m1+z2

；

c2=z1m2+z2

。這是一個關于密鑰(z1,z2)的二元一次方程組，能計算出(z1,z2)

。2023/2/220一、信息安全的基本概念可以看出，以上兩個例子所用的加解密算法都不能抵抗已知明文攻擊，因此不能用作多次一密的加解密方式。2023/2/221一、信息安全的基本概念注解三：已知明文攻擊的一些弱化形式設攻擊者Eve知道了以往的一個密文c以及c所對應的明文m。Eve又截獲了一個新的密文c’，Eve試圖猜測出c’所對應的明文m’。如果加解密算法設計得“不好”，則密鑰對明文的覆蓋就可能出現(xiàn)漏洞。此時由{m,c,c’}猜測出c’所對應的明文m’就會變得容易得多。可能出現(xiàn)以下的現(xiàn)象：2023/2/222一、信息安全的基本概念（1）當c’與c的“距離很近”時，m’與m也“距離很近”，而無論密鑰是什么值。（2）當c’與c具有某種固定的關系A時，m’與m具有某種固定的關系B，而無論密鑰是什么值。（3）當c’與c具有某種固定的關系A時，m’與m“以很大的概率”

具有某種固定的關系B，而無論密鑰是什么值。（4）當密鑰的可能變化范圍（密鑰量）太小時，攻擊者Eve可以窮舉搜索密鑰。2023/2/223一、信息安全的基本概念（簡單介紹）為了抵抗諸如此類的攻擊，以便適用于多次一密，加解密算法應該滿足：（1）具有良好的“混淆性”（confusion）和“擴散性”（diffusion）；（2）具有良好的“非線性性”（non-linearity）；（3）具有良好的“差分均勻性”（differencebalance）。（4）密鑰的可能變化范圍（密鑰量）應該大到不可能窮舉搜索密鑰（bruteforcesearch）。2023/2/224一、信息安全的基本概念2023/2/225二、密碼體制的分類密碼體制加解密算法的專業(yè)術語為”密碼體制”。從原理上，密碼體制可以分為兩大類：（1）單鑰密碼體制。（又稱為對稱密碼體制）（2）雙鑰密碼體制。（又稱為非對稱密碼體制，也稱為公鑰密碼體制）2023/2/226二、密碼體制的分類單鑰密碼體制單鑰密碼體制的加密密鑰z和解密密鑰k能夠簡單地相互推導出來。換句話說：Alice知道加密密鑰z，她當然也就知道解密密鑰k；Bob知道解密密鑰k，他當然也就知道加密密鑰z

。再換句話說，Alice和Bob的地位是對稱的，可以雙向地發(fā)送和接收保密信息。

（其實在一般實用情形之下，總有z=k

）2023/2/227二、密碼體制的分類雙鑰密碼體制（公鑰密碼體制）在雙鑰密碼體制中，要從加密密鑰z推導出解密密鑰k是很困難的。（雖然，也許加密密鑰z唯一地確定了解密密鑰k

）具體地說：Bob擁有加密密鑰z和解密密鑰k。加密密鑰z稱為Bob的公鑰，解密密鑰k稱為Bob的私鑰。Bob的公鑰z向大家公布。（像電話號碼一樣）Bob的私鑰k被Bob私藏。2023/2/228二、密碼體制的分類因此，大家都知道Bob的公鑰z，而只有Bob自己知道他的私鑰k。因此，大家都能夠用Bob的公鑰z將明文消息加密變?yōu)槊芪?，并把密文向Bob發(fā)送，而只有Bob自己能夠解密這些密文。因此，公鑰密碼體制除了具有信息保密的功能以外，還具有了一種信息認證功能：Alice用Bob的公鑰z加密一個消息，誰能把消息正確解密，Alice就認為誰是真正的Bob。2023/2/229二、密碼體制的分類公鑰密碼體制的原理：數(shù)學難題例如：大數(shù)分解問題；離散對數(shù)問題；背包問題；多項式的分解問題；格的最小向量問題；等等。2023/2/230二、密碼體制的分類單鑰密碼體制與雙鑰密碼體制的比較單鑰密碼體制雙鑰密碼體制一對密鑰可供一對通信伙伴雙向使用。一對密鑰可供多用戶向一用戶單向使用。無消息認證功能。有消息認證功能。n個用戶之間的保密通信，一共需要n(n-1)/2對密鑰。n個用戶之間的保密通信，一共需要n對密鑰。加解密算法簡潔快速。加解密算法相對較慢。通信伙伴之間需要協(xié)商密鑰。通信伙伴之間不用協(xié)商密鑰。2023/2/231三、古典密碼古典密碼是密碼學的淵源，這些密碼大都比較簡單，現(xiàn)在已很少采用了。然而，研究這些密碼的原理，對于理解、構造和分析現(xiàn)代密碼都是十分有益的。2023/2/232三、古典密碼明文字母表和密文字母表相同，為：Zq={0,1,

…,q-1}。明文是長為L的字母串，以m表示：m=(m0m1,…,mL-1)，其中每個mlZq，l=0，1，…，L-1。密文是長為L的字母串，以c表示：c=(c0,c1,...,cL-1)，其中每個clZq，l=0，1，…，L-1。2023/2/233三、古典密碼單表代換密碼單表代換密碼是字母表到自身的一個可逆映射f，f：ZqZq。令明文m=m0m1...，則相應密文為c=c0c1...=f(m0)f(m1)...2023/2/234三、古典密碼1．移位代換密碼(ShiftSubstitutionCipher)加密變換：f

(l)=(l+k)modq，0

l<q。其中k為密鑰，0k<q。解密變換：f

-1(l)=(l-k)modq，0

l<q。例如：凱撒(Caeser)密碼是對英文26個字母進行移位代換的密碼，其q=26。2023/2/235三、古典密碼選擇密鑰k=3，則有下述代換表：abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC明文：m=Casearcipherisashiftsubstitution密文：c=FDVHDUFLSKHULVDVKLIWVXEVWLWXWLRQ2023/2/236三、古典密碼2.乘數(shù)密碼(MultiplicativeCipher)：加密變換：f

(l)=lkmodq

，0l<q。其中k為密鑰，0k<q。顯然，僅當(k,q)=1（即k與q互素）時，f

(l)才是可逆變換。解密變換：f

-1(l)=lk-1modq，0

l<q。2023/2/237三、古典密碼我們知道，共有(q)個k滿足：0k<q，(k,q)=1。這就是說，乘數(shù)密碼共有(q)個不同的密鑰。對于q=26，(26)=(2×13)=(2)×(13)=12，即共有12個不同的密鑰k=1,3,5,7,9,11,15,17,19,21,23和25。此時對應的k-1modq=1,9,21,15,3,19,7,23,11,5,17和25。2023/2/238三、古典密碼3.仿射密碼(Affinecipher)加密變換：f

(l)=lk1+k0modq，0l<q。其中k1,k2Zq，(k1,q)=1，以[k1,k0]表示密鑰。當k0=0時就得到乘數(shù)密碼，當k1＝1時就得到移位密碼。q=26時可能的密鑰數(shù)為26×(26)＝26×12＝312個。

2023/2/239三、古典密碼4.多項式代換密碼(PolynomialSubstituteCipher)加密方程為：f

(l)=ktlt＋kt-1lt-1＋…＋k1l+k0modq。其中，kt,...,k0Zq，lZq。前三種密碼都可看作是它的特例。2023/2/240三、古典密碼5.密鑰短語密碼選一個英文短語，稱其為密鑰字(KeyWord)或密鑰短語(KeyPhrase)，如HAPPYNEWYEAR，去掉重復字母得HAPYNEWR。將它依次寫在明文字母表之下，而后再將字母表中未在短語中出現(xiàn)過的字母依次寫于此短語之后，就可構造出一個字母代換表，如下所示：

2023/2/241三、古典密碼A：abcdefghijklmnopqrstuvwxyzA’：HAPYNEWRBCDFGIJKLMOQSTUVKZ這是一種易于記憶而又有多種可能選擇的密碼。用不同的密鑰字就可得到不同的代換表。q=26時將可能有26!≈4×1026種。其中絕大多數(shù)代換都是好的。是一種靈活變化密鑰的代換密碼。2023/2/242三、古典密碼用現(xiàn)代密碼學的眼光觀察單表代換密碼設單表代換密碼用于多次一密的加解密方式，以下對其進行已知明文攻擊。Eve截獲了一段密文，并獲得了該段密文所對應的明文。一、只要密文中含有q個不同的字母（因此對應的明文中也含有q個不同的字母），則加密變換f被確定。2023/2/243三、古典密碼二、對于移位代換密碼，只要密文中含有1個字母（對應的明文中也含有1個字母），則密鑰k被確定。三、對于乘數(shù)密碼，只要密文中含有1個字母（對應的明文中也含有1個字母），則密鑰k被確定。四、對于仿射密碼，只要密文中含有2個不同的字母（對應的明文中也含有2個不同的字母），則密鑰[k1,k0]被確定。2023/2/244三、古典密碼五、對于多項式代換密碼，只要密文中含有min{t+1,q}個不同的字母（對應明文中也含有min{t+1,q}個不同的字母），則密鑰[kt,...,k0]被確定。綜上所述，只要密文中含有至多q個不同的字母，單表代換密碼體制就被攻破了。2023/2/245三、古典密碼多表代換密碼多表代換密碼是字母表Zq={0,1,

…,q-1}到自身的d個可逆映射f0，f1，...，fd-1，在加密時循環(huán)排列使用。令明文m=m0m1...，則相應密文為c=c0c1...=f0(m0)f1(m1)...fd-1(md-1)f0(md)f1(md+1)...2023/2/246三、古典密碼1.維吉尼亞密碼可逆映射f0，f1，...，fd-1都是移位代換密碼，分別使用密鑰(k0,k1,…,kd-1)。令明文m=m0m1...，則相應密文為c=c0c1...=(m0+k0modq)(m1+k1modq)...(md-1+kd-1modq)(md+k0modq)(md+1+k1modq)...2023/2/247三、古典密碼對維吉尼亞密碼的討論設維吉尼亞密碼用于多次一密的加解密方式，對其進行已知明文攻擊。Eve截獲了一段密文，并獲得了該段密文所對應的明文。只要密文長度不小于d，密鑰(k0,k1,…,kd-1)就被確定。若d充分大，大到不可能截獲長度為d的密文（存儲量和時間限制），甚至可以設d“接近無窮大”。此時當然可以抵抗已知明文攻擊。2023/2/248三、古典密碼（注解：當d“接近無窮大”時，維吉尼亞密碼變成了現(xiàn)代密碼中的一種，我們稱之為流密碼或序列密碼。）但問題是，通信伙伴之間怎樣簡單快速地協(xié)商極長的密鑰序列(k0,k1,…,kd-1)？當然不能逐字母地協(xié)商密鑰。因為，如果攻擊者截獲長度為d的密文是不可能的（存儲量和時間限制），則通信伙伴協(xié)商出長度為d的密鑰也是不可能的。2023/2/249三、古典密碼一種辦法是：取(k0,k1,…,kd-1)為一本書，此時通信伙伴只需要相互告知該書的書名和版本號，因此使得密鑰協(xié)商簡單快速。這種辦法很容易進行局部破譯。設Eve截獲了一段長度為l的密文，并獲得了該段密文所對應的明文。Eve因此也獲得了密鑰中長度為l的一段(k0,k1,…,kl-1)。l與d相比當然是微不足道的。2023/2/250三、古典密碼如果該段是名書名句，則Eve只需要找到該名書。如果該段并不著名，也可以根據(jù)文字推斷書名及書目類別，并到書店尋找該書。也可以根據(jù)文字的特征，由上下文含義來推測后續(xù)密鑰。比如(k0,k1,…,kl-1)=informationsecurit，則kl=y

；(k0,k1,…,kl-1)=計算機病，則kl=毒；等等。2023/2/251三、古典密碼另一種辦法是：取(k0,k1,…,kd-1)為某個周期序列的一個周期，周期d極大，而用一個長度大約為ln(d)的“密鑰種子”，采用公開算法來遞歸生成這個周期序列。此時通信伙伴只需要相互告知“密鑰種子”的值。這是現(xiàn)代流密碼的一般構造，存在著大量有待解決的工程實踐問題、學術理論問題。2023/2/252三、古典密碼2.多字母代換密碼多字母代換密碼是字母L維向量空間到自身的一個可逆映射f：ZqLZqL；即f(m0m1...mL-1)=c0c1...cL-1。令明文m=m0m1...，則相應密文為c=c0c1...=f(m0m1...mL-1)f(mLmL+1...m2L-1)...

2023/2/253三、古典密碼對多字母代換密碼的討論我們知道，字母L維向量空間ZqL一共有qL個向量。換句話說，多字母代換密碼f實際上是一個單表代換密碼，只不過“字母表”是ZqL，有qL個“字母”。這里的一個“字母”就是ZqL中的一個L維向量。如果f設計得好，則需要qL個“密文字母”和其對應的“明文字母”才能確定f。（取q=2，L=128，則qL=2128是一個極龐大的數(shù)字。）2023/2/254三、古典密碼因此，設計得好的多字母代換密碼f能夠極大地擴大已知明文攻擊所需要的明文/密文的長度。但問題是，多字母代換密碼f怎樣做到設計得好并且簡單快速？（達到設計要求的密碼是一種現(xiàn)代密碼，稱之為分組密碼。）