密碼學/橢圓曲線

橢圓曲線密碼學是一種依賴於稱為“橢圓曲線”和“有限域”的數學結構的密碼學。橢圓曲線是形如 $y^{2}=x^{3}+ax+b$ 的關係，其中 $a$ 和 $b$ 是曲線的預設引數，而 $x$ 和 $y$ 是座標。任何滿足該關係的 $(x,y)$ 對都被認為是橢圓曲線上的點。在橢圓曲線點上，可以定義一個稱為“加法”的操作，如下所示

要新增兩個點 $P$ 和 $Q$ ，透過它們畫一條線，找到該線穿過曲線的第三個點；稱之為 $R$ 。如果 $P$ 和 $Q$ 具有相同的 x 座標，則連線它們的線將是垂直的，並且 R 將不存在，因此在這種情況下，我們將 $P+Q$ 稱為“無窮遠點”。無窮遠點加到任何其他點都是該點本身，因此可以將無窮遠點視為數字零的橢圓曲線點類似物。否則，從 $R$ 處畫一條垂直線到曲線另一側的相同 x 座標上的點。該點定義為 $P+Q$ 。要計算 $P+P$ ，而是取曲線在 $P$ 處的切線，將其延伸到 $R$ ，並取垂直對面的點作為答案，就像在 $P+Q$ 案例中一樣。

由於橢圓曲線是數學函式，我們可以使用高中代數和微積分的工具來推匯出 $P+Q$ 和 $P+P$ 的公式。對於 $P+Q$ ，公式為

$m={\frac {P_{y}-Q_{y}}{P_{x}-Q_{x}}}$

$(P+Q)_{x}=m^{2}-P_{x}-Q_{x}$

$(P+Q)_{y}=P_{y}+m(R_{x}-P_{x})$

對於 P+P

$m={\frac {3P_{x}^{2}+a}{2P_{y}}}$
$(P+P)_{x}=m^{2}-2*P_{x}$

$(P+P)_{y}=P_{y}+m(R_{x}-P_{x})$

請注意，兩種情況下演算法都是相同的：首先我們在 $P$ 處找到斜率，然後我們得到答案的 x 座標，然後我們使用斜率-點公式得到 y 座標。然而，從這些公式中，我們得到一個非常令人驚訝的結果： $(A+B)+C=A+(B+C)$ ，無論 $A$ ， $B$ 和 $C$ 是否不同或相同。此外，從視覺定義中可以明顯看出 $A+B=B+A$ 。這些事實表明橢圓曲線點形成了一個被稱為_阿貝爾群_的結構——支援加法，因此透過擴充套件支援整數的乘法。例如， $4A=(A+A)+(A+A)=(A+(A+A))+A=(A+(A+(A+A)))$ 。

將橢圓曲線點乘以非常大的數字也很容易。您可能會認為將一個點乘以十億需要將其自身加十億次，但實際上有一個更簡單的演算法。

  define multiply(P, k) {
    if (k == 0) return point_at_infinity()
    if (k == 1) return P;
    if (k % 2 == 0) return double(multiply(P,k/2))
    if (k % 2 == 1) return add(P,double(multiply(P,(k-1)/2)))
  }

基本上，該演算法不是將原始點多次重複加到零，而是重複使用加倍，在每一步都將問題的大小減半。例如，對於 $k=83$ ，該演算法擴充套件為

 83p
 add(p,double(41p))
 add(p,double(add(p,double(20p))))
 add(p,double(add(p,double(double(10p)))))
 add(p,double(add(p,double(double(double(5p))))))
 add(p,double(add(p,double(double(double(add(p,double(2p))))))))
 add(p,double(add(p,double(double(double(add(p,double(double(p)))))))))

對於 $k=1000000000$ ，該演算法只需三十步。這使得我們可以將橢圓曲線數字乘以極大的數字——實際上，這些數字大到宇宙中沒有足夠的原子來計數它們。

有限域

現在，我們進入橢圓曲線數學中更有趣的部分。不久前，數學家發現，我們今天使用的加法、減法、乘法和除法的形式並不是唯一數學上一致的形式。實際上，還有許多其他結構，有些使用數字，有些使用更復雜的形式（例如多項式），我們可以以特殊的方式定義基本運算，並且仍然擁有一個有效的代數系統。最常見的是“模算術”。模加法和模乘法就像普通的加法和乘法一樣，只是在計算完成後，您將結果除以一個預設值（稱為“模數”），只取餘數。例如，在模 7 中

$3+6=9\equiv 2{\pmod {7}}$

以及

$5*4=20\equiv 6{\pmod {7}}$

減法類似，只是如果結果變為負數，則新增模數以使其再次變為正數。因此

$1-2=-1\equiv 6{\pmod {7}}$

除法實現起來比較複雜，但可以透過乘法來定義 - 也就是說， $a/b{\pmod {7}}$ 定義為一個數字 $c$ ，滿足 $bc\equiv a{\pmod {7}}$ 。可以證明，當且僅當模數為素數時，所有模除法都有答案，並且沒有模除法有多個可能的答案。因此，我們通常只關心“素數域”。

那麼這種怪異的算術有什麼用呢？基本上，它非常適合對橢圓曲線進行運算。無論你加減多少次點，結果的座標始終是範圍在 $[0...p-1]$ 內的整數，其中 $p$ 是模數。“迴圈”屬性也使結構在密碼學上安全；給定一個普通的橢圓曲線，給定兩個點 $G$ 和 $Q=k*G$ ，你可以透過檢視輸出的大小，並利用這些資訊縮小可能的範圍來計算 $k$ 的值。對於素數域上的橢圓曲線，所有點看起來都差不多；它們都是範圍在 $[0...p-1]$ 內的數字，分佈大致均勻。這個問題的難度，即給定 $G$ 和 $k*G$ 計算 $k$ ，實際上是橢圓曲線密碼學安全性的基礎。

在橢圓曲線中最著名的兩種演算法是橢圓曲線Diffie–Hellman協議和橢圓曲線數字簽名演算法，分別用於加密和簽名訊息。

密碼學 圖書中的此頁面或部分是殘缺的。你可以透過擴充套件它來幫助華夏公益教科書。