1.2 密碼學和現代密碼學

密碼學（Cryptography，源于希臘語kryptós“隱藏的”和gráphein“書寫”）是研究如何隱密地傳遞信息的學科。在現代特別指對信息及其傳輸的數學性研究，常被認為是數學和計算機科學的分支，它與信息論也密切相關。著名的密碼學者Ron Rivest解釋道：“密碼學是如何在敵人存在的環境中通信”，這是從工程學的角度來看的，在此也可以看出密碼學與純數學的異同。在密碼學中，研究密碼變化的客觀規律，應用于編制密碼以保守通信秘密的，稱為編碼學；應用于破譯密碼以獲取通信情報的，稱為破譯學。密碼學是信息安全等相關領域（如認證、訪問控制）的核心，在這些領域中密碼學的首要目的是隱藏信息的含義，而不是隱藏信息的存在。因此也可以說密碼學是研究編制密碼和破譯密碼的技術。

1.2.1 傳統密碼體制

傳統密碼體制主要通過字符間的簡單置換和代換來實現對信息的加/解密。現在來看，傳統密碼體制的技術、思想以及破譯方法相對簡單，但它們反映了密碼設計和破譯的基本思想，可以作為學習現代密碼學的入門資料，對于理解、設計和分析現代密碼學具有很好的借鑒價值。下面介紹兩種主要的傳統密碼體制：置換密碼和代換密碼。

1.置換密碼（Permutation Cipher）

置換密碼又稱換位密碼，是指根據一定的規則重新排列明文，以便打破明文的結構特征。置換密碼的特點是保持明文的所有字符不變，只是利用置換打亂明文的位置和次序。最常見的置換密碼有兩種：一種是列置換密碼，另一種是周期置換密碼。

定義1.1 有限集X上運算σ：X→X被稱為一個置換，則σ 是一雙射函數，即σ 既是單射又是滿射，并且σ 的定義域和值域相同。也就是說，任意x∈X，存在唯一的x′∈X使得σ (x) x′。同理可以定義置換σ 的逆置換σ-1：X→X，這是因為σ-1也是雙射函數，并且σ-1的定義域和值域相同。也就是說，任意x′∈X，存在唯一的x∈X使得σ-1(x′)=x。

定義1.2 設n為一固定整數，P、C和K分別為明文空間、密文空間和密鑰空間。明/密文是長度為n的字符序列，分別記為X=（x1,x2,…,xn）∈P和Y=（y1,y2,…,yn）∈C，K是定義在{1,2,…,n}的所有置換組合集合。對于任何一個密鑰σ∈K（即一個置換），定義置換密碼如下：

eσ(x1,x2,…,xn)=(xσ(1),xσ(2)),…,xσ(n))

上式中，σ-1是σ 的逆置換，密鑰空間K的大小為n!。

（1）列置換密碼

列置換密碼是一種常見的置換密碼方式，列置換密碼的加密方法如下：

① 把明文字符以固定的寬度m（分組長度）水平地（按行）寫出，即每行有m個字符；若明文長度不是m的整數倍，不足的地方用雙方約定的方式填充。

② 按1,2，…，m的某一置換σ 交換列的位置次序得到字符矩陣。

③ 把矩陣按1,2，…，m列的順序讀出得密文序列c。

相應的解密過程就是上述加密過程的逆過程，故密文c的解密過程如下：

① 將密文c以分組寬度n按列寫出得到字符矩陣。

② 按加密過程用的置換σ 的逆置換σ -1交換列的位置次序得到字符矩陣。

③ 把矩陣按1,2，…，m列的順序讀出得明文序列p。

（2）周期置換密碼

周期性置換密碼是將明文p串按固定長度m分組，然后對每組中的子串按1,2，…，m的某個置換重新排列位置從而得到密文，其中密鑰包含分組長度信息。解密時同樣對密文c按長度m分組，并按σ 的逆置換σ -1把每組子串重新排列位置得到明文p。

