0

我有一个 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 做到这一点?有没有更有效的方法来计算这个?

如果这不是问这个问题的正确地方,我真诚地道歉。感谢您的任何帮助。

4

2 回答 2

0

你不会炸你的电脑。

运行可能需要很长时间,但看起来这是一个直接的 O(n) 问题,所以它不会炸到无穷大。只要不花费大量时间来检查一个哈希是否有效,这甚至可能需要不到一分钟的时间来运行。现代机器以 gHz 为单位测量时钟周期。那是每秒 10^9 个周期。此外,由于您说您无法从错误的猜测中推断出正确答案是什么,因此蛮力似乎是唯一的解决方案。

于 2019-04-09T13:09:41.873 回答
0

我是gmpy2维护者。

要计算 C**d mod n,您应该使用内置pow()函数并指定所有三个值。pow(C,d,n)会比 快得多C**d % n

使用gmpy2应该很容易。无需使用int()将字符串转换为 Python 整数,您只需使用gmpy2.mpz(). 您可以pow()mpz实例一起使用。(如果 to 的三个值之一pow()mpz,gmpy2将用于计算。)

我估计运行时间gmpy2从不到一个小时到几个小时不等。Python 的原生整数可能会慢 10 倍。

于 2019-04-10T06:37:10.910 回答