ECC
跟RSA一樣同樣用 elliptic curves, 通常我們可以做以下兩件事:
Digital signatures (public key equivalent of message authentication codes) Alice 用 private key 簽署, 然後其他人用 public key 驗證
Encryption with elliptic curves: 通常用來作金鑰交換, Alice 用 elliptic curve Diffie-Hellman (ECDH) 來產生跟Bob的 shared key
Standard Curve
除了certicom外,IEEE1363和NIST方面有定義出一些建議使用的curve,其中NIST三條標準的 elliptic curve 為:
NIST P256 curve, which is equivalent to an AES-128 key (also known as secp256r1)
NIST P384 curve, which is equivalent to an AES-192 key (also known as secp384r1)
NIST P521 curve, which is equivalent to an AES-256 key (also known as secp521r1)
另外還有其他著名的curve像是 Curve25519 curve (key exchange使用), Ed25519 curve (數位簽章使用),更多curve 選擇可參考
最近也有一個有趣的專案Million Dollar Curve,想要用樂透等公開random source來建立第三方可驗證的curve
ECC的 Key Exchange (ECDH) 紀錄在 in NIST publication 800-56Ar2中
Mathematics Behind Elliptic Curves
Elliptic curve是什麼呢? 事實上著名的Fermat's Last Theorem便是由elliptic curve解開的(不過是定義於實數域的elliptic curve),可參考數學女孩
Wolfram MathWorld有完整數學上的定義
我們可以把他想成由以下方程式組成的點:
其中 (用來排除 singular curves). 這種形式稱為 Weierstrass normal form for elliptic curves
根據不同的a, b值, elliptic curves 會呈現不同的形狀, 我們在實數上畫出來 elliptic curves 是對稱x軸的!
通常我們會把無窮遠點也加入 curve中,我們將它標記為 0
故納入無窮遠點後的橢圓曲線為:
, 以下我們簡單的畫出elliptic curve和上面的點加法(後面會進一步介紹)給讀者參考:
Group
我們這邊簡單介紹一些abstract algebra中的群論:一個set我們定義 "addition" 並標示為 +, 此 set G 稱之為 group, addition 必續根據下列四個性質來定義!
Closure: 若在內, 則也要在 內
Associativity:
有 identity element 使得
所有元素有 inverse, 亦即對任意 一定找的到 使得
若再加上 commutativity: 則此 group 稱為 abelian group.
我們常見的加法配上 integer numbers 組成的set 便是 group (事實上他是 abelian group).然而自然數就不是了,因為不符合第四個條件。
若我們能證明某一set滿足以上性質,我們就可以借用抽象代數中的群的相關特性!! 例如: identity element是唯一的,inverse也是唯一的
Group Law of Elliptic Curve
Geometric addition
我們可以定義橢圓曲線群如下:
Group 中的元素是 elliptic curve上的點
Identity element 是無窮遠點 0;
橢圓曲線上點 P 的 inverse 是對 x 軸鏡射的點
Addition定義為: 給定三個 aligned 且 non-zero 的點 P, Q, R, P+Q+R=0
經由這樣的定義我們可以得知這個點是無順序性不相關的,也就是說假設 P, Q, R 是 aligned, 則 P+(Q+R)=Q+(P+R)=R+(P+Q)=⋯=0. 因此我們的 +
operator 是 associative 且 commutative 故為一個 abelian group! 既然在abelian group我們就可以把 P+Q+R=0 寫成 P+Q=-R 因此得到圖像加法如下:
可以由此來感受加法!!
Algebraic addition
接下來我們把上述加法寫成數學式,考慮兩個點,假設兩者不同,通過兩點的線斜率為
而他與橢圓曲線的交點為
因此
若的話,經由微分 可得
Scalar Multiplication
連加次可寫成此運算稱為scalar multiplication。
這邊可感受乘法
在實際時做上,我們可以藉由double-and-add來加速此運算
Logarithm
橢圓曲線基於的數學問題是elliptic curve discret logarithm problem(ECDLP): 給定我們可以很快利用上述方法算出,然而給和要推就不容易了...。
Finite Field
實數域的elliptic curve並不能拿來密碼學使用(前述是在實數中),這邊我們介紹Galois Field (Finite Field)。 Finite field 是一個元素為有限數目的set, 一個簡單的例子是 integers modulo p (為質數)。 我們通常寫成 .
在 field 中我們有兩種 binary operations: addition (+) 和 multiplication (·), 兩者皆為 closed, associative 且 commutative。對此兩種運算, 都存在著唯一的identity element, 且對field內的 element 都有唯一的 inverse element。 最後 multiplicationy在field中是 distributive over addition:
在field中可寫成,
EC over Finite Field
接下來我們將elliptic curve限制在 Finit Field中 (注意其仍為abelian group!)
0 為無窮遠點, 且 a 和 b 為兩個 中的 integer.
來感受一下現在他長怎麼樣吧( 當 對每一x最多會有兩點y。 另外點是對 對稱的!)
經過此一限制之後,geometric addition會變得不太一樣(可以玩前述tool),不過我們保持定義的話,algebra addition仍然可保持相同公式(多了modulus P)。
接下來我們可以證明出 multiples of P 實際上是一個 cyclic subgroup of the group formed by the elliptic curve
,藉此我們進一步定義出elliptic curve的order(所有點的數目)和點的order(加幾次可以回到自己)。
Elliptic Curve for Cryptography
對密碼學應用來說,我們會去選擇高order的 subgroups。 實務上我們會先選 elliptic curve, 然後計算 order (N), 選擇 high divisor的(n) 來當 subgroup order, 最後找到適合的 base point。
Lagrange's theorem 告訴我們 永遠是整數 (因為 為 的 divisor). 稱作 cofactor of the subgroup.
假設 為定義在 field 上的 elliptic curve,根據 group addition law 我們可以知道每一個上的點都可以產生出一個 cyclic group 。若這個 的 order 是質數的話就可以用在cryptography上。
這表示group operation, inversion, hasing都可以很快完成,但是DLP很難解
因此跟乘法群的對照便是我們可以用上的點配上點加法來類比乘法群元素。在乘法群中,我們會選擇一個的subgroup order為,但任意選通常不會有此order,因此常見的做法是用演算法隨機hash到一個 ,然後再把他exponential 成 ,(為 的元素數量)。
橢圓曲線也是如此,假設,
選一個curve ,計算他的 order N
選一個prime 整除,但是不能整除, 來建立出 order 為 的 subgroup。並計算 cofactor
選擇隨機點 ,然後計算 (hashing也是如此做)
接下來group operation用addition,negate去反轉做標,點乘法用point multiplication。
若 為 , 回到 step 3. 最後我們得到 subgroup with order 和 cofactor .
Domain Parameter
Elliptic curve algorithms 是定義於 cyclic subgroup of an elliptic curve over a finite field 因此我們會有下列參數:
The prime that specifies the size of the finite field.
The coefficients and of the elliptic curve equation.
The base point that generates our subgroup.
The order of the subgrouop.
The cofactor of the subgroup.
也就是 domain parameters包含tuple
事實上有些curve是不安全的,我們如何確保選出的curve是安全的呢,有一種常見作法如下
Curve 用此方法產生稱作 verifiably random. 這個用 hashes 產生 parameters 的方法叫 "nothing up my sleeve", 常常被用於 cryptography中
他給我們一些信心,curve不會是 crafted 而有特定 vulnerabilities 只有設計者知道。 事實上設計者給我們seed和curve, 他沒辦法控制我們選取 parameters 和 , 因此比較有安全感。
標準產生和驗證 random curves 的方法訂於 ANSI X9.62 並用到 SHA-1. 可以看SECG的相關說明
可以用以下程式來確認:
ECC
Private key 為在之間的 random integer ( 為 subgroup 的order).
Public key 為 這個point ( 為 subgroup的base point).
接下來我們將重點放在 ECDH (Elliptic curve Diffie-Hellman)(用於加密), 和 ECDSA (Elliptic Curve Digital Signature Algorithm)(用於簽章)
最後,我們上述都是在prime filed, affine coordinate, Weierstrass form curve,更多的其他選擇和加法公式可參考 EFD
Pyelliptic
在這邊我們先使用 PyElliptic 這個提供 ECC class 的library,來實際應用在金鑰交換以及數位簽章上
Generating Keys
假設我們AES用256 bit, 所以這邊至少要用到 P521的curve
Public 和 private keys 可以從curve exported 出來
Signing Messages
通常做數位簽章的時候, 我們會先計算 message 的 hash 再做簽章。 PyElliptic 會使用 SHA-512 來做 ECDSA.
驗證時候的input是 serialised public key 然後匯入 pyelliptic.ecc.ECC instance 做運算
Encryption
現在來說明如何用ECDH來產生shared key
用 pyelliptic時, private key 要是 instance of pyelliptic.ecc.ECC; 而 public key 要是 serialised form.
Ephemeral keys
接下來我們來看看常見的 hybrid encryption的方式,我們會用 ephemeral keys 來做 encryption;也就是我們每次加密會產生 elliptic curve key pair 這種加密方法叫 elliptic curve integrated encryption scheme, ECIES。 (或更準確來說,因為 key exchange 為 on the fly 完成,故稱為 ECDHE)
上述我們將 public key 加到開頭, 包含 public key 的長度,然後將 ciphertext 接在後面。 解密時需要解回 public key (先讀取 length 然後從 message 中擷取出 public key) 接著用ECDH 找出 shared key後進行訊息加密