仅从公钥中破解长RSA密钥

Question

在一场比赛中，我试图学习如何在只有公钥的情况下破解RSA密钥：

• e=65537
• n=632459103267572196107100983820469021721602147490918660274601

所以我关注了这个网页和这个答案。尝试过：

>>> n = 632459103267572196107100983820469021721602147490918660274601
>>> import math
>>> math.floor(math.sqrt(n))
795272974058324394239265341440
>>> c = math.floor(math.sqrt(n))
>>> for i in range(c-1,c-41,-2):
...     if c%i ==0:
...         print(i, c%i)
...

但它没有给我任何东西。我已经开始了一种蛮力方法：

>>> print(repr(math.sqrt(n)))
7.952729740583244e+29
>>> c = math.sqrt(n)
>>> int(c)
795272974058324394239265341440
>>> for i in range(c-1, 2, -2):
...     if n%i == 0:
...         print(i, n%i)
...

但它已经运行了半天。我知道这很愚蠢，因为我测试的甚至不是素数。有更明智的方法吗？

一开始我用c开头，这是一个偶数。我想从偶数开始按第2步递减是愚蠢的，因为它只会让我测试非因子分解器？

更新

在阅读了丹的评论后，我现在正在努力寻找一个小因素，而不是从大因素开始。

>>> for i in range(1,c-1,2):
...     if c%i ==0 and i%2 != 0 and i%5 !=0:
...         print(i, c%i)
...
1 0

Answer 1

TL；DR：破解长RSA密钥在计算上很困难(即，没有在多项式时间内运行的已知解决方案(，虽然你的算法可能不是最有效的，但还没有人找到可以破解长RSA密码的算法(使用经典计算机-量子计算机的Shor算法可以在多项式时间破解长RSA钥匙(。

---

更长的答案：

为了估计程序执行所需的时间，我编写了以下python：

import time
n = 632459103267572196107100983820469021721602147490918660274601
c = 795272974058324394239265341440
test_size = 100000
start_time = time.time()
for i in range(c-1, c-test_size, -2):
if n%i == 0:
print(i, n%i)
time_elapsed = (time.time() - start_time)
print("Elapsed Time for %i iterations: %f seconds" % (test_size, time_elapsed))
seconds_in_a_year = 31557600
projected_time = time_elapsed * (c / 2 / test_size) / seconds_in_a_year
print("Projected Time for %i iterations: %i years" % (c, projected_time))

当我在电脑上运行这个程序时，输出是：

Elapsed Time for 100000 iterations: 0.024008 seconds
Projected Time for 795272974058324394239265341440 iterations: 3025094101018381 years

太多年了！

关于你链接的文章和答案，需要注意的一点是，它们提供了带有快捷键的示例。RSA密码系统被使用和工作的原因是，当生成足够大的密钥时，使用任何已知的过程来确定给定公钥的私钥在计算上是困难的(即，即使地球上所有的计算资源协同工作，也需要许多寿命(。随着计算机速度的加快，被认为足够大的密钥可能会发生一些变化，其他更难破解的公钥密码系统也可以用于提高安全性，但目前，1024到4096位的RSA在生产环境中广泛使用。你提供的n是199位(math.log(n,2)(，所以我想它可以在合理的时间内被强制使用。。。只是不使用笔记本电脑，也不使用python(如果你在C中尝试同样的暴力方法，它仍然不会在合理的时间内运行，但它会比python更快(。如果你对解决离散对数问题或整数分解的其他算法感兴趣，我对此了解不多，但我可以告诉你，对于非量子计算机，还没有已知的有效算法。

如果我有时间的话，我会回来用一些C代码更新这个答案进行比较，我只是想指出，你没有做错什么，你正在努力解决一个棘手的问题。