2.代換密碼（Substitution Cipher）

代換密碼是將明文中的字符替換為其他字符的密碼體制?；痉椒ㄊ牵航⒁粋€代換表，加密時將待加密的明文字符通過查表代換為相應的密文字符，這個代換就是密鑰。代換是傳統密碼體制中最基本的技巧，它在現代密碼學中也有廣泛的應用。按照一個明文是否總是被一個固定的字母代替進行劃分，代換密碼主要分為單表代換密碼和多表代換密碼。

1）單表代換密碼

單表代換密碼是指明文消息中相同的字母，在加密時都是用同一固定的字母來代換。單表代換密碼又分為移位密碼、基于密鑰的單表代換密碼和仿射密碼3類，由于移位密碼可以看成仿射密碼特例，下面只介紹基于密鑰的單表代換密碼和仿射密碼。

（1）基于密鑰的單表代換密碼

基于密鑰的單表代換密碼很多，其基本思想是類似的。首先選取一個英文單詞或字母串作為密鑰，去掉其中重復的字母得到一個無重復字母的字母序列，然后將字母表中的其他字母順序依次寫在此字母序列后面，如果密鑰中的字母序列有重復則后出現的字母不再出現，從而使所有的字母建立一一對應關系，也就是字母代換表。這種單表代換密碼的破譯難度稍高，而且密鑰更改便捷，增加了單表代換密碼體制的靈活性。

（2）仿射密碼

仿射密碼的加密算法就是一個線性變換，即對任意的明文字符 x，對應的密文字符為y=e(x)=ax+b(mod 26)，其中a,b∈字母表，并且要求gcd(a,26)=1，函數e(x)稱為仿射加密函數。仿射加密函數要求gcd(a,26)=1，即要求a和26互為素數，否則e(x)=ax+b(mod 26)就不是一個單射函數。當gcd(a,26)=1時，仿射加密函數的解必然唯一。

2）多表代換密碼

多表代換密碼是以一系列代換表對明文消息的字母序列進行代換的加密方法，即明文消息中出現的同一個字母，在加密時不是完全被同一個固定的字母代換，而是根據其出現的位置次序用不同的字母代換。如果代換表序列是非周期的無限序列，則相應的密碼稱為非周期多表代換密碼，它是理論上不可破譯的密碼體制。但實際應用中經常采用的是周期多表代換密碼，它通常使用有限個代換表，代換表被重復使用以完成消息的加密，它是一種比單表密碼體制更為安全的密碼體制。

多表代換密碼利用從明文字符到密文字符的多個映射隱藏單字母出現的統計特性（頻率特性）。它將明文字符劃分為長度相同的明文組，然后在對明文組進行替換。這樣統一字母在明文序列中的位置不同就有不同的密文，能更好抵抗統計密碼分析。多表代換密碼體制有很多，比較典型的有Playfair密碼和Vigenere密碼。

（1）Playfair密碼

Playfair密碼（Playfair Cipher）是1854年由Charles Wheatstone提出的，此后由他的朋友Lyon Playfair將該密碼公布，所以稱為Playfair密碼。

Playfair密碼將明文字母按兩個字母一組分成若干個單元，然后將這些單元替換為密文字母組合，替換時基于一個5×5字母矩陣，該矩陣使用一個選定的關鍵詞來構造，其構造方法如下。第一步是編制密碼表。在這個5×5的密碼表中，共有5行5列字母。第一列（或第一行）是密鑰，其余按照字母順序。密鑰是一個單詞或詞組，若有重復字母，可將后面重復的字母去掉。當然也要把使用頻率最少的字母去掉，假如密鑰是“live and learn”，去掉后則為“liveandr”。如果密鑰過長可以占用第二列或行。第二步是整理明文。將明文每兩個字母組成一對，如果成對后有兩個相同字母緊挨或最后一個字母是單個的，就插入一個字母X。最后編寫密文。對明文加密規則如下：

