參考文獻(xiàn)
- 《PKI/CA 與數(shù)字證書技術(shù)大全》書籍
-
ECC加密算法入門介紹
如有理解bug, 請(qǐng)大家指正兜粘。
非對(duì)稱加密算法有多種喳篇，比如 RSA, Elgamal, 背包算法, Rabin， D-H, ECC, SM2 等自沧。如下僅僅對(duì) RSA, ECC, SM2 算法進(jìn)行解釋。
RSA
RSA 算法是由美國(guó)三位科學(xué)家 Rivest、Shamir 和 Adleman 于1976年提出并在1978年正式發(fā)表的公開(kāi)密碼加密算法秧均，其命名取自三位創(chuàng)始者的首字母縮寫。該算法基于數(shù)論中的大數(shù)分解難題号涯，即：根據(jù)數(shù)論目胡，尋求兩個(gè)大素?cái)?shù)比較簡(jiǎn)單，而將它們的乘積分解開(kāi)則極為困難链快。
理論來(lái)源于數(shù)論
歐拉函數(shù) ：
歐拉函數(shù)是數(shù)論中很重要的一個(gè)函數(shù)誉己，歐拉函數(shù)是指：對(duì)于一個(gè)正整數(shù) n ，小于 n 且和 n 互質(zhì)的正整數(shù)（包括 1）的個(gè)數(shù)域蜗，記作 φ(n) 巨双。
完全余數(shù)集合：
定義小于 n 且和 n 互質(zhì)的數(shù)構(gòu)成的集合為 Zn ，稱呼這個(gè)集合為 n 的完全余數(shù)集合霉祸。 顯然 |Zn| ＝φ(n) 筑累。
有關(guān)性質(zhì)：
對(duì)于素?cái)?shù) p ，φ(p) = p -1 丝蹭。
對(duì)于兩個(gè)不同素?cái)?shù) p慢宗， q ，它們的乘積 n = p * q 滿足 φ(n) = (p -1) * (q -1) 。
這是因?yàn)?Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} 镜沽， 則 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ＝φ(p) * φ(q) 敏晤。
歐拉定理 ：
對(duì)于互質(zhì)的正整數(shù) a 和 n ，有 a^φ(n) ≡ 1 mod n 缅茉。
因此嘴脾， RSA 算法中，用戶有兩個(gè)密鑰：公鑰為 PK = {e, n} 和私鑰 SK = {d, n}, n 為兩個(gè)素?cái)?shù)p, q的乘積,即 n = p * q（素?cái)?shù)p宾舅，q一般為100位以上的十進(jìn)制數(shù)）, e 和 d 滿足一定的關(guān)系统阿，如只知道 e, n 很難計(jì)算出 d，這里是 a ^ (e * d) ≡ a (mod n) 筹我。即 e * d ≡ 1 mod φ(n) 扶平。<b>根據(jù)上述定理可得出 p， q 蔬蕊，φ(n) 均小于 n结澄。</b>
簡(jiǎn)單從上述公式可看出 公鑰加密與私鑰解密，及私鑰加密與公鑰解密 是能到達(dá)同樣的效果岸夯，但通常是公鑰會(huì)發(fā)布公告麻献，所以用公鑰解密的是不安全的。
具體過(guò)程如下：
(1) 加密/解密過(guò)程
若用整數(shù)X表示明文猜扮，用整數(shù)Y表示密文勉吻，則加密和解密運(yùn)算過(guò)程為：
加密： Y = (X ^ e) mod n
解密： X = (Y ^ d) mod n
(2) 秘鑰產(chǎn)生過(guò)程
- 獲取兩個(gè)長(zhǎng)度大于 100 位的素?cái)?shù) p, q;
- 計(jì)算 n = p * q;
- 計(jì)算出 n 的歐拉函數(shù) φ(n) = φ(p * q) = (p - 1) * (q - 1) ;
- 計(jì)算 e，從 (0, φ(n) ] 中任選一個(gè)與 φ(n) <b>互素</b>的數(shù)字 e, 作為公鑰的加密指數(shù)
- 計(jì)算 d旅赢，通過(guò)計(jì)算出滿足公式 e * d = 1 mod φ(n) 的 d 作為解密指數(shù)
即 公鑰: PK = {e, n} ; 私鑰 SK = {d, n}
ECC
ECC 是橢圓曲線密碼 (Elliptic Curve Cryptography) 的縮寫齿桃。1985 年， Koblitz 和 Miller 提出基于橢圓曲線離散對(duì)數(shù)問(wèn)題 (ECDLP, Elliptic Curve Discrete Logarith Problem) 的公鑰密碼體制煮盼，即 橢圓曲線密碼體制 ECC 短纵。 它是用橢圓曲線有限群代替基于有限域上離散對(duì)數(shù)問(wèn)題公鑰密碼中的有限循環(huán)群所得到的一類密碼體制。由于在一般的橢圓曲線群中沒(méi)有亞指數(shù)時(shí)間算法解僵控，所以橢圓曲線密碼成了目前最流行的公鑰密碼體制香到。
ECC 算法的基本原理如下：
(1) 有限域 Fp 與橢圓曲線
有限域 Fp 是由小于素?cái)?shù) p 的非負(fù)整數(shù)組成的集合{0, 1, 2, 3, ...., p - 1} ，其上的運(yùn)算是模 p 的算術(shù)運(yùn)算报破。
Fp 上的橢圓曲線是滿足方程 y^2 =x^3+ax+b 的 Fp 上的點(diǎn) (x, y) 組成的集合悠就，其中常量 a 和 b也是 Fp 中的元素。
為了詳細(xì)描述一條 Fp 上的橢圓曲線泛烙，應(yīng)該給出如下參數(shù)：
- 素?cái)?shù) p 的值理卑， 為滿足 ECC 的安全性的要求， p 應(yīng)該為 160 以上位長(zhǎng)的素?cái)?shù)蔽氨。
- 常數(shù) a 和 b 的值藐唠， 其中 a 可以取 -3 以提高點(diǎn)運(yùn)算效率帆疟。
- 橢圓曲線上的一個(gè)基點(diǎn) G (稱為生成元)
- 基點(diǎn) G 的階為 n， 一般情況下要求n為素?cái)?shù)且等于橢圓曲線上的點(diǎn)數(shù)宇立。
選擇兩個(gè)滿足下列條件的小于 p (p為素?cái)?shù)) 的非負(fù)整數(shù)a踪宠、b
4 * (a^3) + 27 * (b^2) ≠ 0 (mod p)
則滿足下列方程的所有點(diǎn) (x,y)，再加上 無(wú)窮遠(yuǎn)點(diǎn)O(∞,∞) 妈嘹，構(gòu)成一條橢圓曲線柳琢。
y^2 = x^3 + ax + b (mod p)
其中 x, y屬于 0 到 p-1 間的整數(shù)，并將這條橢圓曲線記為 Ep(a,b)润脸。
(2) ECC 密鑰對(duì)
對(duì)于給定的橢圓曲線參數(shù) {p, a, b, G, n} 柬脸，ECC 的私鑰 d 為滿足 1 < d < n 的隨機(jī)數(shù)，相應(yīng)的公鑰為 P = d*G毙驯。 為滿足安全性要求倒堕， d 必須通過(guò)隨機(jī)或強(qiáng)偽隨機(jī)發(fā)生器產(chǎn)生。
(3) ECC 加密/解密機(jī)制
1爆价、用戶A選定一條橢圓曲線Ep(a,b)垦巴，并取橢圓曲線上一點(diǎn)，作為基點(diǎn)G铭段。
2骤宣、用戶A選擇一個(gè)私有密鑰k，并生成公開(kāi)密鑰K=kG序愚。
3憔披、用戶A將Ep(a,b)和點(diǎn)K，G傳給用戶B爸吮。
4活逆、用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點(diǎn)M（編碼方法很多拗胜，這里不作討論），并產(chǎn)生一個(gè)隨機(jī)整數(shù)r（r<n）怒允。
5埂软、用戶B計(jì)算點(diǎn)C1=M+rK；C2=rG纫事。
6勘畔、用戶B將C1、C2傳給用戶A丽惶。
7炫七、用戶A接到信息后，計(jì)算C1-kC2钾唬，結(jié)果就是點(diǎn)M万哪。因?yàn)?
C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M
再對(duì)點(diǎn)M進(jìn)行解碼就可以得到明文侠驯。
(4) ECC 簽名機(jī)制
軟件作者按如下方法制作注冊(cè)機(jī)（也可稱為簽名過(guò)程）
1、選擇一條橢圓曲線Ep(a,b)奕巍，和基點(diǎn)G吟策；
2、選擇私有密鑰k（k<n的止，n為G的階）檩坚，利用基點(diǎn)G計(jì)算公開(kāi)密鑰K=kG；
3诅福、產(chǎn)生一個(gè)隨機(jī)整數(shù)r（r<n）匾委，計(jì)算點(diǎn)R=rG；
4氓润、將用戶名和點(diǎn)R的坐標(biāo)值x,y作為參數(shù)赂乐，計(jì)算SHA（Secure Hash Algorithm 安全散列算法，類似于MD5）值旺芽，即Hash=SHA(username,x,y)沪猴；
5、計(jì)算sn≡r - Hash * k (mod n)
6采章、將sn和Hash作為 用戶名username的序列號(hào)
軟件驗(yàn)證過(guò)程如下：（軟件中存有橢圓曲線Ep(a,b)运嗜，和基點(diǎn)G，公開(kāi)密鑰K）
1悯舟、從用戶輸入的序列號(hào)中担租，提取sn以及Hash；
2抵怎、計(jì)算點(diǎn)R≡sn*G+Hash*K ( mod p )奋救，如果sn、Hash正確反惕，其值等于軟件作者簽名過(guò)程中點(diǎn)R(x,y)的坐標(biāo)尝艘，因?yàn)?
sn≡r-Hash*k （mod n）
所以
sn*G + Hash*K
=(r-Hash*k)*G+Hash*K
=rG-Hash*kG+Hash*K
=rG- Hash*K+ Hash*K
=rG=R ；
3姿染、將用戶名和點(diǎn)R的坐標(biāo)值x,y作為參數(shù)背亥，計(jì)算H=SHA(username,x,y)；
4悬赏、如果H=Hash 則注冊(cè)成功狡汉。如果H≠Hash ，則注冊(cè)失敗(為什么闽颇？提示注意點(diǎn)R與Hash的關(guān)聯(lián)性)盾戴。
簡(jiǎn)單對(duì)比一下兩個(gè)過(guò)程：
作者簽名用到了：橢圓曲線Ep(a,b)，基點(diǎn)G兵多，私有密鑰k尖啡，及隨機(jī)數(shù)r橄仆。
軟件驗(yàn)證用到了：橢圓曲線Ep(a,b)，基點(diǎn)G可婶，公開(kāi)密鑰K沿癞。
Cracker要想制作注冊(cè)機(jī)，只能通過(guò)軟件中的Ep(a,b)矛渴，點(diǎn)G椎扬，公開(kāi)密鑰K ，并利用K=kG這個(gè)關(guān)系獲得k后具温，才可以蚕涤。而求k是很困難的。
SM2
SM2 算法由國(guó)家密碼局于2012年12月17日發(fā)布的橢圓曲線公鑰密碼算法铣猩，主要滿足電子認(rèn)證服務(wù)系統(tǒng)等應(yīng)用需求揖铜。
該算法主要參數(shù)如下：
- 推薦使用素?cái)?shù)域?yàn)?256 位橢圓曲線。
- 橢圓曲線方程： y^2 = x^3 + ax + b
- 曲線參數(shù)：
p = FFFFFFFE FFFFFFFFFFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a = FFFFFFFE FFFFFFFFFFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
b = 28E9FA9E 9D9F5E344D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
n = FFFFFFFE FFFFFFFFFFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
Gx = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
Gy = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0
