備注

2021/12/3 星期五
多門考試和課程設計接踵而至，我只能選擇用兩天時間突擊密碼學了，邊學邊記錄一下

一、基本知識

1.術語

• 明文：沒有經過加密，任何人都能看得懂的文字
• 密文：經過加密后的文字
• 密鑰：明文與密文轉換的引數

2.保密原則

是現代密碼學和古典密碼學的重要區別

• 現代密碼原則：密碼系統的安全性不依賴于演算法的保密而依賴于密鑰的安全
• 古典密碼原則：密碼系統的安全性依賴于演算法的保密和密鑰的安全

3.安全性

絕對安全(無條件安全)：
指的是攻擊者在擁有無限的計算資源的條件下也無法被攻破的秘密體制，對于一個加密演算法，如果明文空間的每種概率分布，其中的每個明文和每個密文都滿足，不論特定密文是否出現，特定明文出現概率都相同(即：P(M=m|C=c) = P(M=m))
計算安全：
攻擊在有限計算資源的條件下很難攻破密碼體制，將攻擊者的攻擊視作一個演算法，要求演算法的時間復雜度O(n^c)足夠大，無法遍歷密鑰(n為密鑰的二進制位數，c為常數)

當前默認加密演算法至少需要能夠抵抗選擇明文攻擊

4.安全目標

破壞性從上到下依次降低

• 攻擊者不能獲得密鑰
• 攻擊者不能獲得全部明文
• 攻擊者不能獲得明文的任何部分
• 攻擊者不能獲得明文的任何函式

5.加密原則

• 擴散(diffusion)：明文及密鑰的影響盡可能散布到多密文中(置換)
• 混淆(confusion)：使明文和密文間的統計相關性最小化(代換)

6.數學基礎

包括數論、概率論、近世代數、代數幾何、計算復雜性

7.數學難題

多項式求解、離散對數、大整數分解、背包問題、二次剩余、模n平方根、Diffie-Hellman

二、密碼編碼

1.古典密碼

(1)置換密碼

明文中的字符保持不變，通過改變字符順序進行加密

• 柵欄密碼：
  加密：將明文分成k組，取每組的第i個字符連成密文段i，再將密文段全部相連形成密文
  解密：將密文分成k組，取每組的第i個字符連成明文段i，再將明文段全部相連形成明文
  密鑰：k

(2)代換密碼

明文中的字符順序保持不變，通過將字符替換成其他字符進行加密

單字符代換：

單表代換:

• 加法密碼:
  (也叫移位密碼特例為凱撒密碼)
  加密：E(x)=(x+k)%m
  解密：D(x)=(x-k)%m
  密鑰：k
• 乘法密碼:
  加密：E(x)=(kx)%m
  解密：D(x)=(k^-1x)%m
  密鑰：k
• 仿射密碼:
  加密：E(x)=(a*x+b)%m
  解密：D(x)=(x-b)/a%m
  密鑰：(a，b)
• 棋盤密碼:
  編制密碼表：繪制5*5的方格，將i和j放入同一個格子，給每一個格子一個坐標(x，y)
  加密：將明文依次替換為坐標對
  解密：將密文在密碼表中找到坐標對應的值

多表代換:

• 維吉尼亞密碼:
  加密：E(x)=(x[i]+k[i%n])%m
  解密：D(x)=(x[i]-k[i%n])%m
  密鑰：k[n]

多字符代換

• 普萊費爾密碼:
  編制密碼表：
  1.繪制5*5方格
  2.選取密鑰(任意字符組合)
  3.將密鑰依次填入方格(重復的字符只保留第一次出現的位置，字符I和L視作同一個字符)
  4.其余字符按順序填入方格
  5.整理明文，每兩個字符組成一對，兩相同字符相連時在中間插入X
  加密：
  1.明文對在同一行時，密文為其右側的字符
  2.明文對在同一列時，密文為其下方的字符
  3.明文對在不同行列時，密文為明文對所在正方形的另外兩個角點上的字符
  解密：
  1.密文對在同一行時，明文為其右側的字符
  2.密文對在同一列時，明文為其上方的字符
  3.密文對在不同行列時，明文為密文對所在正方形的另外兩個角點上的字符

