了解關於短 Weierstrass 曲線的 Twist Security

我試圖了解SafeCurves Twist 安全頁面的“針對梯子的無效曲線攻擊”部分，但我很難將其應用於較短的 Weierstrass 曲線。

該部分聲稱，為了阻止無效曲線攻擊，一種有效的技術是使用單個座標梯來計算標量乘法。然後該部分繼續描述曲折並明確​​提到蒙哥馬利曲線，特別是當它說“蒙哥馬利階梯公式 $ By^2=x^3+Ax^2+x $ 還計算扭曲曲線的標量乘法 $ (B/u)y^2=x^3+Ax^2+x $ ”。

現在，我明白這是一個問題，因為在 ECDH 期間，使用蒙哥馬利曲線上的單個座標梯實現，我可以提供曲線扭曲的公鑰，如果扭曲的順序是“弱”，則獲得另一個資訊對等方的私鑰。

但是，這適用於較短的 Weierstrass 曲線嗎？如果是這樣，如何？

據我了解，Weierstrass 曲線上的非平凡二次扭曲具有以下形式 $ y^2=x^3+c^2ax +c^3b $ 在哪裡 $ c $ 是一個非正方形 $ F_p $ . 所以扭曲修改了兩者 $ a $ 和 $ b $ 曲線的參數。為了使攻擊起作用，我假設需要有一個在兩條曲線（正常曲線和扭曲曲線）上都有效的標量乘法階梯。這個假設正確嗎？

對於較短的 Weierstrass 曲線，是否存在這樣的階梯？

據我所知 $ x $ - 座標只有Weierstrass使用的梯子 $ a $ 和 $ b $ 在計算中，例如Brier 和 Joye之一。這怎麼能在扭曲上起作用，因為它是不同的值 $ a $ 和 $ b $ ?

我問這個問題是因為如果不存在這樣的算法，那麼我看不到如何像 djb 在該頁面上所做的那樣將扭曲安全性度量應用於 NIST P-224 和 BrainpoolP256t1 等短 Weierstrass 曲線。

扭曲攻擊在Fouque 等人的論文中得到了最好的解釋。

而曲線的（二次）扭曲 $ E : y^2 = x^3 + ax + b \in \mathbb{F}p $ 確實是形式 $ E^t : y^2 = x^3 + d^2ax + d^3b \in \mathbb{F}{p} $ 對於非正方形 $ d $ , 你也可以把twist想成點的集合 $ (x, y) $ 在 $ E^2 : y^2 = x^3 + ax + b \in \mathbb{F}_{p^2} $ 在哪裡 $ x $ 僅在 $ \mathbb{F}p $ 但 $ y $ 或者是 $ 0 $ 或僅定義在 $ \mathbb{F}{p^2} $ （顯然，加上無窮大的點）。您可以從 $ E^2 $ 到 $ E^t $ 作為 $ (dx, d^{3/2}y) $ . 但你不必——你可以簡單地直接求解對數 $ E^2 $ .

這是一個Sage範例，它展示了對整數模上的 Weierstrass 曲線的扭曲攻擊 $ 2^{127}-1 $ :

# Setup fields
p  = 2^127-1
d  = -1 # non square in the field
K  = GF(p)
K2.<z> = GF(p^2)

# this curve has prime order, but a 2^44-smooth twist
a  = -3
b  = 2045
E  = EllipticCurve(K, [a, b])
Et = EllipticCurve(K, [d^2*a, d^3*b])
E2 = EllipticCurve(K2, [a, b])

# precompute orders
print (E.order().factor());
print (Et.order().factor());
print (E2.order().factor());

# generate a discrete logarithm to solve
s  = randint(0, E.order())
P  = E([0, 26743016104147931148362869907315104519])
Q  = s * P

# query target with an invalid point
# of order 207464639
P_ = E2.lift_x(K(randint(0, p)))
while P_.order() != Et.order():
 P_ = E2.lift_x(K(randint(0, p)))

P_ *= Et.order() // 207464639

Q_ = s * P_ # query -- pretend this is done with an x-only ladder

# solve the log directly on E2
x1 = P_[0]
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))

# map to Et (optional) and solve
x1  = d * P_[0]
x2  = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))

print (s % 207464639)
print (s_, -s_ % 207464639) # either one or the other
print (s__, -s__ % 207464639) # either one or the other

所以你可以看到沒有操縱 $ a $ 和 $ b $ 曲線參數：扭曲攻擊中唯一需要的就是發送一個 $ x $ - 座標 $ x^3 + ax + b $ 不是正方形 $ \mathbb{F}_p $ . 請注意，由於兩者 $ x $ , $ a $ ， 和 $ b $ 在 $ \mathbb{F}_p $ ， 一個 $ x $ - 只有梯子 $ E $ 也適用於定義的扭曲點 $ E^2 $ . 也許更容易理解它為什麼起作用的方法是重寫 $ y^2 = x^3 + d^2x + d^3b $ 作為 $ dy^2 = x^3 + ax + b $ .

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