比特幣的優化模乘逆（secp256k1）
我已經為 OpenCL 編寫了一個暴力攻擊比特幣地址的應用程序。它實現了一個簡單的窮舉搜尋，從公鑰 G（私鑰 1）和點增量（G 的加法）開始得到下一個密鑰。
它可以工作，但它的性能比使用GMP的 CPU 實現慢一個數量級（相同的點增量算法，但使用 GMP 常式而不是自定義常式）。在 GMP 實施中，散列是瓶頸。在 OpenCL 實現中，點增量是瓶頸。
我的點增量實現通過二進制擴展 GCD 使用模乘逆（應用密碼學手冊的算法 14.61）。它比使用
mpz_invert().我需要的是針對曲線secp256k1優化的優化點增量（用 G 加點） 。這是一個教育項目，所以我對該主題的了解有限。我不知道是否有一種方法可以在不使用模乘逆的情況下完成它，或者是否有一種方法可以為我的特定應用程序加快計算速度。
我看到並實現（由 Segher Boessenkool）使用具有預先計算值的模冪運算，但沒有關於如何為其他曲線獲取這些值的資訊。我未能複制 GMP 實施。它的原始碼非常龐大，一堆混合優化的 C 和彙編程式碼讓我無法理解。
要求：
- G 實現的快速加點。
- 由於它的使用，安全性無關緊要。
- 如果可能，針對曲線 secp256k1 進行優化。
- 如果可能，請盡可能多地進行預計算。
問題：
在我的特定情況下，如何提高橢圓曲線點加法的速度？
評論註釋：
- 在每個 OpenCL 核心中搜尋是順序的，但考慮到整個程序是並行的。我的工作量經過實驗優化，接近僅執行 SHA-256 的理論 GPU FLOPS，因此瓶頸不在於 OpenCL 的使用，而在於橢圓曲線密碼學的算法實現。
- 我所說的性能小一個數量級是在 CPU 上測量的，而不是在 GPU 上測量的。我用自己的模乘逆運算得到大約 30 kKeys/s，使用 GMP 得到大約 200 kKeys/s（筆記型電腦）。在 GPU 上，我得到大約 2 MKeys/s。僅計算未優化的 SHA-256+RIPEMD-160 雜湊，不加點，我得到大約 1 GHashes/s (AMD Radeon RX 580)。
- 主程序使用標量乘法計算公鑰數組。它可以偽隨機或等間距計算它們。這個數組被提供給 OpenCL 核心，每個實例計算
RIPEMD160(SHA256(P)) == TARGET,RIPEMD160(SHA256(P+G)) == TARGET,RIPEMD160(SHA256(P+2G)) == TARGET, … 目前，只有一個目標地址。- OpenCL 不是這裡的問題。CPU 分析表明 90% 的時間都在計算模乘逆。與 GMP 相同的算法
mpz_invert()僅使用 25% 的時間來執行相同的步驟，而將剩餘時間用於雜湊計算。
半擴展二進制 GCD
當給定正整數時，問題中提到的 HAC算法 14.61的擴展二進制 GCD $ x $ 和 $ y $ , 計算整數 $ a $ , $ b $ , $ v $ 和 $ ax+by=v=\gcd(x,y) $ . 什麼時候 $ v=1 $ ， 它遵循 $ a $ 是乘法的逆 $ x $ .
在我們的上下文中， $ 0<x<y $ , $ y $ 奇怪的， $ \gcd(x,y)=1 $ （最後兩個條件滿足 $ y $ 是 $ p=2^{256}-2^{32}-977 $ secp256k1 的 $ v=1 $ ，這是素數）；因此 $ a $ 總是相反的。重要的是，我們不需要 $ b $ ，這允許簡化。這導致了半擴展二進制 GCD，我希望它可以在一定程度上有所幫助：
- 如果 $ x $ 那麼奇怪 $ u\gets x $ ; 別的 $ u\gets x+y $ ;
- $ v\gets y $ ; $ a\gets0 $ ; $ d\gets 1 $ ; $$ or $d\gets y-1$ in unsigned variant, see note $$
- 儘管 $ v\ne1 $
$$ invariant here and at start of the next while loop: $u$ and $v$ are odd and distinct $$
儘管 $ v<u $
$ u\gets u-v $ ; $ d\gets d-a $ ; $$ or $d\gets d+a$ in unsigned variant, see note $$
儘管 $ u $ 是偶數（至少一次）
- 如果 $ d $ 那麼奇怪 $ d\gets d+y $ ;
- $ u\gets u/2 $ ; $ d\gets d/2 $ ;
$ v\gets v-u $ ; $ a\gets a-d $ ; $$ or $a\gets a+d$ in unsigned variant, see note $$
儘管 $ v $ 是偶數（至少一次）
- 如果 $ a $ 那麼奇怪 $ a\gets a+y $ ;
- $ v\gets v/2 $ ; $ a\gets a/2 $ ;
- $ a\gets a\bmod y $ ; 這是所需的逆。
注：如圖所示， $ a $ 和 $ d $ 已簽署。在無符號變體中，我們可以通過記錄三個更改來保持它們為非負數。
如圖所示， $ a $ 和 $ d $ 可以增長到幾倍 $ y $ （帶符號變數的絕對值）。我們可以為此付出一些額外的努力。我推測沒有證據 $ \max(|a|,|d|)<4y\log_2(y) $ （或者 $ \max(a,d)<8y\log_2(y) $ 對於無符號變體）。或者，我們可以改變 $ a\gets a+y $ 進入 $ a\gets a-y $ 什麼時候 $ a\ge0 $ 對於已簽名的變體（對於未簽名的變體，可以是 $ a\ge y’ $ 為了一些方便 $ y’\ge y $ ，例如 $ y=2^{256} $ ); 和同樣的 $ d\gets d-y $ . 這足以確保一切都保持在以下 $ 4y’ $ ， 或者 $ 2^{258} $ 在上下文中。
可能的優化：次數 $ i $ 那個“雖然 $ u $ 是偶數”循環的執行可以從低位預測 $ u $ ，我們可以對整體效果進行分組 $ u $ 和 $ d $ 成一個循環。需要添加什麼 $ d $ 取決於 $ i $ ， 這 $ i $ 的低位 $ d $ ， 和 $ y $ . 它可以預先計算，因為 $ y $ 是固定的。即使我們這樣做是為了 $ i $ 最多 2 或 3 個（然後在必要時進行迭代），這可以顯著節省（至少在經典 CPU 上）。相同的 $ v $ 和 $ a $ .
（半）擴展歐幾里得算法（見這個答案）也計算乘法逆，並有一個簡單的變體避免乘法（商是2的冪）。它可以具有競爭力。兩者可以混合使用。
GPU 最適合 SIMD 工作負載
GPU 在相同指令流適用於並行啟動的不同獨立作業的工作負載上大放異彩。在同時啟動的作業中採用不同的程式碼路徑最多會顯著降低性能。因此，GPU 友好的算法是那些沒有測試的長序列的算法，並且可以預見的測試在不同的工作中大多采用相同的路徑。算法通常需要為此進行調整。
$$ hopefully more to come there $$
這是蠻力攻擊
攻擊需要大約 $ 2^{b-1} $ 點加法查找私鑰 $ b $ 未知位，或大約 $ 256-b $ 已知位（例如為零）。除了故意之外，我認為沒有理由應該有這樣的鑰匙。因此，我懷疑這件事的整體有用性。我們仍然可以出於教育目的考慮它。
從使用笛卡爾座標的地址開始
因為攻擊的一個版本被稱為是雜湊綁定的，所以我們知道攻擊試圖從相應公鑰的雜湊（稱為地址）中找到私鑰，而不是從公鑰中。這已在其他答案的評論中得到證實，該答案提出了一種假設公鑰已知的數學技術。我不是在探索那條路。
因此，算法的大部分順序版本是計算公鑰 $ kG $ 用於增量私鑰 $ k $ 使用點加法 $ G $ 從一個公鑰轉移到另一個；散列得到的公鑰（本質上）在其笛卡爾未壓縮 $ X|Y $ 形式; 並檢查雜湊。
攻擊應該是多目標的
同時定位多個地址有巨大的潛在好處；只有最終散列的比較稍微增加了計算密集度（它變成了目標地址之間的搜尋），其餘的都是共享的。這太好了，不容忽視。
GPU的外循環（很好）
在為 GPU 或其他高度並行架構優化算法時，必須將任務拆分為獨立的作業。那部分問題讓我認為它沒有完成：
從公鑰 G（私鑰 1）和點增量（G 的加法）開始搜尋以獲得下一個密鑰
使用這種算法，整體搜尋速度不會隨著 GPU 功率的增加而擴大：點增量無論多麼優化都將成為瓶頸。
但現在的問題也有：
主程序使用標量乘法計算公鑰數組。
這表明*“從公鑰 G（私鑰 1）開始”*不適用於 OpenCL 作業/核心。相反，將私鑰搜尋間隔細分，計算相應的公鑰，然後執行搜尋；沒關係。
實際上，如果您計算橢圓曲線點的原因是將它們與目標點進行比較，則不需要計算乘法逆。相反，如果您保持點在投影座標中進行迭代 $ H = (H_x, H_y, H_z $ ) 和標準座標中的目標值 $ T = (T_x, T_y) $ , 你可以確定是否 $ H = \pm T $ 只需檢查是否 $ H_x = T_x H_z $ （實際上，如果你保持 $ H $ 在雅各比座標系中，這是 $ H_x = T_x H_z^2 $ 反而）。由於使用投影座標進行計算的額外成本小於進行模逆計算的成本，因此這是一個勝利。