一次一密

每次加密都使用全新的密鑰，每個密鑰僅使用一次，是理論上絕對安全的加密方式

• 費納姆密碼:

2.現代密碼

(1)對稱密碼(單鑰密碼)

優點：加密快，密鑰短，歷史悠久
缺點：密鑰管理困難，不能進行身份認證和數字簽名
序列密碼(流密碼)：
給定種子通過演算法生成密鑰流，再將明文位或字符分別與密鑰流進行模加法運算
基礎：有限狀態自動機，二元序列偽隨機，線性反饋移位暫存器，m序列

• A5-1：
  應用：蜂窩電話手機到基站間的通信加密，用戶sim卡中有不發生改變的基本密鑰K1，在產生會話時基站生成64位隨機密鑰k，并使用k1加密，發送給用戶，用戶使用k1解密后得到隨機密鑰k，隨機密鑰僅一次通話內有效，
• RC4：
  演算法：
  1.初始置換
  (1)線性填充256位長的s表s[i]=i
  (2)回圈使用種子填充256位長的k表k[i]=seed[i%n]
  (3)用k表對s表進行初始置換,j=(j+s[i]+k[i])%256(j初始為0)，交換s[i]和s[j]的位置
  2.密鑰流生成
  (1)i，j初始為零
  (2)回圈加密每一位，i=(i+1)%256,j=(j+s[j])%256，交換s[i]和s[j]，t=(s[i]+s[j])%256
  (3)s[t]就是這一位的位密鑰，與該位進行異或得到位密文

(2)分組密碼(塊密碼)

將明文劃分為若干組(一般64位一組)，再將各分組加密
基礎：SP網路，Feistel結構、SPN結構

• DES：
  衍生：3DES
  演算法：
  1.輸入64位的明文資料
  2.初始置換IP
  3.在輪函式F中進行16輪迭代變換
  4.逆置換IP^-1
  5.得到64位密文資料
  輪函式：
  先將64位資料分成左右兩部分(L,R)，每輪計算時，記錄R成為下一輪的L，同時讓R經過擴展表(E盒)、代換表(S盒)、置換表(P盒)的變換再與L進行異或成為下一輪的R
  密鑰生成演算法：
  1.初始置換(PC-1)：根據置換表去除校驗位并對剩余字符進行置換
  2.輪迭代：將初始置換得到的56位字符分左右兩部分(C,D)，C，D分別向左回圈移動移位得到下一輪的(C,D)，并將本輪(C,D)輸入置換表PC-2得到本輪的密鑰K(48位)

• AES：
  衍生：AES-128、AES-192、AES-256
  演算法：
  1.白化(輪密鑰加)
  2.進行輪迭代(128迭代10輪、192迭代12輪、256迭代14輪)[位元組代換、行移位、列混淆、輪密鑰加]
  3.最后一輪迭代[位元組代換、行移位、輪密鑰加]
  設計原理：
  AES將一個位元組視作一個系數為各位的七次多項式，而它可以通過在二元域上模一個不可約的八次多項式m(x)得到，選取m(x)為下x⁸ +x⁴ + x³+x+1并定義加法為兩位元組逐位異或，乘法為多項式在模m(x)下相乘的結果，同理，也可以將一個字視作一個系數為各位的三次多項式，m(x)為x⁴+1，

• SM4：
  國密演算法

(2)非對稱密碼(雙鑰密碼)

優點：密鑰管理簡單，能夠進行身份認證和數字簽名
缺點：運算慢，密鑰長，發展較短

• RSA:
  演算法：
  1.密鑰生成
  取不相等的兩大素數p，q，令N=p*q，N的lambda函式為lcm(p-1，q-1)，在1到lambdaN之間任取一與lambdaN互素的整數e，再求e在模lambda N下的逆元d，(e,N)為公鑰(d,N)為私鑰
  2.加密演算法
  密文c=E(m)=m^e(modN)
  3.解密演算法
  明文m=D?=c^d(modN)
  另：計算a^b(modN)的方法是二元法，先將b寫成二進制形式，然后分離每一位(最高位為1號其他位依次編號)，令c[0]=1，c[i]=c[i-1]^2*m(b[i]-1)
