主要三大塊

1.古典密碼

移位密碼：

E(x)= (x + K) mod 26
D(x)= (x - K) mod 26

代換密碼

是指先建立一個替換表，加密時將需要加密的明文依次通過查表，替換為相應的字符，明文字符被逐個替換后，生成無任何意義的字串，即密文，替代密碼的密鑰就是其替換表

歐拉函式：

設a ≥ 1，m ≥ 2, 如果gcd(a, m) = 1,則稱a與m 互素，Zm中所有與m互素元素的個數用φ(m)來表示（函式φ稱為歐拉函式）
例如φ(10) = 4，因為1,3,7,9均和10互質，
計算方法：
1.先化為標準分解式形式（化簡成最小質數的冪乘積）：

例如：

2.再依照下式規則計算


這其中 {1，5，7，11，13，17，19，23，25，29，31，35} 與36 互質，共計12 個

所以如果 m為質數 則 φ(m) = m-1

乘法逆元用拓展歐幾里得求解詳細程序：

例如求15 關于模26的乘法逆元：
15x = 1 mod 26 
這道題轉化成15x - 26y = 1 ：

		解法如下：
		26 = 1× 15 + 11
		15 = 11×1 + 4
		11 = 4 × 2 + 3
		4 = 1 × 3 + 1
		3 = 1 × 3 
		
		∴ 1 = 4 – 3
    		  = 4 – (11 – 4×2)
    		  = 4×3 – 11
  	    	  = (15-11) ×3 - 11
  	    	  = 15×3 - 11×4
  	    	  = (26-11)×3 - 11 ×4
  	    	  = 26×3 - (26 - 15)×7
  	    	  =26×(-4) + 15×7
		∴ x = 7, y = ?4 為此不定方程的一組整數解，15關于模26的乘法逆元為7

群Zm內所有元素關于模26的乘法逆元如下：

1：1
3：9
5：21
7：15
11：19
17：23
25：25

仿射密碼：

假設密鑰K= (7,3), 使用仿射密碼體制加密單詞hot并對得到的密文進行解密，
加密：

加密函式： E(x)= (7x + 3) (mod 26)
根據上面英文字母編碼表得到X

解密：

解密函式：
求得a的乘法逆元為15
D(x) = 15(x - 3) (mod 26)

希爾密碼：

用希爾密碼對明文串x = EastChinaNormalUniversity 進行加密，

密鑰矩陣:

加密：
密文向量 = 明文向量 * 密鑰矩陣 (mod 26)

1. 先將明文串對應英文字母編碼表進行數字轉化 4 0 18 19 2 7 8 13 0 13 14 17 12 0 11 20 13 8 21 4 17 18 8 19 24
   然后兩兩一組寫成矩陣形式：
   
   做補0處理，

2. 接下來開始加密
   
   得到密文矩陣后，按照分組對應的向量轉成字母：
   IK BX NB DH NN JD YE SR OB KB UJ HL W

解密同理用密鑰矩陣的逆矩陣乘以加密結果，

定義在Zm上的矩陣求逆 ：

設矩陣

是定義在Zm上的矩陣,

舉個例子：


這其中，9 關于模26 的乘法逆元為3.

2.對稱密碼體制

AES加密的作業模式

ECB（電子密碼本模式）
之所以使用分組密碼模式是因為分組密碼只能處理定長的資料，如AES處理128bit，那么將明文切分成若干個128bit，分別加密，這種模式就是ECB模式，實際上有很明顯的弱點，現在已經不被使用，

ECB模式是最簡單的一種，它有很嚴重的問題，就是相同的明文會得到同樣的密文，因為每個分組加密方式和密鑰都相同，若分組明文相同，加密后密文也相同，

所以需要尋找一種模式，它至少得滿足：

1. 相同的明文分組加密后密文不同，
2. 明文微小變化都能造成密文有很大變化，

