libsodium x25519 和 Ed25519 小訂單檢查
研究 x25519 和 Ed25519 的 libsodium 實現，我看到它執行一個小訂單檢查，將給定的輸入與硬編碼的值黑名單進行比較。這個列表是詳盡的還是目前已知無效點的列表？
原始碼：
簡短的回答：除非您正在設計一個奇特的協議，否則您無需擔心黑名單或點驗證。
中等答案：
這取決於你想要做什麼。有一個簡短的黑名單和一組更大的點（太大而無法列出）可能會給您帶來麻煩 - 但前提是您通過使用不尋常的新穎協議中的原語並期望來自不尋常的安全屬性來設置自己的麻煩他們。
“黑名單”點的順序低：每個點 $ P $ 具有數量很少的性質 $ n $ , 在這種情況下總是 8 的除數, 這樣 $ [n]P = \mathcal O $ . 因此，每個點最多只有 8 個不同的標量倍數。
這顯著減少了某人使用其私有秘密標量計算“共享秘密”的可能共享秘密值的數量 $ n $ 和惡意對等方的“公鑰” $ P $ ，幾乎或完全否定了秘密標量的貢獻 $ n $ 其中有 $ 2^{251} $ 可能性。沒有一個低階點實際上是有效的公鑰：標準基點 $ B = (9, \dots) $ 不生成它們。
在明智的協議中，您通常根本不需要擔心以下幾點：
- 在互動式密鑰協議中，(a) 惡意對等方通常超出範圍，(b) 應通過驗證記錄來檢測 MITM，以及 (c) 您對密鑰交換的整個記錄進行雜湊處理，包括共享密鑰和倒霉的 sap 的公鑰 $ [n]B $ 為後續對話生成會話密鑰。
- 在簽名系統中，您依賴於已知公鑰下的驗證；給出“黑名單”點之一的惡意簽名者超出範圍。簽名中的黑名單點無法欺騙驗證者——如果可以的話，簽名方案將被嚴重破壞。
有關驗證的更多詳細資訊，請參閱Trevor Perrin 關於此類協議中的點驗證的文章。
任何其他屬性，您必須非常小心，例如公鑰或簽名的唯一性——而這裡的黑名單是不夠的。為什麼對於一些需要晦澀安全屬性的晦澀應用程序來說，黑名單還不夠？如果 $ P $ 是一個低階點，並且 $ n $ 是合法使用者的秘密標量，那麼對於任意點 $ Q $ 由基點生成 $ B $ , $ [n](P + Q) = [n]Q $ . 發生這種情況是因為每個合法的秘密標量都是 8 的倍數，即輔因子，因此湮滅 $ P $ ，即 $ [8]P = \mathcal O $ 是身份。去年，在Trevor Perrin 隨意評論解釋了這一點之後，這種需要新安全屬性的新協議的不謹慎設計讓Monero 徹底陷入了困境。
長答案：
X25519 和 Ed25519 工作的組具有一些重要的結構，這使得所謂的“無效點”相關。我將專注於 X25519。
每個組都有一個身份元素，我們稱之為 $ \mathcal O $ . 每一個元素 $ P $ 一個有限群的（加法寫法）有一個有限階 $ n = \operatorname{ord}(P) $ ，將其添加到自身的最小正數 $ P + \cdots + P = [n]P $ 產生身份 $ \mathcal O $ . 身份的順序是1；所有其他點的階數都大於 1。
X25519 工作在素數領域 $ \mathbb F_p $ 在哪裡 $ p = 2^{255} - 19 $ ，也稱為 $ \mathbb Z/(2^{255} - 19)\mathbb Z $ . 具體來說，它適用於 $ x $ 曲線上點的座標
$$ E/\mathbb F_p \colon y^2 = x^3 + 486662 x^2 + x. $$ 每個曲線點 $ P $ 除了身份 $ \mathcal O $ 有一個 $ x $ 座標，我們稱之為 $ x(P) $ . 我們另外定義 $ x_0(P) = x(P) $ 什麼時候 $ P \ne \mathcal O $ ， 和 $ x_0(\mathcal O) = 0 $ . 事實證明，如果 $ P \in E(\mathbb F_{p^2}) $ 有 $ x_0(P) \in \mathbb F_p $ , 那麼對於每個整數 $ n $ , $ x_0([n]P) \in \mathbb F_p $ ，並且每個 $ P $ 同 $ x_0(P) $ 有相同的 $ x_0([n]P) $ . 也就是說，標量乘法保持 $ x $ 基場座標 $ \mathbb F_p $ 而不是在擴展欄位中，並且 $ x $ 標量倍數的座標 $ [n]P $ 是由唯一定義的 $ x $ 基點座標 $ P $ . 這是Curve25519 論文的定理 2.1 。
你不需要了解所有的細節——只要明白這一點就足夠了，因為我們只處理元素的編碼 $ \mathbb F_p $ ，我們唯一需要擔心的就是組中的那些 $ E(\mathbb F_{p^2}) $ 和 $ x $ 協調 $ \mathbb F_p $ . （我們為什麼要擔心 $ \mathbb F_{p^2} $ 完全是一個二次擴展 $ \mathbb F_p $ 將虛構的平方根添加到非平方元素 $ \mathbb F_p $ ? 有一些 $ x $ 座標 $ x^3 + 486662 x^2 + x $ 是非正方形的，所以沒有對應的 $ y $ 協調 $ \mathbb F_p $ ，但有一個在 $ \mathbb F_{p^2} $ .)
群組 $ E(\mathbb F_p) $ 的 $ \mathbb F_p $ -有理點，或大致座標在 $ \mathbb F_p $ 而不是擴展域（更準確地說，自同構群的分量作用的不動點 $ \overline{\mathbb F_p} $ 修復 $ \mathbb F_p $ ; 這個定義也適用於投影座標），有 $ 8 p_1 $ 元素，其中 $ p_1 = 2^{252} + 2774231777737235353585193779088364849 $ 是素數，而 8 稱為輔因子。根據群論的標准定理，每個元素的階 $ E(\mathbb F_p) $ 劃分 $ 8 p_1 $ . 這意味著每一個元素 $ E(\mathbb F_p) $ 有八種可能的順序之一： $ {1, 2, 4, 8, p_1, 2p_1, 4p_1, 8p_1} $ .
扭曲群，它是 的子群 $ E(\mathbb F_{p^2}) $ 和 $ x $ 座標 $ \mathbb F_p $ 和 $ y $ 座標不在_ $ \mathbb F_p $ ， 有 $ 4 p_2 $ 元素，其中 $ p_2 = 2^{253} - 5548463555474470707170387558176729699 $ 也是素數。這是我們通常不使用的組（該組中除了身份之外沒有標準基點的倍數），但大約有一半可能 $ x $ X25519 可以處理的座標將解碼為。因此，扭曲群中每個元素的階數除以 $ 4 p_2 $ ，因此僅有的八個可能的順序是 $ {1, 2, 4, p_2, 2p_2, 4p_2} $ .
合法的 X25519 使用者選擇形式的公鑰 $ x_0([8a]P) $ ， 在哪裡 $ P $ 是質數階的標準基點 $ p_1 $ ，並共享表單的秘密 $ x_0([8a]B) $ ， 在哪裡 $ x_0(B) $ 是他們對等點的公鑰。因子 8 表示公鑰 $ x_0(B + Q) $ 為了一點 $ Q $ 8 階（也稱為 8-torsion 元素）產生與公鑰相同的共享秘密 $ x_0(B) $ ， 因為 $ [8a](B + Q) = [8a]B + [8a]Q = [8a]B + [a][8]Q = [8a]B + [a]\mathcal O = [8a]B $ . 惡意對等體可以選擇這樣的 $ B + Q $ , 它是按位不同的 $ B $ 但總是產生相同的共享秘密。惡意對等方可以選擇 $ B $ 不屬於形式 $ [8b]P $ 根本不是一個低階點，這會將可能的共享秘密的數量減少到 1、2、4 或 8 個。 例如，他們可以選擇 $ \mathcal O $ ; 那麼“共享秘密”將是 $ x_0(\mathcal O) = 0 $ ——這就是零檢查的來源。
黑名單是將零作為“共享秘密”的所有點的列表。它沒有列出所有非法公鑰——有太多無法列出，形式為 $ B + Q $ 在哪裡 $ B $ 是合法的公鑰（其中有 $ p_1 $ 可能性）和 $ Q $ 在黑名單上。檢測合法公鑰的唯一方法是確認 $ [p_1]B = \mathcal O $ .
但是對於大多數協議來說，通過替換非法公鑰可能引起麻煩的威脅模型是無關緊要的，因為同一個攻擊者，同一個惡意對等體，無論如何都可能以各種其他方式造成麻煩。例如，在 DNSCurve 中，這可能是 X25519 使用靜態-靜態 DH 密鑰協議的原始應用程序，惡意名稱伺服器或使用者使用非法公鑰可能導致的唯一問題是將網路上的對等方的秘密洩露給竊聽者——無論如何他們都可以做到。