現實中常遇到的一個問題：
假設有兩個人 Alice 和 Bob，他們不能互相見面，只能透過不同的中間人轉發訊息。
可是，他們想確認接收到的訊息，真的是由對方發出的。
在這個情況下，因為每個人都有 Bob 的 Public Key (PKBob)，
所以即使 Bob 收到 Enc({I am Alice}, PKBob)，也不能代表這句是由 Alice 發出。
面對這種情況，有兩種解決方法。
第一種是 Alice 和 Bob 先互相見面，交換機密，然後 Alice 和 Bob 之間可以透過不斷試探對方（例如問機密中有沒有某個字），來確認對方的身份。這種做法叫 ZKP (Zero Knowledge Proof)，雖然聽起來簡單，但操作起來並不容易。因為要互相見面一次，而且試探過程不能只問一條問題。所以，要透過問多條問題，還要小心選題，才能 99.999...% 確保對方身分。
第二種方法，就是利用電子簽名，就比較常用。由於每個人都會儲起自己的 Private Key，所以如果我可以利用自己的 Private Key 為文章做些記號，然後讓對方用我的 Public Key 驗證這個記號，對方就能 100% 相信，文章是我寫的（因為理論上只有我才有自己的 Private Key）。這種方法既可以善用 Public / Private Key，又可以確保 non-repudiation，所以一直都十分受歡迎。
---
ECDSA (Elliptic Curve Digital Signature Algorithm) 的算法：
公開參數 Public Key Parameters:
α, β (elliptic curve), p (large prime), G (elliptic curve base point), n (order), h (co-factor)
公鑰 Public Key： d_a
私鑰 Private Key：d_a • G
訊息： m
簽名過程：
先選一個 random k (under integer with order n (ℤn))，
計算出 P = k • G = (x_p, y_p)。
再計算 r = x_p mod n 和 s = [ k^(-1) * (m + r * d_a) ] mod n。
最後產生 output signature = (s, r)。
驗證過程：
先計算 u_1 = ( s^(-1) * m ) mod n
再計算 u_2 = ( s^(-1) * r ) mod n
得出 P = u_1 • G + u_2*(PK) = u_1 • G + u_2*d_a • G
= {[( s^(-1) * m ) + ( s^(-1) * r * d_a )] mod n } • G
= {[ (s^(-1)) * ( m + r * d_a )] mod n } • G
= {[ k^(-1) * (m + r * d_a) * ( m + r * d_a ) ] mod n } • G = (x_p, y_p)
如果 r = x_p mod n，則代表驗證成功。
詳細證明的話，需用到 elliptic curve 的 multiplication / addition 公式，
由於比較繁複，所以到有需要就再補充吧。
---
參考：
[1] https://www.maximintegrated.com/en/design/technical-documents/tutorials/5/5767.html
[2] Chapter 13.5 - Elliptic Curve Digital Signature Algorithm - (P.430), CRYPTOGRAPHY AND NETWORK SECURITY PRINCIPLES AND PRACTICE SEVENTH EDITION, William Stallings
Showing posts with label Elliptic Curve. Show all posts
Showing posts with label Elliptic Curve. Show all posts
Thursday, December 12, 2019
Monday, September 23, 2019
Understanding Elliptic Curve Cryptography（橢圓曲線加密學）
要理解 ECC, 首先要了解 Elliptic Curve 的特性和定義。
以下內容會以最簡單的方式表達。
1. Elliptic Curve 的定義：
- y^2 = x^3 + ax + b
- 當中 4a^3 + 27b^2 != 0 （有 cusp 或者 self-intersection 交點的曲線都不算 Elliptic Curve）
符合 EC 的例子（a = -7 , b = 10）：
---
2. Elliptic Curve 的特性：
- 用圖片表示的話，你會發現所有 EC 都會有 P+Q+R=0 的特性
- （注意：這裏用的 P/Q/R 並非普通座標計算，而是有特定的公式）
用圖片表達，你會發現以下的現象：
為了方便日後討論，我們重新定義 EC 的加法「＋」和乘法「・」的意思：
加法 (Algebraic Addition)：
- 假設 P != Q，斜率 m = ( y_p - y_q ) / ( x_p - x_q )
- 如果 P = Q，斜率 m = 3x_p^2 + a / 2y_p （如果用上一條式，除 0 計不到啊）
- R = ( x_r , y_r ) , x_r = m^2 - x_p - x_q , y_r = y+p + m(x_r - x_p)
乘法 (Scalar Multiplication)：
- 這個簡單得多，n・P 不就是 P + P + ... + P 共 n 次嗎？
- 所以計法就是不斷用上面的加法，一直加到 n 次
- （但如果真的加 n 次，計算時間就會太繁複，所以有人想到用 double and add 的方法加速，在此不述）
---
3. 加了餘數 (modulo) 的 EC 公式
加了餘數的公式將會變成：
- y^2 = (x^3 + ax + b) mod p
- 當中 (4a^3 + 27b^2) != 0 mod p
- 假設 P != Q，斜率 m = ( y_p - y_q )*( x_p - x_q )^-1 mod p
- 如果 P = Q，斜率 m = (3x_p^2 + a)*(2y_p)^-1 mod p
- R = ( x_r , y_r ) , x_r = (m^2 - x_p - x_q) mod p , y_r = [ y+p + m(x_r - x_p) ] mod p
可見即使加了 mod，P+Q+R = 0 的特性仍然生效，而且公式也很像樣（數學證明在此不述）。
以下圖表則是 mod 版本的 EC：
---
4. 找出重複規律
Mod 版的 EC 在不斷進行 P 點相加後，會出現重複規律。
例如 y^2 = (x^3 -x + 3) mod 37，如果從 P=(2,3) 開始，每加 7 次就會出現 R = (0,0)
我們要找出其最小規律 (subgroup order n) ，任由選一個規律倍數 (order N)，
並且只用這個規律中的餘因子 (cofactor h = N/n) 來進行加密。
例子：y^2 = (x^3 -x + 3) mod 37, n = 7, N = 7, 14, 21, 28, 42, 49 ...
最後，G = h・P 將會用作加密用途。
h 會成為私密鑰匙。對方如果想找出 h，唯一方法就只有不斷加 P。
同時，因為每次加 P 都要用 double and add，相比傳統 RSA，破解時間會較長。
同時，因為每次加 P 都要用 double and add，相比傳統 RSA，破解時間會較長。
---
5. 用作非對稱加密 (Asymmetric Encryption)
公鑰 (Public Key): a, b, p, G, P
私鑰 (Private Key): h
加密 M ：C = {kP, M + kG} （k 只有發送者知道）
解密 C：M + kG - hkP = M + khP - hkP = M
---
6. 用作交換共同金鑰 (EC Diffie-Hellman Key Exchange)
假設 Alice 和 Bob 均使用同一點 G:
Alice 公鑰 (Public Key): Ha = da・G
Alice 私鑰 (Private Key): da
Bob 公鑰 (Public Key): Hb = db・G
Bob 私鑰 (Private Key): db
Alice 計算出 S = da・(Hb) = da・db・G
Bob 計算出 S = db・(Ha) = db・da・G
所以，他們就能有同一條金鑰 S 用作對稱加密。
---
7 . 用作簽署 (ECDSA)
由於只是 DSA 協議的變種，在此不再詳述。
---
參考資料：
http://amitmason.blogspot.com/2016/08/elliptic-curve-cryptography_37.html
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
CX4024 Lecture 4 - 2018, Anwitaman Datta, Nanyang Technological University
Subscribe to:
Posts (Atom)