RSA 计算 c^d mod n
在RSA加密算法中，当c和d都是大数时，如何计算c^d mod n？
In the RSA Encryption Algorithm, how would one calculate c^d mod n when c and d are large numbers?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
GMP 是一个 C/C++ 软件库，可以为您执行此操作：文档中的 mpz_powm、mpz_powm_ui。使用的方法（很大程度上）在维基百科页面中进行了解释，您可以尝试阅读源代码对于 GMP，如果您愿意的话...
GMP is a C/C++ software library that does this for you: mpz_powm, mpz_powm_ui in the documentation. The method used is (largely) explained in the wikipedia page and you could try to read the source code for GMP, if you feel up to that...
简单的答案是：使用一种语言和/或库来实现“大整数”算术并包含适当的模幂函数。在 Java 中，这意味着使用
java.lang.BigInteger，特别是方法modPow()。由于底层计算机不能真正处理“整数”，而是对其进行有限的模拟（例如“32位整数”，其行为类似于整数，除了第32位以上的高位被丢弃），因此这种“大整数”实现必须应用一些特定的算法， 应用密码学手册（第 14 章）中对此进行了详细描述。
The easy answer is: use a language and/or library which implements arithmetics on "big integers" and includes an appropriate function for modular exponentiation. In Java, this means using
java.lang.BigInteger, specifically the methodmodPow().Since the underlying computers cannot really handle "integers" but a limited emulation thereof (e.g. "32-bit integers" which behave like integers except that upper bits beyond the 32nd are discarded), such "big integer" implementations must apply some specific algorithms, which are described in full detail in the Handbook of Applied Cryptography (chapter 14).
“powMod”操作可以分解为更小的步骤。
例如
5 ^ 3 % 6等于((5 * 5) % 6) * 5 % 6且5 ^ 4 % 6为等于(((5 * 5) % 6) * 5 % 6) * 5 % 6)。正如您所看到的，您可以在指数的子结果中应用模运算，以始终使用较小的数字，从而使计算c ^ d % n更容易，即使 c 和 d 的值很高。欲了解更多信息：
http://en.wikipedia.org/wiki/Modular_exponentiation
The "powMod" operation can be taken down into smaller step.
For example
5 ^ 3 % 6is equal((5 * 5) % 6) * 5 % 6and5 ^ 4 % 6is equal to(((5 * 5) % 6) * 5 % 6) * 5 % 6). As you can see you can apply the modulo operation in the sub result of the exponent to always work with smaller number and thus make it easier to calculatec ^ d % neven when c and d are high value.For more information :
http://en.wikipedia.org/wiki/Modular_exponentiation