若p1p2在同一行，對應密文c1c2分別是緊靠p1p2右端的字母。其中第一列被看做是最后一列的右方。

若p1p2在同一列，對應密文c1c2分別是緊靠p1p2下方的字母。其中第一行被看做是最后一行的下方。

若p1p2不在同一行，不在同一列，則c1c2是由p1p2確定的矩形的其他兩角的字母（至于橫向替換還是縱向替換要事先約好，或自行嘗試）。

Playfair解密算法首先將密鑰填寫在一個5×5的矩陣中（去除重復字母），矩陣中其他未用到的字母按順序填在矩陣剩余位置中，根據替換矩陣由密文得到明文。

對密文解密規則如下：

若c1c2在同一行，對應明文p1p2分別是緊靠c1c2左端的字母。其中最后一列被看做是第一列的左方。

若c1c2在同一列，對應明文p1p2分別是緊靠c1c2上方的字母。其中最后一行被看做是第一行的上方。

若c1c2不在同一行，不在同一列，則p1p2是由c1c2確定的矩形的其他兩角的字母。

（2）Vigenere密碼

Vigenere密碼是由法國密碼學家Blaise de Vigenere于1858年提出的一種密碼代換，它是多表代換密碼的典型代表。

定義1.3 設m為某一固定的正整數，P，C和K分別為明文空間、密文空間和密鑰空間，并且 P=K=C=（Z26）m，對于一個密鑰 k=（k1,k2,…,km），定義Vigenere密碼的加密函數為：ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)，與之對應的解密函數為：dk(y1,y2,…,ym)=(y1-k1,y2-k2,…, ym-km)。

其中k=(k1,k2,…,km)是一個長為m的密鑰字，密鑰空間大小為26 m，所以對于一個相對小的m，窮舉密鑰也需要很長的時間。當明文長度超過m時，可將明文串按長度m分組，然后對每一組使用密鑰k加密。

1.2.2 現代密碼學

隨著科學的發展，密碼學占據的位置越來越重要，基于數學模式下的密碼學與越來越多的學科聯系也更加緊密，密碼學的應用越來越廣泛，其主要研究內容如圖1.1所示。

1.現代密碼學理論

在密碼學理論中，關鍵內容是從安全的需要出發，合理定義一些具備一定性質要求的對象，這些對象稱為密碼原語（Cryptographic Primitive），進而探討使用密碼原語解決安全問題的方式，這些解決安全問題的方式稱為范式（Paradigm）。通常基于已證明存在或合理假設存在的原語，證明通過范式構造的解決方案（包括通用構造方法，以及基于某些具體困難問題或者數學結構構造的實際方案）滿足預先定義的安全需求。常用范式總結如下。

① OAEP變換，通過將明文填充，將明文轉化為格式化的明文，原始明文擴散到這種格式化的明文中，并引入隨機性，產生了概率加密和明文敏感性的效果，使得基于單射的單向陷門置換構造的公鑰加密方案為IND—CCA2安全的方案。這種填充方法使用了偽隨機發生器和Hash函數。

② 安全公鑰加密的典型范式如混合加密（Hybrid Encryption），即用非對稱密鑰算法加密臨時的隨機密鑰，然后利用臨時的隨機密鑰使用對稱密鑰算法加密消息。使用非對稱加密作為原語。

③ IND—CCA2安全的公鑰加密的通用轉化方法。包括：Fujisaki-Okamoto轉化方法（FO Conversion）、Pointcheval轉化方法和Okamoto-Pointcheval轉化方法。

④ 安全數字簽名的一個典型范式是Hash-and-Sign范式。所謂Hash-and-Sign范式就是先將消息用Hash函數求值，然后再對散列值進行簽名。也有文獻將這種范式稱為Hash-and-Decrypt范式，它使用Hash函數作為原語。

⑤ 零知識證明中將交互零知識轉變成非交互零知識的Fiat-Shamir啟發式（Hurisitics），也稱Fiat-Shamir范式。該變換是知識簽名的基礎，也是將基于身份的識別協議轉化為簽名方案的一般方法。

