-1為二次餘數時橢圓曲線二次扭曲的無效點攻擊

我正在使用 Short Weierstrass 曲線複製對 ECC 的無效點攻擊。為此，我編寫了一個“愚蠢”的實現，它在進入標量乘法之前不驗證點是否在曲線上。對於攻擊的大綱，我大量借鑒了 Samuel Neves 的出色描述，他在這裡給出了：Understanding Twist Security with short Weierstrass curve

我可以在沒有任何問題的情況下複製它 $ d = -1 $ 是二次非殘差 $ \mathbb{F}_p $ ，然後一切都可以開箱即用。然而，當 $ p $ 是這樣的 $ -1 $ 是二次殘差，因此我需要為 $ d $ ，一切都崩潰了。

為簡單起見，在第一次執行中，我沒有使用曲線 $ \mathbb{F}_{p^2} $ 因為對於小 $ p $ 窮舉查找低階點不是問題。

例如，假設我的曲線定義為 $ \mathbb{F}_{101} $ ; 這裡， $ -1 $ 是二次餘數模 $ p $ ， 自從 $ 10 \cdot 10 = -1 \mod 101 $ . 我的曲線由

$ E: y^2 = x^3 + 13x + 29 $

與 $ d = 2 $ , 二次非殘差 mod 101,

$ E^d: y^2 = x^3 + 52x + 30 $

的順序 $ E^d $ 是 $ 111 = 3 \cdot 37 $ . 我選擇了兩點 $ E^d $ 分別有 3 和 37 個訂單：

$ P_1 = (28, 62) $

$ P_2 = (8, 7) $

當我通過沒有點驗證的標量乘法執行這些值時（對於私鑰 $ d = 58 $ ，我得到以下輸出：

$ S_1 = (94, 53) $

$ S_2 = (32, 14) $

兩者都不 $ S_1 $ 也不 $ S_2 $ 是二次扭曲上的一個點 $ E^d $ . 我可以提升任意一個 X 座標 $ E^d $ ，但是點的順序是錯誤的。

這是我的範常式式碼：

Fp = GF(101)
D = Fp(2)
   
print(D, "is square?", D.is_square())
(a, b) = (13, 29)

E = EllipticCurve(Fp, [a, b])
Et = EllipticCurve(Fp, [ a*D^2, b*D^3 ])

print("Et.order()", factor(Et.order()))

attack_points = [
   Et(28, 62),
   Et(8, 7),
]
print(E)
print(Et)
for P in attack_points:
   print(P, P.order())

# private key d = 58
mul_results = [ 
   Et(94, 53), 
   Et(32, 14), 
]
#print(Et.lift_x(94).order())
#print(Et.lift_x(32).order())

哪個輸出：

2 is square? False
Et.order() 3 * 37
Elliptic Curve defined by y^2 = x^3 + 13*x + 29 over Finite Field of size 101
Elliptic Curve defined by y^2 = x^3 + 52*x + 30 over Finite Field of size 101
(28 : 62 : 1) 3
(8 : 7 : 1) 37
TypeError: Coordinates [94, 53, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 52*x + 30 over Finite Field of size 101

我怎樣才能在二次扭曲中執行這種攻擊 $ d \neq -1 $ ?

這不是 d 不是 -1 的 QNR 的問題。

相反，這是一個小模量的問題。我可以使用 Samuel Neves 的修改腳本可靠地證明這一點：無效點攻擊會為低階點產生錯誤的結果

這根本沒有回答為什麼它不起作用，但至少這表明 $ d \neq -1 $ 不是我的問題的根本原因。

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