總結破解 Curve25519 公鑰的核心數學問題
生成 Curve25519 私鑰非常容易：生成 32 個隨機字節的數據，然後執行以下操作：
e[0] &= 248 e[31] &= 127 e[31] |= 64然後，您可以通過對私鑰進行花哨的數學運算來生成公鑰。例如，這是我剛剛生成的隨機密鑰對：
public: e40ed268dff20db8497d0691421d00b086aad1efedcd5bd223d9eb6c0b85665f secret: e3c0e8b20ba7894882ddb37522dbe90867befcf9f31a5ce29c0d7997e0bd856d公鑰加密的整體安全性在於很難獲取公鑰並進行逆向操作。據我了解，橢圓曲線密碼學依賴於離散對數很難找到的事實。特別是，對於給定的大 b 和 g，很難找到一個整數 k 使得
$ b^k = g $
該方程與 Curve25519 有何關係？具體來說，如果我有一個像上面這樣的公鑰，我將如何用數學術語表達我需要解決的問題才能找到私鑰？它與我不時看到的方程式有什麼關係- $ y^2 = x^3+486662x^2+x $ , 和數 $ 2^{255} - 19 $ ?
我猜它不像上面等式中的“私鑰是k，公鑰是b和/或g”那麼簡單。我也有點困惑，因為鍵的位數似乎大致相同，這似乎意味著 k 的可行值並不多？
六字小結：橢圓曲線離散對數問題。
$ \newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}} $ 數學總結：給定 $ x(A) $ 和 $ x(P) $ 兩分 $ A $ 和 $ P $ 在橢圓曲線上 $ y^2 = x^3 + 486662 x^2 + x $ 在場上 $ \Z/(2^{255} - 19)\Z $ , 找一個整數 $ a $ 這樣 $ A = [a]P $ ， 在哪裡 $ [a]P $ 是曲線上的標量乘法。我們挑選 $ a $ （在你的符號中， $ k $ ) 均勻隨機地從 $ 2^{251} $ 可能性，以便從計算它的最佳算法 $ x([a]P) $ （在你的符號中， $ b^k $ ) 成本約為 $ 2^{125} $ 算術運算，比任何對手都希望執行的要多。
或者，更準確地說，我們依賴於計算橢圓曲線 Diffie-Hellman 問題：給定公鑰 $ x(A) $ , $ x(B) $ ， 和 $ x(P) $ ， 尋找 $ x([ab]P) $ 在哪裡 $ A = [a]P $ 和 $ B = [b]P $ . 但它似乎並不比 ECDLP 容易多少。
更詳細一點：
號碼 $ p = 2^{255} - 19 $ 是一個素數，所以每個整數都不是的倍數 $ p $ 有一個反模 $ p $ , 因此整數模 $ p $ 形成一個有限域 $ \F_p = \operatorname{GF}(p) = \Z/(2^{255} - 19)\Z $ . 定義橢圓曲線需要一個欄位。號碼 $ p $ 很方便，因為它在 $ 2^{256} $ 但下不了太多，而且很接近二的冪。因此：
- 每組模全等的整數 $ p $ 有一個代表可以寫成 256 位 = 32 字節（= 64 十六進制數字，正如您所注意到的）。事實上，它只需要 255 位，這會留下一個額外的位，用於對曲線點進行編碼。
- 減少一個整數 $ u \geq p $ 為整數 $ \overline{u} < p $ 符合 $ u $ 模組 $ p $ ，您可以利用以下事實 $ 2^{255} \equiv 19 \pmod p $ ， 因此，如果 $ u = 2^{255} u_\mathrm{hi} + u_\mathrm{lo} $ 為了 $ u_\mathrm{lo} < 2^{255} $ ， 然後 $ u \equiv 19 u_\mathrm{hi} + u_\mathrm{lo} \pmod p $ .
換句話說，您可以轉移 $ u $ 右乘 255 位，乘以 19，然後將其添加到低 255 位 $ u $ ; 那麼結果將與輸入的倍數不同 $ p $ ——無需計算一般整數除法，這讓加密工程師很高興，因為很難用秒錶將輸入值洩露給對手的快速整數除法。
查看Curve25519有兩種主要的等效方式。
Curve25519 的一種觀點是它是多項式所有根的集合$$ y^2 - x^3 - 486662 x^2 - x $$超過 $ \F_p $ ，每個點寫成仿射座標 $ (x, y) $ , 加上一個額外的點 $ \mathcal{O} $ 稱為在仿射座標中沒有表示的無窮遠點。
Curve25519 的另一種觀點是它是多項式的所有根線的集合$$ Y^2 Z - X^3 - 486662 X^2 Z - X Z^2 $$超過 $ \F_p $ ，每一行寫成齊次座標 $ (X : Y : Z) $ 為了 $ X, Y, Z $ 並非全為零，其中 $ (X : Y : Z) $ 表示與 $ (\lambda X : \lambda Y : \lambda Z) $ 對於任何非零 $ \lambda $ . 無窮遠點具有齊次座標 $ (0 : 1 : 0) $ ，因此不需要單獨處理，因為它在仿射座標中。具有仿射座標的任何其他點 $ (x, y) $ 可以寫成齊次座標 $ (x : y : 1) $ ，以及任何具有齊次座標的線 $ (X : Y : Z) $ 對於非零 $ Z $ 可以寫成仿射座標 $ (X/Z, Y/Z) $ .
Curve25519 的元素在加法的詳細定義下形成了一個組（總結在 Wikipedia 上，並且源自有助於證明費馬大定理的數學理論的悠久歷史，用於分解大整數的快速算法，以及夢想數學大統一理論）定義一個點 $ P + Q $ 給定點 $ P $ 和 $ Q $ 在 Curve25519 上，無窮遠點是一個恆等式，因此 $ P + \mathcal{O} = \mathcal{O} + P = P $ 對於每一點 $ P $ , 並且有一個逆 $ -P $ 和 $ P + -P = P - P = \mathcal{O} $ .
由此，我們可以定義標量乘法 $ [n]P $ 一點的 $ P $ 由一個整數 $ n $ 作為 $ [n]P = P + \dots + P $ ， 這 $ n $ - 倍加 $ P $ 對自身，它具有以下屬性 $ n = [nm]P = [mn]P = m $ 對於任何其他整數 $ m $ ， 在哪裡 $ nm = mn $ 是兩個整數的乘積。
對於任何給定的 $ x $ 座標，Curve25519 上最多有兩個可能的點 $ x $ 座標，對應二次多項式的兩個根 $ y^2 - x^3 - 486662 x^2 - x $ 在 $ y $ . 可能沒有這樣的 $ y \in \F_p $ ， 如果 $ x^3 + 486662 x^2 + x $ 是非平方的，或二次非殘差，模 $ p $ , 但我們可以增加 $ \F_p $ 帶有製造元素 $ \sqrt{2} $ 和所有正式條款 $ a + b\sqrt{2} $ 為了 $ a, b \in \F_p $ , 給出擴展欄位 $ \F_{p^2} $ 其中每個非零元素 $ \F_p $ 正好有兩個平方根。（如果你增加 $ \F_p $ 所有多項式都有根，你得到 $ \overline{\F_p} $ , 的代數閉包 $ \F_p $ , 代數幾何中的大多數橢圓曲線理論都是在代數閉域上發展起來的，例如 $ \overline{\F_p} $ 和 $ \mathbb{C} $ .) Curve25519 上的點，座標為 $ \F_{p^2} $ 被稱為 $ \F_{p^2} $ -有理點，並且對於每個 $ x \in \F_p $ 正好有兩個 $ \F_{p^2} $ - 有理點 $ x $ 協調。
事實證明，對於任何 $ \F_{p^2} $ -理性點 $ P $ ， 如果 $ x(P) \in \F_p $ 然後 $ x([n]P) \in \F_p $ 也適用於所有整數 $ n $ , 如果我們規定濫用符號 $ x(\mathcal{O}) = 0 $ . （這是Curve25519 論文的定理 2.1，省略了一些細節。）而這種特殊形式的曲線是蒙哥馬利曲線，與例如較短的 Weierstrass 曲線相反 $ y^2 = x^3 - a x + b $ 對於一些 $ a, b \in \F_p $ — 允許非常快速的算術計算 $ x([n]P) $ 給定 $ n $ 和 $ x(P) $ 僅使用 $ X $ 和 $ Z $ 座標，在恆定時間內獨立於值 $ n $ 和 $ x(P) $ 因此，可以從頭到尾計算計算時間的人對這些值一無所知。
X25519是由橢圓曲線 Diffie-Hellman 在一組 $ \F_p $ -Curve25519 的有理點。Alice 的私鑰是一個秘密整數 $ a $ 從均勻隨機選擇 $ 2^{251} $ 可能性。她的公鑰是 $ x $ 協調 $ \F_p $ 一點的 $ A = [a]P $ ， 在哪裡 $ P $ 是一個點 $ x(P) = 9 $ . 如果 Bob 的公鑰是 $ x(B) $ 出於某種原因 $ B = [b]P $ ，他們的共享秘密是$$ H(x([a]B)) = H(x([a][b]P)) = H(x([b][a]P)) = H(x([b]A)) $$如您所見，這可以由 Alice 或 Bob 從他們每個人已知的資訊中計算出來，其中 $ H $ 是一些標準的雜湊函式映射 $ \F_p $ 八位字節字元串。
（有關如何選擇的完整詳細資訊 $ a $ 以及如何將秘密標量和公鑰編碼為八位字節字元串，如果您想實現 X25519，請參閱Curve25519 論文或RFC 7748。請注意，在引入它時，名稱“Curve25519”僅表示 DH 功能。名稱已更改，因此“Curve25519”現在表示曲線，“X25519”是 DH 函式。扭曲 Edwards 形式的雙有理等效曲線，有時稱為 Ed25519 或鬆散地稱為扭曲 Edwards 形式的 Curve25519，現在也用於簽名。）
計算橢圓曲線 Diffie-Hellman 問題是要找到 $ x([ab]P) $ 給定元素 $ x([a]P) $ , $ x([b]P) $ ， 和 $ x(P) $ 的 $ \F_p $ . 最知名的方法都是通過橢圓曲線離散對數問題，即在給定兩個元素的情況下找到 $ x(P) $ 和 $ x(A) $ 的 $ \F_p $ , 一個整數 $ a $ 這樣 $ A = [a]P $ ——也就是說，找到一個標量乘法的秘密標量。
最好的通用方法，只知道如何計算組運算，是 Pollard 的 rho 和 kangaroo 算法，其成本約為 $ 2^{125} $ 組操作——可能比任何人計算的都要多。如果基點 $ P $ 有復合順序——也就是說，如果最小的整數 $ n $ 這樣 $ [n]P = \mathcal{O} $ 是複合的——那麼 Pohlig-Hellman 算法可以計算 $ a $ 更快地計算它以每個因子為模 $ P $ 獨立。但 $ P $ 有素數 $ p_1 = 2^{252} + 27742317777372353535851937790883648493 $ , 所以 Pohlig-Hellman 沒有幫助，就像它在有限域Diffie-Hellman 中對形式的安全素數沒有多大幫助一樣 $ 2q + 1 $ 為素數 $ q $ 或者，如果 FFDH 發生器具有素數順序。
在Lim-Lee 攻擊（適用於橢圓曲線群）中，如果攻擊者向 Alice 發送 $ x $ 點座標 $ Q $ 這不是的標量倍數 $ P $ ——甚至可能沒有 $ \F_p $ -理性點，但只是一個 $ \F_{p^2} $ -有理點——並且有小階 $ k $ , 那麼由於 $ [a]Q = [a \bmod k]Q $ ，通過檢查哪個 $ k $ 愛麗絲使用的可能派生的共享秘密，攻擊者了解一點 $ a $ ，即 $ a \bmod k $ . 但是唯一可能的點元素的小訂單 $ x $ 座標 $ \F_p $ 除以 8，愛麗絲總是選擇 $ a $ 以便 $ a \bmod 8 = 0 $ ——這就是（部分）開頭的比特旋轉。
數字 8 是Curve25519的輔因子，因為 $ \F_p $ -理性點有秩序 $ 8p_1 $ . 該組 $ \F_{p^2} $ - 有理點 $ x $ 座標 $ \F_p $ 和 $ y $ 座標不在_ $ \F_p $ 但在 $ \sqrt{2}\F_p $ ，稱為曲線的扭曲，有順序 $ 4p_2 $ 對於一個大素數 $ p_2 = 2^{253} - 5548463555474470707170387558176729699 $ . 沒有合法的公鑰在扭曲，但攻擊者可以輸入看起來像公鑰的東西。這是扭曲安全的主題，也是為什麼 $ \F_p $ 不是上述領域故事中的唯一演員。
橢圓曲線安全故事還有更多內容。進一步閱讀：
- SafeCurves的其他一切。
- 簡要介紹代數幾何及其計算的基礎知識：David Cox、John Little 和 Donal O’Shea，理想、多樣性和算法：計算代數幾何和交換代數簡介，第 3 版，Springer UTM， 2000. 國際標準書號：978-0-387-35650-1。
- 深入了解代數幾何：Robin Hartshorne，代數幾何，Springer GTM，1977。ISBN：0-387-90244-9。
- 對於橢圓曲線計算的具體主題：Joseph H. Silverman，橢圓曲線的算術，第 2 版，Springer GTM，2009。ISBN：978-0-387-09493-9。
- 有關 2006 年之前您需要了解的有關橢圓曲線密碼學的所有內容的全面調查：Roberto M. Avanzi、Henri Cohen、Christophe Doche、Gerhard Frey、Tanja Lange、Kim Nguyen 和 Frederik Vercauteren，橢圓和超橢圓曲線密碼學手冊, Chapman & Hall/CRC, 2006. ISBN: 978-1-58488-518-4。
它不是 $ b^k = g $ 因為 $ b $ 和 $ g $ 不是整數，而是橢圓曲線點。
所以保持你的符號你正在做的是 $ [k]B = G $ 在 Curve25519 上添加點，然後添加 $ B $ 對自己 $ k $ 次。在 Curve25519 上，這些點也僅用它們的 $ x $ 協調。因此，您的公鑰將是 Curve25519 點的 x 座標 $ G $ .