---
tags: 數讀
---
# 基礎橢圓曲線
> [name=W_Ice_Tri] [time=Mon, June 20, 2022] [color=#1f1e33]
## 概要
[TOC]
## 定義
域$k$上的橢圓曲線可看成此方程再加上一無窮遠點
> 不定方程$y^2=x^3+ax+b, \ a,b\in k^2$
> $\Delta=-16(4a^3+27b^2)\neq0$

($\Delta\neq0$為避免重根)
啊原因可能是這種方程長得跟計算橢圓周長的方程很像
其實根本無關

橢圓曲線與一平行y軸的線之交點必有無窮遠點，定義為$P_\infty$
## 基礎性質
顯然曲線是光滑的，這毋庸置疑

橢圓曲線上取兩點，而這兩點所形成的直線與曲線必有第三個交點
(由一元三次方程與韋達定理可知)
小心有一些case要注意：


如果我們有兩個點$P,Q$
做直線$PQ$交橢圓曲線於$R'$，記$R'$對$x$軸之對稱點$R$
則定義$P+Q=R$(這不是單純的加法喔)，且$P_\infty := 0$
順便定義$tP$為$P$的$t$倍點($tp=(t-1)p+p=p+p+p+...$)

左上：$A+B=C$
右上：$A+B=0$
左下：$A+A=B$
右下：$A+A=0$

這也是為什麼在前面要定義無窮遠點

另外，對於橢圓曲線與任一直線的三個交點$P,Q,R$
可推得$$P+Q+R=0$$注意到這個方程是對稱的，那麼就可以具體寫出$P+Q$的表達式

如果$P(x_p,y_p),Q(x_q,y_q),R(x_r,y_r)$
Case(1) : $P,Q$不重合
> $s=\dfrac{y_p-y_q}{x_p-x_q}$
>
> $x_r=s^2-x_p-x_q$
> $y_r=y_p+s(x_r-x_p)$

Case(2) : $P,Q$重合
> $s=\dfrac{3x_p^2-a}{2y_p}$
>
> $x_r=s^2-2x_p$
> $y_r=y_p+s(x_r-x_p)$

總而言之，橢圓曲線上有一個交換群結構，因此我們可以透過一個有理解生成新的有理解

與文章無關的例題們
例題1. 試證明$y^2=x^3-5$沒有正整數解
例題2. 試證明$y^2=x^3-1$只有整數解$(0,1)$
例題3. 試證明$x^4+y^4=z^4$沒有平凡整數解
例題4. 試求$y^2=x^3+6$的所有整數解
例題5. 試求$y^2=x^3-11$的所有整數解

## ECDSA加密

在運算方面數值大小一定得有限，所以考慮對整個橢圓曲線模質數$p$，那麼$P+Q+R=0$的運算也一樣模$p$，如果我們找的到一個點它可以生成出一個循環群，那麼就可以針對這個模$p$的橢圓曲線進行像是離散對數的加密。

所以我們的問題變成:給定一點$P$和另一點$T$，試求最小的$d$使得$dP=T$ (由循環群定義可知只需要求最小解，沒必要求所有解)

那麼大致說完加密的方式後，就來說明完整的加密解密過程。

1. 產生金鑰：選定$a$和$b$分別為橢圓曲線的係數(就是$y^2=x^3+ax+b$中的$a$與$b$)，$p$為質數，拿來模剛給定的橢圓曲線。再找一個循環群($G,·$)與其生成元$P$，若$G$的order為$q$，取一數$d$, $0<d<q$，算出$T=dP$

所以我們得到:公鑰：$(p,a,b,q,P,T)$，私鑰：$d$

2. 簽章：任取一數$e$，滿足$0<e<q$。計算$R=eP$，令$r=R$的$X$座標，並計算$s\equiv(h(x)+dr)e^{-1} \pmod q$，其中$h(x)$是雜湊(hash)函式。

所以我們得到:要傳送的訊息$x$與簽名$(R,s)$

3. 驗章：計算$w\equiv s^{-1}\pmod q$、$u\equiv wh(x) \pmod q$、$v\equiv wr\pmod q$、$A=uP+vT$，若$A$的$X$座標$\equiv r\pmod q$，則該簽章為合法的簽章，若不為$r$則該簽章不合法。

首先產生公私鑰的時候已經將公鑰$(p,a,b,q,P,T)$送出。

接下來的簽章是給一段文字$x$以及簽名$(R,s)$。

最後是驗證$(R,s)$確認訊息$x$是否是由原始發送公鑰的人所傳遞的。

最後的驗章證明:

易知$uP=\dfrac{h(x)eP}{h(x)+dr}$，$vT=\dfrac{erdP}{h(x)+dr}$，故$$A=uP+vT=\dfrac{e(h(x)+rd)P}{h(x)+dr}=eP=R$$

以上是橢圓加密簽章的過程與原理。

整體來說，其實完全了解橢圓曲線上的運算規則後，就可以看出加密背後離散對數加密的樣子，不過單純離散對數的加密其實計算上複雜度蠻高的，而橢圓曲線與模的概念套用下來就明顯降低許多複雜度。
## RSA,ECDSA比較
優點:
$RSA$:較易實踐，原理與加密過程簡單
$ECDSA$:計算速度快，而且不需要太長的$p$就會有很高的加密效果

缺點:
$RSA$:隨著$p,q$越大，解密計算時間就會相對$ECDSA$會花很多時間。
$ECDSA$:原理很難，牽涉到群論等內容，而且實作部分也較$RSA$複雜很多。