secp256k1/r1上模幂的改进算法
我知道模指数(r = b^e \bmod m)对RSA很重要，我可以找到一些算法，如果e以二进制形式表示(对于exp：)--以这样的方式表示n位长e，则可以预期~1.5n圈乘模运算。
我正在为ECC创建一个公开密钥恢复方法，比如secp256k1/r1。在secp256k1库中有一个非常有效的实现，但这是用ASM代码编写的--很难理解。但至少我知道第一步--您需要从ry中恢复rx (即签名的r)。从ry^2获得rx非常容易，但是接下来我需要做平方根模块--它可以转换为域上的幂模，即e= (p+1)/4.。
好吧，那么现在的问题是：
- 是否有比通常的模幂法更好的算法来计算(r = b^e \bmod m)？
- 或者，是否有专门针对secp256k1的快捷算法，我根本不需要运行模块幂运算，并且仍然能够从rx恢复ry？
回答 1
Cryptography用户
发布于 2021-10-06 06:33:36
在这个问题的密码体制中，模乘是不可替代的。有些语言，如Python，使这很容易为教育目的，只有。
在RSA和DSA中，以及在secp256k1或secp256r1上较小程度的ECC密码中，需要计算大e的b^e\bmod m。最快的算法(例如滑动窗指数)可以执行\log_2 e模平方运算和类似于\approx0.2\,\log_2 e模乘运算。然而，从对侧信道的安全性的角度来看，还有其他一些代价更高的算法(例如蒙哥马利梯子)可能更好。
每一个模乘或平方模m，对于上述或(在ECC中)点加法或由标量乘法，在使用小学学习的算法以适应计算机单词而不是数字时，其计算成本最多与(\log m)^2一样增长。这可以降低为(\log m)^{\approx1.6}与卡拉特赛或(\log m)^{\approx1.5}与Toom-3，但在ECC的模数m不够大，它支付了很多(m是一个‘只有’约数百位在ECC，而不是几千在RSA/DSA)。
为了教育目的，从零开始使用secp256k1或secp256r1开发签名或加密时，通常有以下几个阶段：
- 通过在模乘的基础上构建笛卡尔坐标下的点加法和倍频，然后点乘，然后签名或/和加密，得到一些有用的东西。
- 通过更好地表示点，例如投影坐标(这允许在点乘法结束前消除代价高昂的模反转)，使它能够更快地工作。
- 让它安全地工作，这是非常困难的，通常需要重写从地面到地面的许多东西。
- 性能优化。这在任何阶段都可以尝试，但深思一句：“过早优化是万恶之源”。
一些关于模乘和幂运算的在线参考文献(不是ECC)：
https://crypto.stackexchange.com/questions/95438
复制相似问题
腾讯云开发者
