Elliptic-Curves
發現未使用 KDF 的 Ed25519 128 位私鑰
如果存在一個均勻隨機的 128 位私鑰標量 $ x $ , 對應的公鑰 $ X=xG $ （在哪裡 $ G $ 是一個眾所周知的基點），發現有多難 $ x $ 從 $ X $ ?
我知道正常方法是使用 KDF 在基點的組大小範圍內派生私鑰（大約 $ 2^{252} $ ）。但是，這是用於有特定原因直接使用 128 位私鑰的承諾方案中。
另請注意，這不是關於偽造簽名難度的問題，而是特別限於發現 $ x $ .
這種計算似乎在目前的能力範圍之內。最著名的方法是使用Pollard 袋鼠方法的變體，其中 $ O(\sqrt {|I|}) $ 橢圓曲線組運算用於 $ I $ 是其中的區間 $ x $ 謊言。這大概意味著 $ 2^{64} $ 針對您的問題進行分組操作。64 位的天真工作說明在現代電腦的能力範圍內感覺很好，但是這裡每個工作單元都涉及到 255 位數字的幾個多精度乘法，這是不平凡的貢獻，可能會增加另外 10-20 位工作取決於組的實現方式和乘法的實現方式。
在實踐中，最接近的結果是Zieniewicz 和 Pons的結果，他們在 2020 年從 112 位大小的區間恢復了 sec256k1 上的離散對數。他們在 256 個 NVIDIA GPU 上花了 13 天時間。您的問題大約要困難 8 位（Ed25519 上的組操作比 sec256k1 上的成本略低，但不會產生重大影響）。幸運的是，Pollard 的袋鼠是高度可並行化的。要是我們
- （有問題）假設過去兩年摩爾定律有 1 位改進
- 購買 4 倍的 GPU
- 讓他們執行 1 年多一點
那麼你的問題應該是可以解決的。