密碼學基礎
博主一個23考研黨，寒假自己復習密碼學，一些筆記希望能給大家一些幫助
基礎術語
明文（M） ：加密前你所要發送的資訊，
密文（C）：加密明文得到的結果，
加密密鑰（K）：加密明文時的一個引數，
解密密鑰（K）：解密密文時的一個引數，
加密演算法和解密演算法（E和D）：加解密時所用的演算法，
以上的字母都表示一個集合，例如M表示所有可能的明文組成的有限集，
密碼體制分類
對稱密碼體制：簡單來說就是發送方使用的加密密鑰和接收方使用的解密密鑰相同，此類體制的安全性主要取決于密鑰保密性而非演算法保密性，
非對稱密碼體制：發送方使用的加密密鑰和接收方使用的解密密鑰不相同，
密碼攻擊概述
密碼分析是基于Kerckhoffs原則：攻擊者知道加密演算法內部機理但不知道加密密鑰，
（1）唯密文攻擊：攻擊者有一些訊息密文，這些密文都由相同加密演算法加密的到，攻擊者要恢復盡可能多的明文，或者能推算出加密密鑰，以便采取相同的密鑰解密更多密文，
（2）已知明文攻擊：攻擊者不僅得到一部分密文，并且知道了密文對應的明文，攻擊者要用已知資訊推算出加密密鑰或者匯出加密演算法，此演算法可以對同一密鑰加密的任何資訊加密，
（3）選擇明文攻擊：攻擊者可以選擇明文知道對應的密文，比已知明文更加有效，因為可以選擇特定的明文訊息進行加密，得到密鑰的更多資訊，攻擊者要用已知資訊推算出加密密鑰或者匯出加密演算法，此演算法可以對同一密鑰加密的任何資訊加密，
（4）選擇密文攻擊：可選擇對應密文的明文，以此推匯出加密密鑰，
還有兩個概念值得注意，第一, 一個加密演算法是無條件安全的,如果演算法產生的密文
不能給出惟一決定相應明文的足夠資訊，此時無論敵手截獲多少密文、花費多少時間,都
不能解密密文，第二, Shannon 指出, 僅當密鑰至少和明文一樣長時, 才能達到無條件安
全，也就是說除了一次一密方案外, 再無其他加密方案是無條件安全的，因此,加密演算法
只要滿足以下兩條準則之一就行:
① 破譯密文的代價超過被加密資訊的價值，
② 破譯密文所花的時間超過資訊的有用期，
滿足以上兩個準則的加密演算法稱為計算上安全的，
古典密碼
古典密碼是指從密碼產生到近代密碼之間這段時期，古典密碼中很多經典的密碼如凱撒密碼，維吉尼亞密碼等，
凱撒密碼:其實就是移位密碼，通過對明文里每一個訊息向前移動固定個key個單位來實作加密，
先在英文字母和0~25之間形成一一對應的關系，
| A | 0 |
|---|---|
| B | 1 |
| C | 2 |
| … | … |
| Z | 25 |
然后e（x）= （x+key）mod 26 得出加密后的序列，再根據上表得到密文，
解密程序和上述流程相同，僅需要改變演算法d（y）= （y-key）mod 26
仿射密碼：仿射密碼是移位密碼的一種推廣，也是需要建立對應關系，
仿射密碼體制：e（x）= （k1 * x+ k2）mod 26 , gcd(k1 , 26) = 1,k1與26互素，
解密：d（y）= k1^(-1) *（y-k2）mod 26 這里就牽扯到一部分數論的知識，求逆元，常用的方法是擴展歐幾里得演算法，
要說擴展歐幾里得演算法，則要先知道歐幾里得演算法，在這里，我們不多做證明，只用結論，比如求156和27的最大公因數
156 = 27 * 5 + 21
27 = 21 * 1 +6
21 = 6 * 3 +3
6 = 32 + 0
故156和27最大公因數為3，而擴展歐幾里得演算法則是逆用，可以得出s a + t* b=gcd(a,b),中的解s,t.具體方法是將gcd(a,b)帶入上式倒數第二步，然后逆運算，若a與b互素則可以得出s=a^(-1) mod b稱作s為a在模b下的逆元，
例：已知一仿射密碼加密密鑰k1,k2分別為7，3求解密演算法
這道題目其實就是求7^(-1) mod 26,首先寫出求26和7的歐幾里得演算法步驟
26 = 7 * 3 + 5
7 = 5 * 1 + 2
5 = 2 * 2 + 1 ok,我們寫到余數為一就足夠了
此時，1 = 5 - 2* 2 mod26
1 = 5 - （7-5* 1）* 2 mod26
1 = 5 - （7-（26-7*3）*1）*2 mod26
然后我們在化簡時要注意，7前的系數就是它的逆元 1 = 5 - 7 * 8 mod 26 而 5mod26 = -21 所以
1 = -11 * 7mod26,所以7的逆元為-11 也可以15，因為-11mod26 = 15
所以解密演算法：d（y）= 15 *（y-3）mod 26
我們在計算逆元時簡化后一定要形成 1 = s * a mod n的形式
維吉尼亞密碼：上述的兩種加密方式都是基于單表代換，也就是說字母表中的每一個字母會被加密成唯一密文，考慮到頻率分析法具有很強的破解單表代換的能力，人們開始考慮使用多表代換，
頻率分析法：對大量密文進行分析，通過明密文高低頻率字母的對應關系來破解密鑰，此種方法密文越多越容易破解，
密碼體制定義：設有整數m，對任意密鑰key = (k1,k2…km)
e(x1,x2…xm) = (x1+k1,x2+k2…)mod26
d(y1,y2…ym) = (y1-k1, y2-k2…)mod26這體現了分組密碼的思想
一定程度上具有抵抗頻率分析法的攻擊，
例：m=8,密鑰字為computer，明文為abcdefghig,密文是什么
首先由密鑰字得k = (02,14,12,15,20,19,04,17)
密文序列是 02,15,14,18,24,24,10,24,10,23密文為cposyykykx
Hill密碼：Hill密碼是置換密碼中非常典型的例子，置換密碼不像上面幾種是將英文字母寫成另一個形式加密，而是通過重新排列位置來進行加密其中體現著分組——置換的思想，其中非常典型的Hill密碼的加密體制為：設m為一大于等于2的整數，k為m* m的矩陣的集合，且A屬于k
e（x）= A* xmod26
d（y）= A^(-1)*ymod26
x和y為一長度為m的列向量，A^(-1）為A的逆矩陣，
對稱密碼體制：還在更新中…
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394155.html
標籤：其他
上一篇：Pocsuite安裝和簡單使用（以vulfocus靶場測驗）
下一篇：硬體安全之ARM體系架構的演進