密碼學的底層原理

一、密碼學的定義

在20世紀晚期之前，密碼學更多的是一門藝術，它主要是用于秘密通信。在那個時候沒有什么理論可以依賴，也沒有什么有效的定義可以構建一個好的密碼。直到上個世紀80年代開始，現代密碼學的出現使得對密碼學的研究成為了一門科學和數學學科。

適用對象：

經典密碼學：軍事組織和政府。

現代密碼學：everywhere。

對密碼學的定義：

《簡明牛津英語詞典》：編碼或破譯密碼的藝術。（不夠完善準確）

現在密碼學：對保護數字信息、系統和分布式計算免受敵方攻擊的數學技術的研究。

其演變過程可表示如下：

二、對稱加密簡述

經典密碼學關注的是對密碼的設計和使用，使得在有第三方竊聽者監聽消息的情況下，雙方能夠發送消息而不被監聽者看到。監聽者可以監視他們之間的所有消息。上面所說的“密碼”就是后面我們要說的“加密方案”。所有經典密碼學的安全性都依賴于一個秘密——密鑰 (key)——由通信雙方提前生成并交換而竊聽者無法獲取。這種方式就是private-key encryption。

在密碼學中，我們將加密方案分為private-key (symmetric) encryption和public-key (asymmetric) encryption。

在private-key encryption中，當通信雙方想要秘密通信的時候，提前交換一個key。其中一方可以使用這個key來加密一條消息，或者叫明文 (plaintext)，然后發送給另一方。因此可以說，其中一方將一個密文ciphertext發送給了另一方。接收者使用key解密這個密文，得到了原始消息。這里的key都是相同的，并且用于明文和密文之間的轉換。這也是為什么人們將之稱為symmetric encryption。然而asymmetric encryption與之相反，其加密和解密使用的是不同的key。

三、加密語法

正式地，一個private-key encryption方案由一個消息空間M和三個算法 (Gen 、Enc和Dec) 組成。

Gen：密鑰生成算法

Enc：加密算法

Dec：解密算法

這三個算法的功能描述如下：

1. Gen是一個概率算法，根據某種分布，輸出一個密鑰k。

2. Enc將一個密鑰k和一個明文消息m作為輸入，輸出一個密文c，即Enc_k(m)表示用密鑰k對明文消息m進行加密。

3. Dec將一個密鑰k和一個密文c作為輸入，輸出一個明文消息m。即Dec_k(c)表示用密鑰k對密文消息c進行解密。

所有由Gen生成的密鑰k組成了一個密鑰空間，記為K。由Dec生成的密文c 組成了一個明文空間，記為C。