⑥ PSS構造方法是使用Hash-and-Sign范式前的填充方法，該填充方法和OAEP填充方法具有某些相似性。

⑦ 基于隨機預言模型，可以將原始明文隨機化，從而得到更安全的公鑰加密和簽名。因為如果一個明文消息是隨機化的，則從密文找到明文的任何信息（如一個比特）和求單向函數的逆一樣困難。

⑧ 特定應用背景下的范式，如E1Gamal一般簽名形式，Schnorr縮短素數域元素的表示，但又不降低DLP的困難程度。

2.密碼系統的安全性測度

一個密碼系統最起碼的安全性要求是：破譯者從截獲的密文中，無法用窮舉所有可能的密鑰來破譯該系統。如果破譯者沒有足夠的時間來試每個密鑰，或即使窮舉了所有密鑰，還是不能破譯該系統，則稱它是窮舉破譯安全的。對于密碼分析，通常有如下三種攻擊類型。

① 僅知密文攻擊：密碼分析者除了擁有所截獲的密文外，沒有其他可利用的信息。

② 已知明文攻擊：密碼分析者僅知道當前密鑰下的一明密對。

③ 選擇明文攻擊：密碼分析者能獲得當前密鑰下的一些特定的明文所對應的密文。

密碼的安全性表現在以下兩個方面。

（1）完全保密性

設明文M出現的概率為p(M)，密文C出現的概率為P(C)，在收到密文C的條件下發送的明文為M的條件概率為P(M/C)。如果對所有的M和C有p(M/C)-p(M)，則稱該密碼是完全保密的。這就是說，如果不論截獲多少密文，關于原明文仍一無所知，即密文與明文是統計獨立的。一個密碼系統是完全保密的充分必要條件是：對每個密文C都有P(C/M)=p(C)，就是說，在給定發送明文M下（在某個密鑰下加密）收到一個特定密文C的概率，和在發送其他消息M下（在另一個密鑰下加密）收到C的概率相同。在一個完全保密的密碼系統中，密鑰數至少應等于明文數。否則，對于給定的密文C，將會有一些明文M找不到密鑰K將C解密為M，這意味著 p(M/C)=0，于是，密碼分析者可能從考慮的范圍中除去某些可能的明文消息，這將導致破譯該密碼的機會增大。一次一密鑰密碼系統是完全保密的密碼系統的一個例子。但是，由于一次一密鑰密碼系統所需要的密鑰量至少應等于明文的數量，這就使得密鑰的分配和管理極為困難。一旦密鑰得不到安全的分配和管理，系統也就沒有安全性可言，因而一次一密鑰密碼系統并不實用。在密碼學中，絕大多數密碼系統是不完全保密的。

（2）計算安全性

實際上，密碼分析者不會擁有無限的計算能力，因此，一個實用的密碼系統的安全性不依賴于破譯該密碼理論上的不可能性，而是極大地依賴于攻擊的實際困難程度。如果一個針對該密碼最佳攻擊方法的困難程度超過了密碼分析者的計算能力則稱該密碼系統是計算安全的，或實際安全的。Shannon用密碼的工作特性W(n)就僅知密文攻擊刻畫了這樣一種困難性。一個密碼的工作特性W(n)定義為當n個密文已知時確定所使用的密鑰所需要的工作量，人們也可以針對其他攻擊探討密碼的工作特性。說一個密碼系統是計算安全的意義是指對該密碼最佳攻擊的復雜度（一般理解為實施該攻擊所使用運行的平均次數）超過了密碼分析者的計算能力。要證明一個密碼是計算上安全的將意味著尋找一個關于解某個計算問題的復雜度下界。目前對實際中所有的計算問題，這都是難以做到的。因此，一個密碼安全性的評估實際上依賴于目前已知道的關于該密碼的最佳攻擊的復雜度。