Elliptic-curve cryptography ( ECC ) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields . ECC requires smaller keys compared to non-ECC cryptography (based on plain Galois fields ) to provide equivalent security
參考文章
[TOC]
數學上，橢圓曲線為壹代數曲線，形如
$$y^2 = x^3 + ax + b$$
並且該曲線無奇點(尖點或自相交)，判別式$\Delta = -16(4a 3+27b 2)$不為0.
在橢圓曲線中添加無窮遠點 O ,由於曲線關於y軸對稱，假設P為曲線上壹點，則P關於y軸的對稱點定義為-P。無窮遠點的對稱點為其自身，因此 O = -O
定義 + 運算，假設P，Q，-R在曲線上，則 P + Q = -R -> P + Q + R = O 其中-R與P，Q***線。
定義數乘 *
$$
nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}
$$
$$y^2 = x^3 + ax+ b \bmod{p}$$
下圖是曲線$y^2 = x^3 -7x+10\bmod{p}$，其中p為19，97，127，487時的點集。可看到點集關於y = p/2對稱。
定義直線$ax+bx+c \equiv 0 \bmod{p}$，既等間距的直線族。
若點集中P,Q,-R三點在同壹直線上，則 P+Q+R = O
$(9 9^{-1})\ mod\ 23 = 1 = (9 18)mod\ 23$
$P = (x_p,y_p)$
$Q = (x_q,y_q)$
$R = (x_r,y_r)$
$$P+Q = -R$$
公式
$$
x_r = (m^2-x_p-x_q) \bmod{p}
$$
$$
y_r = [y_p+m(x_r-x_p)]\bmod{p}
$$
若$P \neq Q $則$m = (y_p - y_q)(x_p-x_q)^{-1}\bmod{p}$
若$P = Q$則$m = (3x_p 2+a)(2y_p) {-1}\bmod{p}$
點集中點的數量稱為橢圓曲線的階數，有快速算法 Schoof's algorithm
$$nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}$$
例如曲線$y^2 \equiv x^3 + 2x + 3 \bmod{97}$的點$P = (3,6)$
通過上邊例子可以看出P與數乘，最終只有有限的循環出現的幾個結果$kP = (k\bmod{5})P$,這五點在加法運算下封閉。這五點構成了 循環子群 ，其中P稱為 generator or base point of the cyclic subgroup
Cyclic subgroups are the foundations of ECC and other cryptosystems.
the order of is the smallest positive integer $n$ such that $nP = 0$ . In fact, if you look at the previous example, our subgroup contained five points, and we had $5P = 0$.
The order of $P$ is linked to the order of the elliptic curve by Lagrange's theorem , which states that the order of a subgroup is a divisor of the order of the parent group .
In other words, if an elliptic curve contains $N$ points and one of its subgroups contains $n$ points, then $n$ is a divisor of $N$, so $N\ mod\ n \equiv 0$
For example, the curve $y^2 = x^3-x+3$ over the field $F_{37}$ has order $N = 42$ . Its subgroups may have order 1,2,3,6,7,14,21 and 42 . If we try $P = (2,3)$ can see that $1P\neq0,2P\neq0,3P\neq0,6P\neq0,7P=0,$ so the order of is 7.
對於ECC算法，我們希望子群階數足夠高。所以通常我們選擇壹條橢圓曲線，計算其階數，並選擇壹個較大的因子作為子群的階數，最終找到壹個基點。
在Lagrange's theorem中令$h =N/n$,稱$h$為 cofactor of the subgroup 余因子
由於$nP = 0$所以$h(nP) = 0 = n(hP)$
現在考慮$n$是素數,令$G =hP$,則生成壹個以$G$為基點的n階子群
現已知點PQ在橢圓曲線上，如何確定整數$k$使得$Q =kP$ ?這個問題被稱為橢圓曲線的離散對數問題，這個問題被認為是壹個困難的問題，目前還沒有多項式時間解決方法。
在密碼學中Digital Signature Algorithm (DSA), the Diffie-Hellman key exchange (D-H) and the ElGamal algorithm都與該問題有關。
ECC問題相比其它幾個問題更難以解決。
Our elliptic curve algorithms will work in a cyclic subgroup of an elliptic curve over a finite field.
得到算法六元組$(p,a,b,G,n,h)$
在前面提到離散對數問題非常困難，但也不是所有的都困難，有些類型的橢圓曲線就非常脆弱，有非常快速的方法解決，例如$p = hn$時就有多項式時間解決的方法。
怎樣保證曲線是安全的呢？
為了解決這個問題，我們需要再附加壹個參數 seed $S$，這是壹個隨機數湧來生成參數a和b，或者基點G再或者所有的參數。這些參數通過hash函數生成，hash容易計算但是難以逆推。
橢圓曲線的生成通過隨機數生成，這使得曲線足夠的隨機。
如果我們知道$d$和$G$,計算$H$非常容易。但是如果我們僅知道$H$和$G$,計算$d$將非常困難，因為這是離散對數問題。
ECDH是 Diffie-Hellman algorithm 的壹種變體，更像密鑰交換協商而不是加密。應用場景：雙方需要安全的交換信息，即使第三方攔截到也無法破譯。這是TSL背後的壹個原則。
$$S=d_AH_B=d_A(d_BG)=d_B(d_AG)=d_BH_A$$
Alice使用私鑰$d_A$簽名文件，Bob使用Alice的***鑰$H_A$來確認。
ECDSA作用在消息的hash上，而不是直接作用在消息上。Hash函數可以選擇密碼學安全的。hash需要被截斷為和子群階數$n$所占bit壹樣的長度，例如前邊n是256bit，那麽hash也需要是256bit，截斷後的hash定義為整數$z$
$(r,s)$ 就是簽名。
Alice對hash $z$ 使用私鑰 $d_A$ 和隨機數 $j$簽名。Bob使用Alice的***鑰 $H_A$驗證。
驗證簽名，驗證簽名需要Alice的***鑰 $H_A$ 截斷的hash $z$，以及簽名 $(r,s)$.
如果 $r=x_P\bmod{n}$則是合法的
$$
\begin{array}{rl}
P & = u_1 G + u_2 H_A \
& = u_1 G + u_2 d_A G \
& = (u_1 + u_2 d_A) G
\end{array}
$$
再帶入 $u_1,u_2$的定義
$$
\begin{array}{rl}
P & = (u_1 + u_2 d_A) G \
& = (s^{-1} z + s^{-1} r d_A) G \
& = s^{-1} (z + r d_A) G
\end{array}
$$
這裏省略了$mod\ n$，因為在子群階數為$n$,所以相當於自動對n取模。由$s = k^{-1} (z + rd_A) \bmod{n}$推出$k = s^{-1} (z + rd_A)\bmod{n}$.
$$
\begin{array}{rl}
P & = s^{-1} (z + r d_A) G \
& = k G
\end{array}
$$
這與簽名算法第二步生成的是同壹個點P，接下來驗證是否滿足生成算法第三步即可驗證簽名。
當使用ECDSA進行數字簽名時，k要相當飽滿。如果每次簽名都使用相同的k，或者k是可預測的，那麽就被找出私鑰。 This is the kind of mistake made by Sony a few years ago. ，PS3只能運行Sony使用ECDSA簽名過的程序，但問題是Sony使用了固定的k
這樣可以輕松的找出Sony的私鑰$d_S$，只要買兩份簽名的遊戲，取出他們的hash ($z_1 z_2$),和兩份簽名$(r_1,s_1),(r_2,s_2)$,以及橢圓參數。
$$
s = k^{-1}(z+rd_S)\bmod{n}\Rightarrow d_S = r^{-1}(sk-z)\bmod{n}
$$
我們認為離散對數問題是非常困難的，但是並沒有數學上的證明。目前解決離散對數問題由三種方法，假設$Q=xP$，求x
隨意假定$x=am+b$
$$
\begin{array}{rl}
Q & = xP \
Q & = (am + b) P \
Q & = am P + b P \
Q - am P & = b P
\end{array}
$$
選擇壹條標準曲線 prime192v1 ,$n$=0xffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831,$\sqrt{n} \approx 7.9\cdot10 {28}$，每個點需要32Byte存儲，大概總***需要$2.5\cdot10 {30}$byte，這比全世界存儲還多。而且 prime192v1 還是壹個低階曲線。
使用量子算法可讓復雜度降低$O((\log{n})^3)$
$y 2+xy=x 3+ax^2+1$ a為0或1，擁有$2^m$點，其中m為素數
$x 2+xy=x 3+x^2+b$ b是隨機生成的整數
這兩條曲線計算較快。