python - 仅从公钥破解长 RSA key

Question

为了参加比赛，我正在尝试学习如何破解仅给定公钥的 RSA key :

• 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开始，它是一个偶数。我猜想从偶数开始减少第 2 步是愚蠢的，因为它只会让我测试非因子分解？

更新

阅读 Dan 的评论后，我现在正在尝试寻找一个小因素，而不是从大因素开始。

>>> 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 key 在计算上很困难(即没有已知的解决方案可以在多项式时间内运行)，虽然您的算法可能不是最有效的，但没有人找到可以破解长 RSA key 的算法(使用经典计算机 - Shor's algorithm 对于量子计算机可以在多项式时间内破解长 RSA key )。

---

更长的答案:

为了估计您的程序执行需要多长时间，我编写了以下 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 密码系统的原因是当生成足够大的 key 时，使用任何已知程序来确定私钥在计算上是难以处理的(即即使地球上所有计算资源一起工作也需要很多生命周期)给定公钥。随着计算机变得越来越快，被认为足够大的 key 可能会发生一些变化，其他更难破解的公钥密码系统也可以用于更高的安全性，但就目前而言，1,024 到 4,096 位 RSA 被广泛使用在生产环境中。您提供的 n 是 199 位 (math.log(n,2))，所以我想它可以在合理的时间内被暴力破解……只是不使用笔记本电脑也不使用 python(如果你在 C 中尝试相同的强力方法，它仍然不会在合理的时间内运行 - 但它会比 python 更快)。如果您对解决离散对数问题或整数分解的其他算法感兴趣，我对此了解不多，但我可以告诉您目前还没有针对非量子计算机的有效算法.

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