是否可以計算 secp256k1 公鑰的模逆？
我知道不可能使用擴展的歐幾里得算法，因為它需要能夠劃分公鑰併計算餘數。我想知道是否還有其他方法可以計算橢圓曲線上某個點的模乘逆（如 secp256k1）？或者也許是證明不可能的原因？當公鑰乘以該整數時，有沒有辦法（除了蠻力）找到一個結果為 1 的整數？
我在數學或密碼學方面沒有受過特別好的教育，但我覺得它很有趣，所以也許我只是不知道自己研究它的正確術語。
當公鑰乘以該整數時，有沒有辦法（除了蠻力）找到一個結果為 1 的整數？
實際上，給定一個公鑰H $ H $ ，很容易找到最小整數x > 0 $ x > 0 $ 使得xH = 1 $ xH = 1 $ 。對於 secp256k1（如果H $ H $ 不是中性元素），則x = 115792089237316195423570985008687907852837564279074904382605163141518161494337 $ x = 115792089237316195423570985008687907852837564279074904382605163141518161494337 $ 。無論H $ H $ 是哪一點，這都是正確的；該曲線上的所有點（中性元素除外）都具有該順序。
但是，如果我們提到“模逆”，這並不是我們通常所說的意思。這聽起來更像是“給定xG $ xG $ ，找到點x^{-1}G $ x^{-1}G $ ”，這相當於 CDH 問題（我們希望這很難）
這是一個有點擴展的答案；
我想知道是否還有其他方法可以計算橢圓曲線上某個點的模乘逆（如 secp256k1）？或者也許是證明不可能的原因？
比特幣社區通常將通常的標量乘法稱為乘法1。我們將標量乘法定義為
[k]G : = \underbrace{G + G + \cdots + G}{k-times}$$ [k]G : = \underbrace{G + G + \cdots + G}{k-times} $$換句話說，添加一個點本身k $ k $ 次。
已經為此定義了一個問題（使用EC版本r $ r $ 是基本元素G $ G $ 的階，曲線是素數階，E(K) $ E(K) $ 是曲線點的集合）；
定義；
- CDH：給定一個三元組(G,[a]G,[b]) $ (G,[a]G,[b]) $ 找到[ab]G $ [ab]G $ 。
- Inverse-DH : 給定一對(G, [a]G) \in E(K) - {\mathcal{O}} $ (G, [a]G) \in E(K) - {\mathcal{O}} $ 元素在E(K)中的素數階r $ r $ 來計算[a^{-1 }]G。 $ E(K) $ $ [a^{-1}]G $
- Square-DH：計算問題 Square-DH 是：給定(G, [a]G ) $ (G, [a]G ) $ 其中G \in E(K) $ G \in E(K) $ 具有素數階r $ r $ 來計算[a^2]G $ [a^2]G $ 。
減少；
- \text{Inverse-DH} \leq_R \text{CDH} $ \text{Inverse-DH} \leq_R \text{CDH} $ 。
假設我們有一個可以解決\text{CDH}的oracle O。 $ O $ 我們得到(G,[a]G)作為\text{Inverse-DH}實例，我們想要找到P = [a]G。那麼我們有G = [a^{-1}]P = [a^{-1}a]G = G $ \text{CDH} $ $ (G,[a]G) $ $ \text{Inverse-DH} $ $ P = [a]G $ $$ G = [a^{-1}]P = [a^{-1}a]G = G $$
現在，用O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P)呼叫 oracle O $ O $ 並且 oracle 輸出[a^{-2 }]P。替換P得到[a^{-2}]P = [a^{-2}a]G = [a^{-1}]G這顯示了減少。 $ O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P) $ $ [a^{-2}]P $ $ P $ $$ [a^{-2}]P = [a^{-2}a]G = [a^{-1}]G $$
- \text{Square-DH} \leq_R \text{Inverse-DH} $ \text{Square-DH} \leq_R \text{Inverse-DH} $ 。
讓我們假設O是一個解決 $ O $ \text{Inverse-DH} $ \text{Inverse-DH} $ 的預言機，並讓(G, P = [a]G ) $ (G, P = [a]G ) $ 給出。如果P = \mathcal{O} $ P = \mathcal{O} $ 則返回\mathcal{O} $ \mathcal{O} $ 否則O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P。$$ O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P. $$這顯示了減少。
所以我們有\text{Square-DH} \leq_R \text{Inverse-DH} \leq_R \text{CDH} $ \text{Square-DH} \leq_R \text{Inverse-DH} \leq_R \text{CDH} $ 。如果我們可以證明\text{CDH} \leq_R \text{Square-DH} $ \text{CDH} \leq_R \text{Square-DH} $ 那麼我們將有等價性。
- \text{CDH} \leq_R \text{Square-DH} $ \text{CDH} \leq_R \text{Square-DH} $
讓O $ O $ 成為解決\text{Square-DH} $ \text{Square-DH} $ 的預言機，並且給定(G,[a]G, [b]G) $ (G,[a]G, [b]G) $ 作為\text{CDH} $ \text{CDH} $ 實例。
- 用O(G,[a]G)和O(G,[b]G)呼叫O $ O $ 兩次，分別得到P= [a^2]G和Q= [b^2]G。 $ O(G,[a]G) $ $ O(G,[b]G) $ $ P= [a^2]G $ $ Q= [b^2]G $
- 現在再呼叫O(G, P+Q) = O(G, [a+b]G) $ O(G, P+Q) = O(G, [a+b]G) $ 並得到R = [(a+b)^2]G = [a^2+2ab+b^2] G。$$ R = [(a+b)^2]G = [a^2+2ab+b^2]G. $$
- 現在最終計算[2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ab]G$$ [2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ab]G $$這顯示了減少。
因此我們有等價物。因此，如果\text{CDH} $ \text{CDH} $ 很難，那麼\text{Inverse-DH} $ \text{Inverse-DH} $ 也很難。好吧，我們希望這適用於非量子對手。
當公鑰乘以該整數時，有沒有辦法（除了蠻力）找到一個結果為 1 的整數？
我可以通過兩種方式閱讀它；
- 1 $ 1 $ 是我們寫為\mathcal{O} $ \mathcal{O} $ 的曲線的恆等式，那麼對於 r階素數曲線的每個元素，我們都有恆等式[ r ]P = \mathcal{O} $ [r]P = \mathcal{O} $ 。這是群論中元素階的定義。 $ r $
- 1 $ 1 $ 作為[a\cdot a^{-1}]G = [\color{red}{1}]G = G $ [a\cdot a^{-1}]G = [\color{red}{1}]G = G $ 那麼這就是我們討論的\text{Inverse-DH} 。 $ \text{Inverse-DH} $
1好吧，可以（定義|稱）點加法為點乘法，但是，加法是歷史性的，所有主要的橢圓曲線書都使用點加法；在復數上，任何橢圓曲線都可以實現 為一些格\Gamma的\mathbb C/\ $ \mathbb C/\Gamma $ Gamma 。在這種情況下，加法只是來自複數的標準加法。 $ \Gamma $