CBC模式（密碼分組鏈接模式）
CBC模式由IBM發明與1976年，在CBC模式中，每個平文塊先與前一個密文塊進行異或后，再進行加密，在這種方法中，每個密文塊都依賴于它前面的所有密文塊，同時，為了保證每條訊息的唯一性，在第一個塊中需要使用初始化向量，

加密跟解密程序如下：

這里引入了初始化向量IV，因為第一組明文不存在"前一個密文"，一般來說每次加密都會生成隨機值來做初始 化向量，

CFB模式 (密文反饋模式）
CFB又稱密文反饋模式，前一個密文分組會被送入密碼演算法的輸入端，再將輸出的結果與明文做異或，與ECB和CBC模式只能夠加密塊資料不同，CFB能夠將塊密文（Block Cipher）轉換為流密文，

加密跟解密程序如下：

OFB模式（輸出反饋模式）
OFB又稱輸出反饋模式，前一組密碼演算法輸出會輸入到下一組密碼演算法輸入，先用塊加密器生成密鑰流，然后再將密鑰流與明文流異或得到密文流，解密是先用塊加密器生成密鑰流，再將密鑰流與密文流異或得到明文，由于異或操作的對稱性所以加密和解密的流程是完全一樣的，

3.非對稱密碼體制

拓展歐幾里得求解同余方程組

1.求解同余方程組：
x ≡ 12 (mod 25)
x ≡ 9 (mod 26)
x ≡ 23 (mod 27)

以上方程組等價于 x = 25a + 12 = 26b + 9 = 27c + 23
移一下項 得：
① : 25a - 27c = 23-12 = 11
②: 26b - 25a = 12-9 = 3

首先對①式運用拓展歐幾里得：

27 = 25×1 + 2
25 = 2×7 + 11
則： 
11 = 25 - 2×7
	 = 25 - (27-25) ×7
	 = 25×8 - 27×7
所以a=8, c=7 
代入x = 25a + 12  = 27c + 23 得：
x = 212

得到合并方程 x = 212 + 25 × 27t 即：x ≡ 212 (mod 675)
然后再跟x ≡ 9 (mod 26) 合并

x = 212 + 675t = 26b + 9
26b - 675t = 203
675 = 26×25+25
25 = 25×1
所以：  
203 = (26-25)×203
	= (26 - (675-26*25))×203
	=  26×5278 - 675×203
b=5278 , t=203
代入得x = 137237

得到合并方程 x = 137237 + 25 × 27×26t 即：x ≡ 137237 (mod 17550) , x=14387
x = 14387 + 17550n (n∈Z）

2.求解如下同余方程組：
13x ≡ 4 (mod 99)
15x ≡ 56 (mod 101)

這類同余方程組帶著系數讓人頭大，但是也不妨礙使用拓展歐幾里德，
首先去掉系數：
x ≡ 46 (mod 99)
x ≡ 98 (mod 101)
去系數步驟如下：這里列舉利用二元一次不定方程方法：
13x ≡ 4 (mod 99) 轉化為 13x-99y = 4
然后用拓展歐幾里德：
13×46-99×6 = 4
x=46, y=6
所以不定方程13x-99y = 4 的所有解為
x=46 + 99t
y=6+13t
所以原同余方程解為：x ≡ 46 (mod 99)

消去系數后變成基本的求解同余方程組：
x = 99a+46 = 101a+98
消去x得： 99a - 101b = 52
拓展歐幾里德走你：x = 7471 (mod 9999)
x = 9999 n + 7471 (n ∈ Z)

本原元求解

當a模n的階為φ(n)，也就是說當且僅當x是φ(n)的倍數，使得ax ≡1(mod n)成立，此時稱a為n的本原元，

假如求11的本原元：
步驟如下：
1.利用歐拉函式求φ(11) = 11-1 = 10
2.對10進行歐拉素因子分解 10 = 2 * 5
3.計算：2的平方 =4 mod 11 != 1 并且 2的5次方mod 11 !=1
則2 就是11的一個本原元

，，，這個來的有點輕松了，換一個數
求7的本原元：
1.φ(7) = 6
2. 6 = 2*3
3. 2的平方mod 7 !=1 ，但是 2的3次方mod7 =1, 所以2不是，
繼續往下，，3的平方mod7!=1 并且3的3次方mod7!=1 所以3是7的一個本原元，

所以精髓就是
要恒成立~

RSA演算法程序

一、密鑰生成

1. 隨機選擇兩個不相等的質數p和q，(這兩個質數越大，就越難破解),我們為了方便舉例，選取5和11

2. 計算p和q的乘積n 和歐拉函式φ(n)
   n = 5×11 = 55
   φ(n) = (p-1)(q-1) = 40

3. 隨機選擇一個整數b，條件是1< b < φ(n)，且b與φ(n) 互質…我們就選擇3吧，方便計算

4. 計算b對于φ(n)的模反元素a
   a ≡ b^-1 (mod φ(n)) ≡ 3^-1 mod 40

   即：a×3 ≡ 1 mod 40
   (有小伙伴可能不知道怎么得來的，，a = n×40 + 3^-1 ,等式兩邊同乘3 即 3a = 3n × 40 + 1)

   這個時候就又到了我們熟悉的拓展歐幾里德求解不定方程，，不熟的參考上一篇歐幾里德演算法、拓展歐幾里德、中國剩余定理多練習一下，

   a×3 ≡ 1 mod 40 =>> 3a - 40y = 1

   得: a = 27, y = 2 是上述不定方程的一組解

5. 好了，到此整理一下Alice算的結果：
   公鑰pk:(n = 55, b = 3)
   私鑰sk:(p = 5,q = 11, a = 27)

   (實際應用中公鑰和私鑰的資料都采用ASN.1格式表達)

至此，我們的公私鑰對生成階段結束，下面開始加密

二、加密和解密
假設Bob要向Alice發送加密資訊x，他就要用Alice的公鑰 (n, b) 對x進行加密，
重點：x 必須是整數（字串可以取ascii值），且x必須小于n，

這里我們例子中的n相對較小，所以我們需要將明文拆開進行多次加密：

假設我們加密明文 987654
一個一個來：
Ek(x) = x^b (mod n) = 9³ mod 55 = 14
Ek(x) = x^b (mod n) = 8³ mod 55 = 17
Ek(x) = x^b (mod n) = 7³ mod 55 = 13
Ek(x) = x^b (mod n) = 6³ mod 55 = 51
Ek(x) = x^b (mod n) = 5³ mod 55 = 15
Ek(x) = x^b (mod n) = 4³ mod 55 = 9

最終明文結果為：14 17 13 51 15 9

然后 Alice用自己的私鑰進行解密：
Dk(y) = y^a (mod n) =14²⁷ mod 55 = 9
Dk(y) = y^a (mod n) =17²⁷ mod 55 = 8
Dk(y) = y^a (mod n) =13²⁷ mod 55 = 7
Dk(y) = y^a (mod n) =51²⁷ mod 55 = 6
Dk(y) = y^a (mod n) =15²⁷ mod 55 = 5
Dk(y) = y^a (mod n) =9²⁷ mod 55 = 4

計算出明文：987654

ElGamal加密演算法

一.密鑰生成

1. 對于Bob,首先要隨機選擇一個大素數p，且要求p-1有大素數因子，再選擇一個模p的本原元α，將p和α公開，我們為了方便計算取p = 37,則Z37的一個本原元α = 2.

2. 隨機選擇一個整數d作為密鑰，2≤d≤p-2 ，我們選擇d = 5,

3. 計算β=α^d mod p，β=2⁵ mod 37 = 32

二.加密
假設Alice 想發送訊息 x = 29

1. 首先選取亂數k , 假設k = 7
   則： y1 = α^k mod p = 2⁷ mod 37 = 17
   y2 = x β^k mod p = 29×32⁷ mod 37 = 33
2. 將密文y = (17,33)發送給Bob

三.解密
Bob收到密文y = (17,33) 后恢復明文如下：
x = y2 (y1^d) ^-1 mod p
= 33 (17⁵) ^-1 mod 37
= 33×2 mod 37
= 29