如何根据公共和私人指数计算RSA模数？

Question

我有一个带模数m,公共指数e和私有指数的RSA私钥d,但我使用的程序需要模数的素因子p和q.

有可能使用e和d得到p和q？

Answer 1

是的 - 一旦你知道模数N和公共/私人指数d和e,就不难获得p和q,使得N = pq.

Dan Boneh撰写的这篇论文描述了这样做的算法.它依赖于这样一个事实,根据定义,

de = 1 mod phi(N).

在任何随机选择的"证人"(2,N),存在关于具有能够用它来发现的模N 1非平凡平方根50%的几率(称之为X).然后gcd(x-1,N)给出了一个因素.

只是挑剔:所有RSA需要的是_de = 1_ mod _p-1_和mod _q-1_,所以_de = 1_ mod _lcm(p-1,q-1)_这是_phi(N)_的严格除数(使用_phi(N)_就是最初描述RSA的方式).然而,Boneh描述的方法也适用于一般情况. (3认同)

Answer 2

您可以使用我在2009年开发的开源工具,它可以在SFM格式(n,e,d)和CRT格式(p,q,dp,dq,u)之间转换RSA密钥,反之亦然.它位于SourceForge上:http://rsaconverter.sourceforge.net/

我实施的算法基于Dan Boneh提出的想法,如前面的答案所述.

我希望这会有用.

Mounir IDRASSI - IDRIX

Answer 3

我在密码栈交换上发布了一个答复，在这里回答了同样的问题。它使用与Boneh论文中概述的方法相同的方法，但是对其实际工作方式进行了很多解释。我还尝试假定最少的先验知识。

希望这可以帮助！