仅从公共密钥中删除长RSA密钥

Question

为了竞赛，我试图学习如何仅基于公共密钥来破坏RSA密钥：

• e = 65537
• n = 632459103267572196107100983820469021721602147490918660274601

所以我跟随了this webpage和this answer。并尝试：

    >>> 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开始，它是一个偶数。我猜想从偶数到第二步减少是愚蠢的，因为这只会导致我测试非因式分解器？

Answer 1

TL; DR：破解长RSA密钥在计算上比较困难（即，没有已知的可在多项式时间内运行的解决方案），虽然您的算法可能不是最有效的，但是没有人发现可以破解长RSA密钥的算法（经典计算机-量子计算机的Shor's algorithm可能会在多项式时间内破解长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密码系统并起作用的原因是，当生成足够大的密钥时，使用任何已知过程来确定私钥在计算上都是棘手的（即，即使地球上的所有计算资源协同工作也将花费很多生命）给定公钥。随着计算机变得越来越快，被认为足够大的密钥可能会发生一些变化，并且其他更难以破解的公钥密码系统也可以用于提高安全性，但是就目前而言，已广泛使用1,024至4,096位RSA在生产环境中。您提供的n是199位（math.log(n,2)），因此我想可以在一段合理的时间内对其进行暴力破解...只是不使用笔记本电脑也不使用python（如果您尝试相同的暴力破解方法在C中，它仍然不会在合理的时间内运行-但它会比python更快。如果您对解决离散对数问题或整数分解的其他算法感兴趣，那么我对此并不了解，但是我可以告诉您没有已知的非量子计算机有效算法

。 >

[如果有时间，我会回来并用一些C代码更新此答案以进行比较，我只是想指出您没有做错任何事情，您正在尝试解决一个棘手的问题。