密碼學基礎--AES和DES

密碼學的基本概念：
保密性：資訊僅被合法使用者存取（瀏覽、閱讀、列印等），不被泄露給非授權的使用者、實體或過程。
完整性：資源只有授權方或已授權的方式進行修改，所有資源沒有授權則不能修改。保證數據完整性，就是保證數據不能被偶然或者蓄意的編輯。
可用性：資源只有在適當的時候被授權方存取，並按需求使用。

古典密碼以及破譯方法：
如果密碼分析者可以僅由密文推出明文或金鑰，或者可以由明文和密文推出金鑰，那麼就稱該密碼系統是可破譯的。

攻擊方法	說明
窮舉攻擊	對截獲到的密文嘗試 遍歷所有可能的金鑰，直到獲得正確的明文；或使用固定的金鑰對所有可能的明文加密一直到得到與截獲到的密文一致爲止
統計分析攻擊	利用已經獲取的明文和密文已知統計規律進行破譯的方法
數學分析攻擊	密碼分析者針對加解密演算法的數學基礎和密碼學特性，通過數學求解的方法來破譯密碼。

密碼分析者的攻擊密碼型別

攻擊密碼的型別	攻擊者擁有的資源說明
僅知密文攻擊	密碼分析者僅能通過截獲的密文破解密碼 。
已知明文攻擊	密碼分析者已知明文-密文對，來破解密碼。
選擇明文攻擊	密碼分析者不僅可得到一些「明文-密文對」，還可以選擇被加密的明文，並獲得相應的密文。
選擇密文攻擊	密碼分析者可以選擇一些密文，並得到相應的明文。

**古典密碼–置換密碼：**明文的字母不變，但位置被打亂了。
如：把明文按行寫入，最後按列讀出密文，結果如下：
|

金鑰	1	2	3	4	5	6
明文	b	a	n	a	n	a
	o	r	a	n	g	e

此時，經過密碼置換加密後，密文爲boarnaanngae

在實際場景中，通常會遇到：
給定明文爲：
tba simpodst yossibje trqnspbsition cipderk,
置換矩陣爲：

Ek = 0 1 2 3 4
     1 4 3 0 2

這個置換矩陣說明了，將明文分成長爲L=5的段，m1=tbasi, m2=mpods, m3=tyoss,m4=ibjet,m5=rqnsp,m6=bsiti,m7=oncip,m8=derkz。
最後一段長不足5，加添一個字母z或者其他特殊符號，再將隔斷的字母序號按Ek置換矩陣進行換位得到:
bista psdmo yssto bteij qpsrn sitbi npioc ezkdr

代替密碼
代替密碼是指先建立一個替換表（代替密碼的金鑰），加密時通過查表，將明文的每個字母依次替換爲對應的字元，生成密文。
代替密碼使用替換表的個數可以將代替密碼分爲：

1. 單表代替密碼：又稱爲簡單替代密碼，即一個明文字元對應一個密文字元。

假設明文字母表A={a0、a1、...、an-1}和密文字母表B={b0、b1、...、bn-1}，
A到B的一一對映f：A->B， f（ai）=bi。
明文M = （m0、m1、...、mn-1）,則密文C=（f（m0）、f（m1）、...、f
(mn-1)）.f函數或者密文字母表B稱爲金鑰

