Elliptic-Curves

用外行的話來說,橢圓曲線公式對變化有多敏感?

  • March 20, 2022

以最近的問題(例如#25519)中的曲線為例:-

$$ y^2 = x^3 + 486662x^2 + x $$ 它被認為是“安全的”。將其略微修改為:-

$$ y^2 = x^3 + 486664x^2 + x $$ 我試圖讓外行的感覺來理解這意味著什麼。比如,現在是完全失效了,根本不能用,很容易壞,還是稍微好壞一點?或者這個微小的變化是否突然允許特定的攻擊發揮作用?

**極其敏感。**實際上,只有另外三個正值不會違反各種安全保證,而您提供的範例不在其中。即使在這三個中,也只有一個被選中的可以保護所有邊緣情況。現在,更詳細一點…

Curve25519 是蒙哥馬利曲線,形式為 $ y^2 = x^3 + Ax^2 + x $ 出於效率原因。為了曲線是安全的,一個足夠的 $ A $ 必須選擇。三種可能的選擇 $ A $ 根據介紹曲線的論文中提出的定義,這將是安全的 $ 358990 $ , $ 464586 $ , 和 $ 486662 $ . 前兩個的質因數小於 $ 2^{252} $ ,這是在給定密鑰與素數匹配的極不可能的情況下的問題。伯恩斯坦沒有修改曲線的安全定義並限制密鑰的選擇,而是選擇了 $ A = 486662 $ 為簡單起見。

如果你去一個完全不同的 $ A $ ,那麼各種不可預知的事情就可能發生。各種安全保證可能會被破壞,許多重要的性能特性將付諸東流。的選擇 $ A $ 必須有曲線和扭曲順序 $ {4 \cdot \mathrm{prime}, 8 \cdot \mathrm{prime} } $ 以避免Curve25519 論文第 3 節中指定的一些攻擊。您提出的特定更改與這些標準不匹配,因此可能會應用任意數量的攻擊。這確實是答案的癥結所在。一旦違反了安全約束,任何事情都可能發生。

引用自:https://crypto.stackexchange.com/questions/61990