有没有可能通过10^8种可能性来确定正确答案？

Question

我有一个615位数的数字。在这本书中，有8处数字缺失。我得找出数字是什么。有10^8种可能性。你知道吗

这是一个RSA问题。有问题的数字是私钥，我正试图找出它是什么。为了帮助我，我有一个公钥对（n，e），两个都是615位数字长，还有一个明文和相应的密文。你知道吗

所以找出d的唯一方法就是用力。我试图在python中使用gmpy2来解决这个问题。我得克服重重困难才能使它发挥作用。我甚至不知道我做得对不对。我不得不下载Python2.7，这样我就可以运行gmpy2安装程序而不会得到错误消息。但我想现在可以了，因为我可以打字了

>>>import gmpy2

在终端，它不会给我一个错误。你知道吗

在我尝试循环10^8种可能性之前，考虑到我的情况，我想知道是否有可能在相对较短的时间内这样做。我不想炒我的电脑或冻结它试图计算这个。我还想知道我是否为此使用了正确的工具，或者gmpy2不是正确的版本，或者Python2.7不够好/快。我正在笔记本电脑上运行Python2.7上的gmpy2。你知道吗

最后，我想我要把所有的10^8个答案加起来，使C^d=M mod n，这是一个（已经）很大的数，等于615位数的幂，10^8倍。这可能吗？如果是，我如何使用gmpy2实现这一点？有没有更有效的方法来计算这个？你知道吗

我真诚的道歉，如果这不是正确的地方问这个问题。谢谢你的帮助。你知道吗

Answer 1

你不会毁了你的电脑。

它可能需要很长时间才能运行，但这似乎是一个直O（n）问题，所以它不会爆炸到无穷大。只要检查一个哈希值是否有效不需要太多的时间，这甚至可能需要不到一分钟的时间来运行。现代机器以千兆赫为单位测量时钟周期。也就是每秒10^9个循环。而且，既然你说你不能从错误的猜测中推断出正确的答案，暴力似乎是唯一的解决办法。你知道吗

Answer 2

我是维护者。你知道吗

要计算C**d mod n，应该使用内置的pow()并指定所有三个值。pow(C,d,n)将比C**d % n快得多。你知道吗

使用gmpy2应该很容易做到这一点。与使用int()将字符串转换为Python整数不同，您只需要使用gmpy2.mpz()。您可以将pow()与mpz实例一起使用。（如果pow()的三个值中有一个是mpz，则gmpy2将用于计算。）

我用gmpy2估计运行时间从不到一个小时到几个小时不等。Python的本机整数可能慢10倍。你知道吗