在 secp256k1/r1 上進行模冪運算的更好算法
我知道模冪（ $ r = b^e \bmod m $ ) 對 RSA 很重要，我可以找到一些算法，如果 e 以二進制形式表示（對於 exp: ）——對於 n 位長 e，可以預期 ~1.5n 輪乘模運算。
我正在為像 secp256k1/r1 這樣的 ECC 制定公鑰恢復方法。secp256k1 庫中有一個非常有效的實現，但它是用 ASM 程式碼編碼的——很難理解。但至少我知道第一步——你需要恢復 $ ry $ 來自 $ rx $ （即簽名的 r）。很容易得到 $ ry^2 $ 從 $ rx $ ，但接下來我需要做平方根模——可以在現場轉換為冪模，即 $ e= (p+1)/4. $
好的，所以現在的問題是：
- 除了通常的模冪運算之外，還有更好的算法來計算 ( $ r = b^e \bmod m $ )?
- 或者，是否有任何專門針對 secp256k1 的捷徑算法，我根本不需要執行模冪運算並且仍然能夠恢復 $ ry $ 從 $ rx $ ?
問題的密碼系統中沒有模乘法的替代品。某些語言（例如 Python）使教育目的變得容易，只有.
在 RSA 和 DSA 中，以及secp256k1或secp256r1上的較小程度的 ECC 加密中，需要計算 $ b^e\bmod m $ 對於大 $ e $ . 最快的算法（例如滑動視窗求冪）執行大約 $ \log_2 e $ 模平方等 $ \approx0.2,\log_2 e $ 模乘法。然而，從安全性的角度來看，還有其他算法成本稍高（例如蒙哥馬利梯子），可能更好。
每個模乘或平方模 $ m $ ，對於上述或（在 ECC 中）點加法或標量乘法，計算成本最多增長 $ (\log m)^2 $ 使用小學時學習的算法適應電腦單詞而不是數字時。這可以降低到 $ (\log m)^{\approx1.6} $ 與Karatsuba或 $ (\log m)^{\approx1.5} $ 使用Toom-3，但在 ECC 中是模數 $ m $ 不夠大，支付的費用不夠多（ $ m $ 是 ECC 中的“僅”幾百位，而不是 RSA/DSA 中的幾千位）。
出於教育目的使用secp256k1或secp256r1從頭開發簽名或加密時，通常有以下幾個階段：
- 通過在模乘之上建構點加法和在笛卡爾座標中加倍，然後是點乘法，然後是簽名或/和加密，得到一些有用的東西。
- 通過使用更好的點表示來使其工作得更快，例如投影座標（這允許將昂貴的模反演推遲到點乘法結束）
- 讓它安全地工作，這非常困難，通常需要從頭開始重寫很多東西。
- 性能優化。這些可以在任何階段進行嘗試，但請思考“過早的優化是萬惡之源”的說法。
一些關於模乘和取冪（不是 ECC）的線上參考資料：