RSA & Yafu -RSA指数与强暴

Question

我是一个门外汉，在RSA背后的数学(和一般的，相对的)，我的目标是残暴的大量512位RSA密钥。在搜索了一下之后，我发现‘ll、yafu和FaaS (保理服务)程序是主要的候选程序，然而，从成本上讲，用亚马逊破解密钥是不切实际的，而我想破解的密钥(对于长期关机的游戏，我要说明的是，没有恶意的)，指数为17。

总之，我想知道.

1. 如果需要在模数旁边指定指数，如果需要，则如何实际指定指数(最好使用msieve，因为根据这，这是唯一被证明能破解这个大小的键的算法)，因为似乎没有选择(msileVersion1.53)。
2. 是否有多台计算机/CPU核心将加速这一过程，以及如果可能的话如何使用它们(这和msieve似乎意味着情况就是这样)。我也有点好奇，尽管上面的程序是单线程的，但在短短几个小时内通过Amazon是如何做到的。

Answer 1

公共指数e是17这一事实并没有帮助。对正确生成的RSA密钥的标准攻击(除了它们的公共模数N的小尺寸外)是对N的因子。这是保理任务的唯一输入，大部分工作都是在这个任务中完成的。

e只涉及到准备私钥的最终形式，这很容易:从e和素因子p、q of N准备私钥的代码可以生成所需格式的RSA密钥。对于N(n,d)格式，工作的d是e^{-1}\bmod((p-1)(q-1))，这是Python：d=pow(17,-1,(p-1)*(q-1))中的一行。

在512位，GNFS是算法的选择，两个常见的瓶颈是筛分和矩阵步长。多个CPU肯定有助于筛分。对于矩阵步骤，它很复杂，但是需要一台内存很大的机器。

查看一下CADO-NFS的实现。

GPU在分解方面是否有用是有争议的，而且我还没有找到任何关于512位实际使用的说明。

如果您有多个N，其中一些是由有缺陷的进程生成的，那么可能会有特殊的攻击来计算对(N_i,N_j)，i<j的GCD。当我们发现它不是1时，这就会影响到N_i和N_j。如果“长时间关机游戏”使用的是一个糟糕的密钥生成器，这是值得一试的，尤其是在CTF上下文中。这方面有一些改进，既包括计算方面的改进，也包括扩展可利用的弱生成器类；参见这。