比特幣中的 Shor 算法和 ECDSA - 為什麼知道基點後仍然難以找到私鑰？
我正在學習 Shor 的算法以及如何應用它來破解 ECDSA。我顯然在這裡錯過了一些基本的東西——我以為我理解 ECDSA 提出的挑戰是在給定公鑰的情況下找到私鑰，如下所示：
$ x\cdot P = X $ （在哪裡 $ x $ 是隨機生成的大私鑰， $ P $ 是 secp256k1 基點，並且 $ X $ 是公鑰）。
Since we know the base point for secp256k1, given in xy-coords as (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424), why is this still a difficult problem that only Shor’s algorithm could solve and not simply a division problem?
讓您感到困惑的是您考慮了標量乘法（在您的符號中 $ x\cdot P $ ) 作為有限域上的**乘法。**實際上;
橢圓曲線上的標量乘法 $ [x]P $ 實際上意味著添加 $ P $ 本身 $ x $ 次。這就是如何計算一個公共點，從一個私鑰，前者是曲線上的一個點，後者是一個整數。更正式的；
讓 $ x \in \mathbb{N}\backslash{ 0} $
$$ \begin{align} [x]:& E \to E\ &P\mapsto [x]P=\underbrace{P+P+\cdots+P}_{\text{$x$ times}}.\end{align} $$
這裡 $ P+P =[2]P;(=2\cdot P) $ 表示點加法，並具有從切弦規則派生的特殊公式。通過這個點加法，對於定義在有限域上的曲線，這些點形成一個有限阿貝爾群，並且通過標量乘法，我們有 $ Z $ -模組。
當我們談到給定的 $ [x]P $ 和 $ P $ 發現 $ x $ 是橢圓曲線上的**離散對數問題。**在某些曲線上，這很容易，但是，在 secp256k1 上，這並不容易，經典攻擊的成本為 $ \mathcal{O}(\sqrt{n} $ ） 儘管 $ n = order(P) $ 與波拉德的 Rho。最佳實現的攻擊使用了Pollard 袋鼠算法的並行版本 $ 2^{114} $ 間隔。
Shor 算法（如果曾經針對實際尺寸實施並且所有問題都已解決）可以在多項式時間內求解離散對數。可以在此處找到對攻擊的估計
- 2017 年Roetteler 等人計算橢圓曲線離散對數的量子資源估計。
其實不需要 $ y $ 協調進攻。最多可以有兩個 $ y $ 給定的值 $ x $ 只要 $ x $ 是滿足曲線方程的點的座標。
另一方面，標準 ECDSA存在一些其他實際問題，而不是 Pollard 的 Rho 和 Shor 的周期查找算法。
重複隨機數：私鑰立即洩露。
隨機數生成器的偏差，格攻擊揭示了關鍵。即使是微小的偏差；
- 2020 LadderLeak：以不到一點的 Nonce 洩漏打破 ECDSA，Aranha 等人。
短隨機，是的，存在於比特幣中；
- 2019 -有偏見的隨機數感知：針對加密貨幣中弱 ECDSA 簽名的格攻擊Breitner 和 Heninger2
我們有一個更好的替代方案，由 Thomas Pornin 和比特幣等開始使用的確定性 ECDSA 。