因子分解安德森的RSA后门
1993年，安德森1提出了一个后门的RSA密钥生成算法。这个后门要求将后门密钥( A )植入到RSA算法的密钥生成部分。
使用以下算法生成素数P和Q，而不是通常的方式：
首先定义一个后门素数A和两个较小的随机素数P'和Q'。
让k=1
模拟是为Q执行使用Q'。
这个算法在这里也有描述，还有更多关于RSA后门的信息吗？。
这个后门允许计算N′= N \mod A，然后将N′考虑到P′和Q′中。N'仍然需要考虑，但是现在这个问题要容易得多，因为N'的大小只有N的四分之一。
请注意，在我上面的算法中，我使用了k=1，安德森最初的实现建议开始值k=P'，并迭代地将k增加一个，直到P成为素数。在我的算法中，我从k=1开始。
我的问题是：
- 从k=1而不是k=P'开始迭代是否会产生影响？
- 在生成N'的方式中，考虑到N'是如何生成的，考虑到它的生成方式，最佳的方法是什么？是否有某种保理算法使分解N'变得非常容易？
1罗斯安德森。实用RSA陷阱门。电子信件。29(11)：995,1993年。
回答 2
Cryptography用户
发布于 2021-03-05 07:42:19
如果您从k=1开始，我们希望您在一些小k_P (和k_Q)上结束循环。请注意，这使得P-Q=(k_P-k_Q)\cdot A+(P'-Q')非常常见，因此使用k_P=k_Q可以方便P\approx Q和N分解。如果您收集了许多很多备份的N，有时您可能会成功。(我仍然知道P'-Q'\gg1，但至少肯定是P'-Q'\ll \sqrt N)。即使iv您故意避免使用k_P=k_Q，它们仍然很小，并且使\frac PQ\approx \frac{k_P}{k_Q}更容易分解(但有相同的警告)。
如果以这种方式计算几个N，并且对\frac PQ总是接近某个简单的分数\frac{k_Ü}{k_Q}感到惊讶，您可能会发现，对于所有被分解的数字，\frac P{k_P}和\frac Q{k_Q}的大小都是可疑的。提取A的努力可能比预期的要少。
Cryptography用户
发布于 2021-03-04 15:21:23
- 从k=1开始迭代而不是从k=P‘开始迭代会有什么不同吗？
那么，素数P和Q都将非常接近于A的小倍数，而且在不了解A的情况下很容易考虑因素。
例如，在猜测了这些因素a,b，例如P=aA+P',Q=bA+Q'之后，我们可以在abN=abPQ=(baA+bP')(baA+aQ')上运行Fermat的方法。注意因素的差异是bP' - aQ'，它很小。在极端情况下，当P,Q大致是O(\sqrt{A}) (较大的值会使A溢出，并且很难使用后门)时，使用Coppersmith的技术可能仍然会破坏这种情况。
https://crypto.stackexchange.com/questions/88624
复制相似问题
腾讯云开发者
