在有限域上的橢圓曲線上生成隨機點

為了應用一些 ECC 算法，我編寫了一個橢圓曲線的實現。然而，在大多數情況下，Alice 需要在給定曲線上選擇一個點 P。選擇這樣一個點的一般程序是什麼？

舉一個小例子，例如 $ y^2 = x^3 + x + 1 $ 超過 $ F_{25} $ ，有沒有一種算法可以在曲線上生成一個隨機點？在我的實現中，該欄位上的點由多項式表示，如果相關的話。

有沒有一種算法可以在曲線上生成一個隨機點？

通過擁有像/dev/urandom您這樣的良好隨機源可以生成隨機點 $ R $ 至少通過兩種方法在曲線上；

1. 通過使用隨機標量和標量乘法

2. 選擇生成點 $ P $ 在曲線上

3. 獲取之間的隨機整數 $ 0 < k < \text{Order of the Group} $

4. 計算 $ R =[k]P $ 通過標量乘法，最好通過雙加算法執行。

5. 在曲線方程上使用帶有樣本拒絕的隨機元素。

6. 選擇一個隨機元素 $ x \in \mathbb{Z_{25}} $ .

7. 檢查方程 $ y^2 = x^3 + x + 1 $ 有一個解，即它是一個二次餘數。

如果沒有解決方案返回 1. 步驟（拒絕樣品）

否則，我們有兩種解決方案， $ y $ 和 $ -y $ （或一個 $ y=-y $ ）。這些值可以使用Tonelli-Shank 算法及其推廣找到。 3. 現在使用隨機源進行選擇 $ \bar{y} $ 作為 $ y $ 或者 $ -y $ ，或擲硬幣。 4. 將曲線上的隨機點形成為 $ R=(x,\bar{y}) $請注意，如果沒有一些技巧，則無法用仿射座標表示無窮遠點。因此，此方法無法返回無窮遠點。如果在隨機選擇中也需要無窮遠點，則可以使用初始隨機選擇它。在裡面選擇它 $ \frac{1}{\text{Order of The Group}} $ 可能性。然後使用上面的。 3. 如果您使用的是 SageMath，那麼它有一個功能

random_element()解釋如下

返回此橢圓曲線上的一個隨機點，在所有有理點中均勻選擇。

SageMathrandom_element()函式使用 2. 方法，另外還可以返回無窮遠點， $ \mathcal{O} $

在我的實現中，該欄位上的點由多項式表示，如果相關的話。

這 $ \mathbb{F}_{25} $ 是一個擴展域，通常用多項式表示來表示域的元素，這對操作非常有利。因此，點的座標具有多項式表示。

來自OP的評論

我用Sage計算了每個點的順序：（sagecell.sagemath.org/…），可以看出即使組的基數是32，最大的順序是16。只是選擇EC的問題嗎？具有主要基數？

SageMath 結構不正確；

E = EllipticCurve(GF(25, 'x'),1, 1)提供這條曲線 $ y^2 = x^3 + x + 2 $ 不是 $ y^2 = x^3 + x + 1 $

可以如下構造；

   E = EllipticCurve(GF(25, 'x'), [1, 1])
   print(E)
   print(E.abelian_group())
   print ( E.cardinality())
   for i in E.points():
       print (i.order())

該結構EllipticCurve(Finite Field,[a,b])適用於標準的 Weierstrass，來自 $ y^2 = x^3+ a x + b $ 在哪裡 $ a,b \in F $ 其中定義的曲線。您只需要提供 $ a,b $ ， 和 $ F $ . 通常表示為的點集 $ E_{a,b}(F) $

該abelian_group()功能列印此橢圓曲線上點組的阿貝爾組結構。結果是

$$ \mathbb{Z_3} \oplus \mathbb{Z_9} $$

不應為一大群人呼叫此函式。這背後有一個理論，這可以在諸如華盛頓的書之類的書中找到，但是，參考可以追溯到 JWS Cassels, 1966, Diophantine Equations with Special Reference To Elliptic Curves

**定理：**讓 $ E $ 有限域上的 ben 橢圓曲線群 $ \mathbb{F_q} $ . 然後$$ E(\mathbb{F_q}) \simeq \mathbb{Z_n} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}} $$對於某個整數 $ n \geq 1 $ ，或者對於一些整數 $ n_1,n_2 \geq 1 $ 和 $ n_1|n_2 $ .

引用自：https://crypto.stackexchange.com/questions/68601