常見的單表代替密碼如下：
**加法密碼：**常見的加法密碼是Caesar（凱撒）密碼，就是把明文字母表回圈右移3位後得到的字母表。
**乘法密碼：**需要預先知道訊息元素的個數，加密的過程其實是相當於對明文訊息所組成的陣列下標進行加密，然後用明文訊息中加密後位置所對應的明文字元代替。
乘法密碼的對映函數爲：f(ai) = bi = aj, j=ik mod n,其中k和n是互素的。
**仿射密碼：**加法密碼和乘法密碼的結合。放射密碼的對映函數爲：f（ai）=bi=aj， j=（ak1+k0）mod n，其中k1和n是互素的。
2. 多名碼代替密碼：單個字元明文可以對映成密文的多個字元之一。例如X可對應1、15或16，Y可對應9、51或82等。
3. 多字母代替密碼： 字元塊被成組加密。例如，XYX對應ARP，CDD對應GOI等。
4. 多表代替密碼：使用從明文字母到密文字母的多個對映，每個對映是像簡單代替密碼中的一對一對映。由於多表代替密碼採用了多個密文字母表，就比單表代替密碼安全強度要高許多。
Vigenere密碼是法國外交官維吉尼亞設計的，是一種常用的多表代替密碼。
代數密碼利用代數相關理論和方法進行加密。vernam密碼是常見的代數密碼，該方法使用代數運算中的模二運算（互斥或）。
其規則：1⊕0 = 1， 0⊕1=1， 0⊕0 = 0， 1⊕1=0
Vernam密碼的金鑰和明文具有相同的長度，金鑰只能使用一次，因此又叫」一次一密「。加密時，對金鑰和明文進行互斥或操作，得到密文；解密時用同樣的金鑰和密文進行互斥或操作，得到明文。
古典密碼的破解方法
除了之前提到的窮舉分析和統計分析，還有量子演算法。
實用的破譯量子計算的演算法有：Shor演算法和Grover演算法。
兩種演算法均可以對RSA、EIGamal、ECC密碼及DH金鑰協商協定進行有效的攻擊。不過由於量子計算機尚未成熟，因此量子演算法暫時對現有的密碼體系不構成威脅。

分組密碼
分組密碼又稱爲祕金鑰密碼或對稱密碼。使用分組密碼對明文加密時，首先對明文分組，每組長度相同，然後對每組明文分別加密得到等長的密文。再分組密碼中，明文被分割多個塊，加密後的密文也是多個塊。分組密碼大致結構如圖所示：

DES演算法
DES分組長度爲64位元，使用56位元金鑰對64位元的明文串進行16輪加密，得到64bit的密文串。其中，使用金鑰爲64位元，實際使用56 位元，另8位元用作奇偶校驗。DES使用了對合運算，即，加密和解密共用同一演算法，則設計總工作量減半。

初始置換IP與逆初始置換
1. 初始置換IP作用是：將64位元明文打亂重新排列。如，初始置換IP就是將原名來64位元明文數據的第58位元換到第1位，原來的50位換到第2位，…，依次類推。
2.初始置換結果分爲兩組： 左L0（32位元）、右R0（32位元）
逆初始置換
1. 把64位元中間密文打亂重排。初始置換IP與逆初始置換是互逆的。如，在IP中把輸入的第2位置換到第8位元，而在逆初始置換中，把輸入的第8位元置換到第2位。
2. 形成最終的64位元密文。

子金鑰產生
64位元金鑰經過置換選擇1、回圈左移、置換選擇2，產生16個長48位元的子金鑰。子金鑰產生流程如圖：

第一步：置換選擇1
置換選擇1作用有：去掉金鑰中位置位8的整數倍的奇偶校驗位，共8個。例如，種子金鑰 「01000010 01101111 01100010 01000001 01101100 01101001 01100011 01100101」.去掉奇偶校驗位後，成爲「0100001 0110111 0110001 0100000 0110110 0110100 0110001 0110010」。
打亂金鑰重拍，根據下圖置換表，生成左28位元，右28位元。


第二步：回圈左移
回圈移位就是將二進制串首位相連，再進行按位元移動。DES每一輪迭代對應子金鑰回圈左移的位數，如下表所示:

加密函數f
DES演算法中，加密函數f是其核心演算法，該函數由選擇運算E、互斥或運算、代替函陣列S（S盒變換）、置換運算P。

第三步：置換選擇2
置換選擇2是一個壓縮置換，將56位的輸入壓縮爲48位元，作爲第i輪的子金鑰。

 **S盒變換**
 S盒變換是一種壓縮替換，通過S盒將48位元輸入變爲32位元輸出。共有8個S盒子，並行作用。每個S盒有6個輸入，4個輸出，是非線性壓縮變換。

