Elliptic-Curves

你能告訴我為什麼在有限域上對橢圓曲線上的一個點進行標量乘法會得到一個無窮大的點嗎?

  • December 21, 2021

我正在閱讀程式比特幣。作者說:

標量乘法的另一個性質是,在某個倍數處,我們到達無窮遠點(請記住,無窮遠點是加法恆等式或 $ 0 $ )。如果我們想像一個點 $ G $ 和標量乘法直到我們得到無窮大的點。

他沒有解釋為什麼。所以我不明白為什麼。如果可能的話,我希望你給我一個簡單的解釋,沒有嚴肅的數學證明。

橢圓曲線的點 $ E $ 在有限域上 $ K $ 正在形成一個有限交換加法群(有限阿貝爾群),以點加法為群運算。該組需要一個標識元素,通常表示為 $ \mathcal{O} $ . 在大多數曲線中,這是無窮遠點,也表示為 $ P_\infty $ . 在 Edwards 曲線中,恆等式是一個仿射點 $ (0,1) $ .

量乘法 $ [k]P $ 這實際上意味著添加 $ P $ 本身 $ k $ 次。更正式的;

讓 $ k \in \mathbb{N}\backslash{ 0} $

$$ \begin{align} [k]:& E \to E\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align} $$

並通過身份 $ [0]P = \mathcal{O} $ .

什麼時候 $ k< 0 $ 和 $ [k]P=-k $ 自從 $ [-1]P = -P $ .

積分數(捐贈者 $ #E(K) $ ) 在有限域上的橢圓曲線上是有限的,那麼如果你添加一個點 $ P $ 本身很多次最終你會得到身份 $ \mathcal{O} $ .

$$ \underbrace{P+P+\cdots+P}_{\text{$t$ times}} = [t]P= \mathcal{O} $$

最小的 $ t $ 將是該點生成的子組的順序 $ P $ . 為了安全起見,由於攻擊,我們希望這個訂單巨大而重要。如果我們考慮 Pollard 的預期攻擊成本 $ \rho $ 是 $ O(\sqrt{#E(K)}) $ ,即我們需要將點大小加倍(使用 256 位曲線來實現 128 位經典安全)。

比特幣使用具有特徵的主要治療方法Secp256k1 $ p $ 它被定義在素數域上 $ \mathbb{Z}_p $ 用曲線方程 $ y^2=x^3+7 $ .

命令 $ n $ 壓縮形式的基點

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

**注1:**一點 $ P $ 可能不會生成整個組,但它總是會生成一個循環子組。在素數曲線中(順序是素數),這意味著除了恆等元素之外的所有元素都是生成器。對於非素數曲線,必須檢查 $ [k]P \stackrel{?}= \mathcal O $ 在哪裡 $ k\mid #E(K) $ 找到順序 $ P $ 由拉格朗日關於群論的定理

**注 2:**正如 SqueamishOssifrage 所指出的,The Smart表明,如果曲線的順序和基場的順序 ( $ K $ )是相同的(即 $ #E(\mathbf{F}_q ) = q $ ) 那麼這條曲線上的離散對數以線性時間執行。這種曲線稱為異常曲線

secp256k1上下文中(包括比特幣),乘以一個點 $ P $ 曲線上的整數 $ k $ 通向無窮遠點 $ \mathcal O $ 當且僅當:

  • $ k $ 是組階的倍數 $ n $ ,包括當 $ k=0 $ . 這個 $ n $ 是secp256k1特性的一個大(素數)整數部分。這是曲線上的點數,包括無窮遠點。
  • 或點 $ P $ 是無窮遠點 $ \mathcal O $ . 這不能發生在 $ P $ 是發電機 $ G $ .

數學上: $ k\times P=\mathcal O\iff k\bmod n=0 $ 或者 $ P=\mathcal O $ .

一個很好的類比是模素數乘法 $ n $ : 乘以 $ k $ 產生零(模 $ n $ ) 什麼時候 $ k $ 是的倍數 $ n $ ,或者當我們乘以已經為零時(模 $ n $ )。類比更進一步:添加零的東西(模 $ n $ ) 什麼都不改變(取模 $ n $ ),這就是零的定義(模 $ n $ ); 很像在無窮遠處添加點 $ \mathcal O $ 到曲線上的任何一點都保持不變,這就是無窮遠點的定義。

更簡單的類比:在時鐘算法中,當我們重複添加目前時間(表示為整數小時),或者等效地將目前時間乘以越來越大的整數時,我們最終到達 12 點(即使我們沒有開始從 12 點開始,這可能發生在我們乘以 12 之前;那是因為 12 不是素數)。

請注意,當乘以 $ k $ 不是的倍數 $ n $ ,一些點乘算法可能仍然在內部遇到無窮遠點。例如當 $ k=8n-1 $ , 一些算法來計算 $ k\times P $ 可以計算為 $ 2\times\bigl(2\times\bigl(2\times\bigl(((k+1)/8)\times P\bigr)\bigr)\bigr),-,P $ . 這在數學上是正確的,但在計算中遇到了無窮大點 $ ((k+1)/8)\times P $ .

什麼時候 $ P $ 不在曲線上,將其乘以整數在數學上沒有定義,並且只能通過檢查如何嘗試乘法來說明會發生什麼。

一些點乘算法通過特殊情況在無窮遠處乘點來避免這兩個問題;驗證該點在曲線上;減少 $ k $ 模組 $ n $ , 然後是特殊情況 $ k=0 $ ; 並確保他們在內部操縱 $ j\times P $ 只有 $ |j|<n $ (也許偶數例外 $ j $ 和 $ |j|<2n $ ).

引用自:https://crypto.stackexchange.com/questions/68593