-1

我试图d在 Python 中找到，这样

(2 ** d) mod n = s2

在哪里n = 

132177882185373774813945506243321607011510930684897434818595314234725602493934515403833460241072842788085178405842019124354553719616350676051289956113618487539608319422698056216887276531560386229271076862408823338669795520077783060068491144890490733649000321192437210365603856143989888494731654785043992278251

和s2 =

18269259493999292542402899855086766469838750310113238685472900147571691729574239379292239589580462883199555239659513821547589498977376834615709314449943085101697266417531578751311966354219681199183298006299399765358783274424349074040973733214578342738572625956971005052398172213596798751992841512724116639637

我不是在寻找解决方案，而是在寻找一种相当快速的方法来做到这一点。我尝试过使用pow和插入不同的值，但这很慢并且永远不会得到解决方案。我怎样才能找到d？

4

3 回答 3

5

没有已知的算法可以解决您的问题。它被称为离散对数问题，一些密码系统取决于它的复杂性（除非你知道 n 的因式分解，否则你无法快速找到它的解决方案）

于 2012-09-17T19:25:45.933 回答
2

查看Is it possible to get RSA private key known public key 和一组“原始数据=>加密数据”条目的第二个答案？. 已知明文攻击并不比已知密文容易。

于 2012-09-17T19:49:27.727 回答
1

唯一已知的离散对数求解器是围绕知道这些因素而构建的。如果您没有因子，则需要生成它们。

最好的合理时间算法是Shor 算法。问题是您需要一台具有足够量子比特的量子计算机，而目前还没有人为您的样本数据构建足够大的量子计算机。看起来还需要几年时间才能有人这样做。目前人们仍然对像 15 和 21 这样的因式分解感到兴奋。

如果您想使用经典计算，那么最知名的算法远非“相当快”。我相信最近有人表明 2^1039-1 的波恩结果应该可以在 4 个月内用现代 PC 重现。再过5年，也许会缩短到一个月。

没有已知的合理的快速算法，你不应该感到惊讶，因为如果有，大多数私钥加密将是可破解的，因此毫无价值。如果有人给了您您正在寻找的答案，那将是重大新闻。（是否有“P = NP？”的问题）

于 2012-09-17T19:41:08.107 回答