如：當S1盒輸入爲「111000」時，則第1位與第6位組成二進制串「10」（十進制2），中間四位組成二進制「1100」（十進制12），查詢S1盒的2行12列，得到數位3，得到輸出二進制數是0011.這裏特別要注意的是，起始的行號和列號都是從0開始的。

DES安全性
（1）.如果DES金鑰太短經不起窮盡攻擊。(2). DES存在弱金鑰和半弱金鑰。
3DES
3DES有兩種加密方式：
1. 第一、三次加密使用同一種金鑰，這種方式金鑰長度128位元（112位元有效）
2. 三次加密使用不同金鑰，這種方式金鑰長度192位（168位元有效）

AES演算法
AES和DES一樣都是應用了輪的思想，將明文經過多輪迭代處理得到密文。二者不同之處是，AES明文分組長度和金鑰長度可以靈活組合。AES明文分組長度可以是128位元、192位、256位；金鑰長度也可以是128位元、192位、256位。
一. AES數學基礎
有限域：有限域的元素個數必須是一個素數的冪p^n
, n爲正整數。元素個數爲p^n的有限域一般記爲GF(p ^n)

乘法逆元
對於有限域GF(pⁿ)，任意的存在w∈GF(p ⁿ)，w≠0，z∈GF(p ⁿ)，使得w * z ≡1 mod p，則z爲w在該有限域上的乘法逆元。
例如： 67 mod 119的逆元是16.其演算法如下：

AES運算特點
AES中的運算包含面向位元組（8位元）或4位元組的字（雙字，32位元）運算。
面向位元組的運算
一個位元組可看作有限域GF（中的一個元素，對應於一個係數在GF（2）中的次數小於8的多項式。即將位元組b7b6b5b4b3b2b1b0）看成二元域GF（2）上的次數小於8的多項式：

·加法：多項式係數按位元模加
如： 57⊕83 = ？
（x⁶+x⁴+x²+x+1）⊕(x⁷+x+1) = x⁷ +x⁶+x⁴+x²
結果位11010100，即D4
（x⁶+x⁴+x²+x+1）*(x⁷+x+1) mod m(x) =
x¹³+x¹¹+x⁹+x⁸+x⁶+x⁵+x⁴+x³+1 mod (x⁸+x⁴+x³+x+1) = x⁷+x⁶+1

結果位11000001，即C1

AES演算法框架
明文State
可以用二維矩陣表示，該陣列爲4行，Nb 列 ，形爲4Nb。陣列每個元素爲1個位元組，即爲2個十六進制數。
Nb=數據塊長度/32。當數據塊長128時，Nb=4；當數據塊192時，Nb=6；當數據塊256時，Nb=8.
金鑰State
金鑰State也可以用二維矩陣表示，該陣列爲4行，Nk列，形爲4Nk。陣列每個元素爲1個位元組，即爲2個十六進制數。
Nk=數據塊長度/32。當數據塊長128時，Nk=4；當數據塊192時，Nk=6；當數據塊256時，Nk=8。
加密輪數
值取決於明文塊和金鑰塊長度，即和的值。具體對應關係如下圖所示：

AES演算法框架

加密：首先執行"子金鑰加「演算法；然後進行前9輪加密操作，每輪包含」位元組代換「、」行移位「、」列混淆「、」子金鑰加「；第10輪加密操作，少了一步「列混淆」。
解密:執行的是逆過程，演算法不完全一致。

金鑰生成
AES演算法中，首先利用種子金鑰推導出子金鑰，再由子金鑰推導出子金鑰…，最後由子金鑰推導出子金鑰。

AES不是對合運算，即，AES解密演算法與加密演算法不同。AES解密演算法是加密演算法的逆過程，加密和加密演算法原理基本一致。其中不同的是，有幾步是求逆過程。