一個加密方案必須滿足如下確定性要求：對于每一個由Gen輸出的密鑰k和每一個明文消息m∈M，Dec_k (Enc_k(m) = m

對稱加密流程：運行Gen來生成密鑰k，當一方想要發送明文消息m給另一方時，

他計算c : = Enc_k(m)，

然后在公開信道中將密文c發送給對方。

接收者收到密文c后，

計算m : = Dec_k(c)來得到原始消息。

“ := ”表示確定性等式，假設此處的Enc是確定性的，Enc是概率性的算法

四、Kerckhoffs原則

“加密方案沒有必要保密，它可以被敵人輕易獲得。”

也就是說，即使竊聽者知道加密方案的所有細節，只要攻擊者不知道正在使用的密鑰k，這個加密方案應該是安全的。故，Kerckhoffs的原則要求安全性僅僅依賴于密鑰k的保密。

理由：

1. 保密一個密鑰k比保密一個相對復雜的加密方案更加容易，尤其是在加密方案被廣泛使用的情況下。

2. 如果誠實方共享的秘密信息被泄漏，更換密鑰比更換加密方案容易得多。此外，生成一個新的隨機密鑰是相對簡單的，而設計一個新的加密方案則是一個巨大的工程。

3. 在廣泛部署加密方案之前，鼓勵公眾對該方案進行審查以檢查可能存在的弱點，這是一個顯著的好處。進一步地，標準化加密方案可以確保不同用戶之間的兼容性，公眾將使用經過公開審查的強大的加密方案。這更加令人信服。

故，廣泛、公開地傳播加密方案的全部細節是有利的。

五、經典加密方案

以下介紹的加密方案均已被破解，是不安全的，但是其思想值得學習。

1. 凱撒加密（Caesar’s cipher）

凱撒加密是最古老的加密方案之一，它將字母表中的字母向右移動3個位置進行加密。即，a加密為D，b加密為E，以此類推。當移動到字母表的末尾時，回到字母表的開頭，循環移位。該方案沒有密鑰，且加密方法是固定的。因此任何人可以通過學習凱撒加密的加密方法來輕易的破解密文。其變體ROT-13依然被各種在線論壇使用。我們可以從中發現，它們均沒有提供任何的密碼學安全性，它們僅僅是使得消息是令人難以理解的，除非消息的讀者有意識地決定解密它。

2. 移位加密

移位加密可以視為凱撒加密的一種密鑰變體。在移位加密中，密鑰k是一個介于0到25之間的數字，在凱撒加密中，字母移動3個位置，而在移位加密中，字母移動k個位置。其算法可概括如下：明文空間M由任意長度的英文字母字符串組成，其中去掉了標點、空格和數字，并且大小寫沒有區別。Gen輸出一個均勻一致的密鑰k ∈ { 0 , . . . , 25 } ，算法Enc將一個密鑰k和一個明文作為輸入，然后將明文的每個字母向前移動k個位置，算法Dec將一個密鑰k和一個密文作為輸入，然后將將密文中的每個字母向后移k個位置。

在不知道密鑰k的情況下，破解密文也是相當容易的。因為它只有26個可能的密鑰，攻擊者只需要用這些可能的密鑰去解密密文即可，故可得到26種可能的候選明文，正確的明文就在這26種之中。此外，如果密文“足夠長”，那么正確的明文很可能是列表中唯一“有意義”的候選明文。（這在大多數時候是正確的）

這種嘗試每一個可能的密鑰的攻擊被稱為蠻力 (brute-force) 或窮舉 (exhausient-search) 攻擊。故如果加密方案要保證安全，就不能輕易受到這種攻擊，這個觀察被稱為充分密鑰空間原理：任何安全的加密方案必須要有足夠大的密鑰空間來抵抗窮舉搜索攻擊。為了防止這種攻擊，密鑰空間必須非常大，例如，至少2⁸⁰ ，在很多情況下甚至更大。

充分密鑰空間原理給加密方案的安全性提供了必要條件，但不是充分條件。

3. 單字母替換加密

在“移位加密”中，明文到密文的映射是一個由密鑰決定的固定的移位，而在單字母替換加密中，允許映射是任意的，只受一對一的約束。密鑰空間包含字母表的所有雙射或置換。如下圖：

圖中的a映射到X，等等。

從該加密方案的名稱上能夠了解到這樣一個事實：密鑰定義了明文中單個字符的(固定)替換。假設使用的是26英文字母表，那么，密鑰空間的大小可計算為：26! = 26·25·24···2·1，大約為2⁸⁸  ，蠻力攻擊是不可行的。

單字母替代加密可以利用英語語言的統計特性進行攻擊。由于每一個字母的映射都是固定的，所以，如果得知e映射為D，那么，其余的e都映射為D。英文字母的概率分布如下圖所示：

4. 維吉尼亞加密

可以使用統計攻擊來破解“單字母替代加密”，因為它的密鑰定義了一個固定的映射，該映射逐字應用于明文。在“多字母替代加密”中，該攻擊無效，它的密鑰定義了應用于明文字符塊的映射。多字母替代加密“平滑”了密文中字符的頻率分布，使其更難進行統計分析。維吉尼亞加密就是多字母替代加密的一種，可以看作是將移位密碼的不同實例應用于明文的不同部分。如下圖所示，它的密鑰是一個字符串。加密是通過按密鑰的下一個字符表示的數量移動每個明文字符來完成的，必要時在密鑰中環繞。

六、現代密碼學的原則

 · 原則一：形式化定義：明確“安全”到底是什么意思

 · 原則二：精確的假設：事實證明，大多數密碼證明依賴于關于某些數學問題的算法難度的目前未被證明的假設

 · 原則三：安全性證明：任何這樣的假設都必須明確并精確地陳述。

安全的加密方案應該保證：不管攻擊者已經擁有什么信息，密文都不應該泄露關于底層明文的額外信息。

威脅模型（按強度增加的順序）：

1. 唯密文攻擊（Ciphertext-only attack）：敵手只觀察一個密文(或多個密文)，并試圖確定關于底層明文(或多個明文)的信息。

2. 已知明文攻擊（Known-plaintext attack）：在這里，對手能夠學習使用某個密鑰生成的一個或多個明文/密文對。然后，對手的目標是推斷使用相同密鑰產生的其他密文的基礎明文的信息。

3. 選擇明文攻擊（Chosen-plaintext attack）：在這種攻擊中，對手可以獲得如上所述的明文/密文對，用于其選擇的明文。

4. 選擇密文攻擊（Chosen-ciphertext attack）：攻擊者能夠額外獲得其選擇的密文的解密(一些信息)，例如，解密攻擊者選擇的一些密文是否會產生有效的消息。同樣，對手的目標是了解使用相同密鑰生成的其他密文(對手無法直接獲得其解密)的底層明文信息。