• ElGamal:
  演算法：
  1.密鑰生成
  取一大素數p，求其生成元g，找一亂數做私鑰x，通過g^x%p求公鑰y
  2.加密演算法
  密文有兩部分，先選一個亂數k，求出c1=g^k%p，c2=m*yk%p，密文為(c1，c2)
  3.解密演算法
  直接計算m=c2*(c1^x)^-1即為明文
  另：該演算法是不確定性的，同一個密文使用不同的亂數k加密得到的密文不同(同一個密文最多有p-1個明文)，所以k必須保密且僅使用一次，如果使用相同k被攻擊者得到，則可通過y^k%p得到私鑰
• ECC：
  演算法：

(3)單向函式

也叫散列函式、雜湊函式或哈希函式，將任意長度的資訊映射為較短的、固定長度的值，一般用于訊息摘要

• MD5：
• SHA：
  衍生：SHA-1、SHA-128、SHA-256

三、數字簽名與密鑰管理

1.數字簽名

• RSA：
• 簽名演算法：
  與加密演算法一致，但是使用私鑰進行加密
  驗證演算法：
  與解密演算法一致，但是使用公鑰進行解密
• ElGamal：
  簽名演算法：
  1.任選一個與大素數p的歐拉函式f互素的整數k
  2.計算s1=g^{kmodp，s2=(m-x*s1)*k}-1modf
  3.(s1,s2)為簽名
  驗證演算法：
  簽名真實的等價條件為y^s1*s1^s2=g^m(mod p)

2.密鑰管理

(1)密鑰生成

(2)密鑰分發

密鑰協商(Diffie-Hellman)：

中心分發(KDC)：

四、密碼分析

1.敵手模型

敵手一般假定在發送方與接收方之間，能夠截獲密文并企圖恢復明文

2.攻擊場景

攻擊性從上到下依次提高

唯密文攻擊: 攻擊者只能得到若干條同一密鑰加密的密文
已知明文攻擊: 攻擊者能拿到若干同一密鑰加密的明密文對
選擇明文攻擊: 攻擊者可以選擇一些明文并得到對應的密文
選擇密文攻擊: 攻擊者可以選擇一些密文并得到對應的明文

3.攻擊方式

(1)窮舉法

暴力窮舉: 窮舉全部密鑰
字典攻擊: 用所有可能的密鑰組成一個字典進行窮舉

(2)頻率分析

利用明文已知的統計規律進行破譯
單字符:
最常出現依次為E、T、A、O、I、N、S、H、R、D、L(有效攻擊單字符替換和置換密碼)
雙字符：
最常出現依次為TH、HE、IN、ER、AN、RE、DE、ON、ES、ST、EN、AT、TO、NT、HA、ND(有效攻擊多字符替換和置換密碼)
三字符：
最常出現依次為THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH(有效攻擊多字符替換和置換密碼)

(3)長度測驗法

兩個相同的明文段加密成相同的密文段，則者兩個明文段之間的距離大概率是密鑰長度的整數倍，當有多個相同段時，密鑰長度大概率為段間距的最大公因數的因數，再利用重合指數法就可以驗證密鑰長度

(4)重合指數法

當猜對密鑰時，計算的概率值約為0.065，否則約為0.038

(5)社會工程學

通過對知道演算法的人的滲透獲得演算法

(6)逆向工程學

對含有加密演算法的程式進行逆向工程獲取其演算法

(7)彩虹表攻擊

預先計算常見的加密值形成資料庫，破解時查表得到明文

(8)確定性分析

利用已知兩和數學關系進行破譯

(9)差分密碼分析

通過分析兩個明文差值對密文的影響推斷密鑰，利用拉格朗日公式的思想，推斷加密演算法的等價變換破譯密碼

(10)線性密碼分析

尋找給定密碼的演算法的近似表達破譯密碼

(11)差分線性分析

將差分密碼分析和線性密碼分析組合破譯

(12)密鑰相攻擊

根據有某種關系的明密文對進行分析攻擊

導圖