多點頭發，少點代碼。
Hello，小夥伴們，《密碼學系列》終于又要更新啦，今天小馮童學（沒錯，這是除了龍叔以外的另一位小姐姐）認真的分析了分析，發現《密碼學系列》從第一期開始到現在已經兩個多月了，雖然還有很多知識沒有細細道來，但是基礎架構已經基本完善了，如果小夥伴們在密碼學方面還有别的問題，可以直接在公衆号【龍躍十二】背景私信，随時線上
也歡迎大家多多關注微信公衆号【龍躍十二】，龍叔和小馮童學繼續為你分享知識。
在公要加密體制的分析之前，我們先聊聊數論…
數論：
數論是密碼學特别是公鑰密碼學的基本工具，也是了解密碼學的前提，是以還是要适當的了解一些簡單的數論知識。或許當你看完數論知識，再回去看之前的密碼學文章會有其他味道哦。
以下幾個基本的數論知識，是小馮精心挑選出來的，看懂這幾個，其他的都不是問題。
模運算 ：
設 n 是一正整數，a是整數，如果用 n 除 a，得商為 q，餘數為 r，則
a = qn + r，其中0 ≤ r < n，q = [a/ n]
注：[x] 為小于或等于 x 的最大整數。
用 a mod n 表示餘數 r，則 a = [a/ n]· n + a mod n。（ a mod n也就是常說的a模n取餘）
費爾瑪定理：
若 p 是素數, a 是正整數且 gcd( a, p) = 1,則 ap - 1 ≡ 1 mod p。（gcd是指最大公約數）
歐拉定理 ：
- 歐拉函數：設 n 是一正整數，小于 n 且與 n 互素的正整數的個數稱為 n 的歐拉函數，記為 φ( n)。
- 歐拉定理：若 a 和 n 互素, 則 aφ( n) ≡1 mod n
歐幾裡得算法:
歐幾裡得算法是數論中的一個基本技術,主要是用來求兩個正整數的最大公因子的簡化過程。
而推廣的歐幾裡得算法不僅可求兩個正整數的最大公因子，而且當兩個正整數互素時，還可求出其中一個數關于另一個數的乘法逆元。（emm…逆元是不是有是個新詞，百度一下吧）
求最大公因子
歐幾裡得算法是基于下面一個基本結論:
對任意非負整數 a 和正整數 b，有 gcd(a, b) = gcd(b, a mod b)。
是以可假定算法的輸入是兩個正整數，設為 d、f，并設 f > d。
求乘法逆元
如果 gcd(a, b) = 1 ，則 b在 mod a下有乘法逆元( 不妨設 b< a) ,即存在一 x ( x < a) ,使得 bx≡1 mod a。推廣的 Euclid 算法先求出 gcd( a, b) ,當 gcd( a, b) = 1 時， 則傳回 b 的逆元。
平方剩餘
設 p 是一素數，a 小于 p，稱 a 是 p 的平方剩餘，如果方程 x2 ≡ a ( mod p) 有解。否則稱為非平方剩。
emmm…小馮童學還是覺着這幾個是平日裡用的多的，小夥伴們還是需要多了解一下。
公要密碼體制：
在公鑰密碼體制以前的整個密碼學史中，所有的密碼算法，包括原始手工計算的、由機械裝置實作的以及由計算機實作的，都是基于代換和置換這兩個基本工具。
而公鑰密碼體制則為密碼學的發展提供了新的理論和技術基礎。
- 公鑰密碼算法的基本工具不再是代換和置換，而是數學函數。
- 公鑰密碼算法是以非對稱的形式使用兩個密鑰。
公鑰密碼算法的最大特點，概括起來就一句話：
采用兩個相關密鑰将加密和解密能力分開，其中一個密鑰是公開的，簡稱公開鑰，用于加密; 另一個密鑰是為使用者專用，因而是保密的，簡稱秘密鑰，用于解密。是以公鑰密碼體制也稱為雙鑰密碼體制。
算法有以下重要特性:
已知密碼算法和加密密鑰，求解密密鑰在計算上是不可行的。
加密：
公鑰體制加密框圖
我們來分解一下加密過程：
- ① 要求接收消息的端系統，産生一對用來加密和解密的密鑰，如圖中的接收者 B，産生一對密鑰 PKB , SKB ,其中 PKB 是公開鑰，SKB 是秘密鑰。
- ② 端系統 B 将加密密鑰 ( 如圖中的 PKB ) 予以公開。另一密鑰則被保密 ( 圖中的 SKB)。
- ③ A 要想向 B 發送消息m，則使用 B 的公開鑰加密 m，表示為 c= E PKB [ m]， 其中 c 是密文，E 是加密算法。
- ④ B 收到密文 c 後，用自己的秘密鑰 SKB 解密，表示為 m =DSKB [c]，其中 D 是解密算法。
認證：
公鑰加密算法不僅能用于加、解密，還能用于對發方 A 發送的消息 m 提供認證。
公鑰密碼體制認證框圖
戶 A 用自己的秘密鑰 SKA對 m 加密,表示為 c = ESKA [ m]
将 c 發往 B。B 用 A 的公開鑰 PKA 對 c解密, 表示為 m = DPKA [ c]，因為從 m 得到 c 是經過 A 的秘密鑰 SKA 加密,隻有 A 才能做到。是以 c 可當做 A 對 m 的數字簽字。
另一方面，任何人隻要得不到 A 的秘密鑰 SKA就不能篡改m，是以這個過程獲得了對消息來源和消息完整性的認證。
以上認證過程中，由于消息是由使用者自己的秘密鑰加密的，是以消息不能被他人篡改，但卻能被他人竊聽。這是因為任何人都能用使用者的公開鑰對消息解密。為了同時提供認證功能和保密性, 可使用雙重加、解密。
雙重加解密：
公鑰密碼體制的認證、保密框圖
發方首先用自己的秘密鑰 SKA對消息 m 加密，用于提供數字簽字。用收方的公開鑰 PKB第 2 次加密。
加密過程為：c = EPKB [ESKA [m]]
解密過程為：m = DPKA [DSKB [c]] 即收方先用自己的秘密鑰, 再用發方的公開鑰對收到的密文兩次解密。
這就是公要加密體制的基本内容，你是不是想問怎麼還不講算法，下來我們就看看關于公鑰加密體制的算法。
RSA算法：
RSA 算法是1978年由R.Rivest , A.Shamir 和 L.Adleman 提出的一種用數論構造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制。
密鑰的産生：
① 選兩個保密的大素數 p 和 q。
② 計算 n = p × q，φ(n) = (p - 1) (q - 1) ,其中 φ(n) 是 n 的歐拉函數值。
③ 選一整數 e，滿足 1 < e < φ(n)，且 gcd(φ(n) , e)= 1。
④ 計算 d，滿足 d·e≡1 mod φ(n)，即d是 e 在模φ(n)下的乘法逆元，因 e 與φ(n)互素，由模運算可知，它的乘法逆元一定存在。
⑤ 以{e，n}為公開鑰，{d, n}為秘密鑰。
加密時首先将明文比特串分組，使得每個分組對應的十進制數小于n，即分組長度小于log2 n。然後對每個明文分組m，作加密運算:c ≡ me mod n
解密：
對密文分組的解密運算為: m ≡ cdmod n
計算問題：
RSA 的加密、解密過程都為求一個整數的整數次幂, 再取模。如果按其含義直接計算, 則中間結果非常大，有可能超出計算機所允許的整數取值範圍，是以我們應該考慮如何提高加、解密運算中指數運算的有效性。
橢圓曲線密碼體制：
為保證 RSA 算法的安全性，它的密鑰長度需一再增大，使得它的運算負擔越來越大。相比之下，橢圓曲線密碼體制 ECC( elliptic curve cryptography) 可用短得多的密鑰獲得同樣的安全性，是以也就具有更大的使用空間。
我們先來看看什麼是橢圓曲線？
高中畢業沒幾年的我們這個東西應該還有印象….hhhhh
密碼中普遍采用的是有限域上的橢圓曲線，有限域上的橢圓曲線是指曲線方程定義式y2+axy+by = x3+cx2+dx+e，所有系數都是某一有限域GF(p)中的元素 (其中p為一大素數）。其中最為常用的是由方程 y2 +axy + by = x3 +ax+b(mod p) ，其中(a,b ∈ GF(p),4a3+27b2(mod p) ≠ 0) 。
Diffie-Helmlan密鑰交換：
- 首先取一素數 p≈2180 和兩個參數a、b，則得上邊說到的方程來表達的橢圓曲線及其上面的點構成的Abel群Ep( a, b)。
- 然後，取 Ep (a, b)的一個生成元 G( x1, y1)，要求G的階是一個非常大的素數， G 的階是滿足 nG = O的最小正整數 n。Ep ( a, b) 和 G作為公開參數。
兩使用者 A 和 B 之間的密鑰交換如下進行:
① A 選一小于 n 的整數 nA，作為秘密，并由 PA= nA·G産生 Ep ( a, b)上的一點作為公開鑰。
② B 類似地選取自己的秘密鑰 nB 和公開鑰PB 。
③ A、B 分别由 K = nAPB和 K =nBPA 産生出雙方共享的秘密鑰。
EGlamal密碼體制
- 密鑰産生過程: 首先選擇一素數 p 以及兩個小于 p 的随 機數 g 和 x，計算 y≡ gx mod p。以( y、g、p)作為公開密鑰，x作為秘密密鑰。
- 加密過程: 設欲加密明文消息M，随機選一與p-1互素的整數k, 計算 C1 ≡ gk mod p，C2 ≡ yk M mod p， 密文為 C = ( C1 , C2 )。
- 解密過程: M = (C2/ C1x) mod p