计算从私人指数（d）中，公共指数（e）和模数（n）的素数p和q [英] Calculate primes p and q from private exponent (d), public exponent (e) and the modulus (n)

问题描述

我如何计算从E p和q参数（公钥），D（privatekey）和模量？

How do I calculate the p and q parameters from e (publickey), d (privatekey) and modulus?

我的BigInteger键在眼前，我可以复制粘贴到代码。一个公钥一privatekey和模量。

I have BigInteger keys at hand I can copy paste into code. One publickey, one privatekey and a modulus.

我需要计算RSA参数p和q来源于此。但我怀疑还有对于这点我是无法找到与谷歌图书馆。有任何想法吗？谢谢你。

I need to calculate the RSA parameters p and q from this. But I suspect there is a library for that which I was unable to find with google. Any ideas? Thanks.

这并不一定是蛮力，因为我的私有密钥后，我不是。我只是有一个遗留系统存储一个公共，私有密钥对和模量，我需要让他们到C＃与的RSACryptoServiceProvider使用。

This does not have to be brute force, since I'm not after the private key. I just have a legacy system which stores a public, private key pair and a modulus and I need to get them into c# to use with RSACryptoServiceProvider.

所以它归结为通过

public BigInteger _pPlusq()
    {
        int k = (this.getExponent() * this.getD() / this.getModulus()).IntValue();

        BigInteger phiN = (this.getExponent() * this.getD() - 1) / k;

        return phiN - this.getModulus() - 1;

    }

但这似乎并没有工作。 ？你能找出问题

but this doesn't seem to work. Can you spot the problem?

5个小时后...：）

5 hours later... :)

确定。我如何在C＃中选择一个随机数出锌*（http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n）的？

Ok. How can I select a random number out of Zn* (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) in C#?

推荐答案

让我们假设的电子的小（这是常见的情况下，传统的公共指数为65537 ）。让我们也假设的 ED = 1 的MOD的岛（N）的，其中的岛（N）=（P-1）（Q-1）的（这并不一定的情况下;在RSA要求是<青霉> ED = 1 的模 LCM（p-1，q-1）和披（n）的的只是多的 LCM（p-1，q-1）的）。

Let's assume that e is small (that's the common case; the Traditional public exponent is 65537). Let's also suppose that ed = 1 mod phi(n), where phi(n) = (p-1)(q-1) (this is not necessarily the case; the RSA requirements are that ed = 1 mod lcm(p-1,q-1) and phi(n) is only a multiple of lcm(p-1,q-1)).

现在你的 ED = K *岛（N）+1 的一些整数的 K 的。由于的 D 的小于的岛（N）的，你知道的 K< Ë的。所以，你只能有少数的 K 的的尝试。实际上，的披（n）的的是接近的 N 的（不同之处的的顺序的sqrt（n）的的;换句话说，写入时出位的的岛（n）的上半部的是相同的的的 N 的），所以你可以计算的 K 的有： K'= ROUND（ED / N）的。 K 的是非常接近的 K 的（即 | K'K |< = 1 的），只要大小的 Ë的是不超过一半大小的 N 的

Now you have ed = k*phi(n)+1 for some integer k. Since d is smaller than phi(n), you know that k < e. So you only have a small number of k to try. Actually, phi(n) is close to n (the difference being on the order of sqrt(n); in other words, when written out in bits, the upper half of phi(n) is identical to that of n) so you can compute k' with: k'=round(ed/n). k' is very close to k (i.e. |k'-k| <= 1) as long as the size of e is no more than half the size of n.

由于 K 的，你轻松搞定的岛（N）=（ED-1）/ K 的。恰巧的是：

Given k, you easily get phi(n) = (ed-1)/k. It so happens that:

的岛（N）=（P-1）（Q-1）= PQ - （P + Q）+ 1 = N + 1 - （p + q）的

这样，你得到的 p + q = N + 1 - 岛（N）的。您还可以的 PQ 的。现在是时候要记住，对于所有实数的 A 和乙的 A 和乙的是这两种解决方案二次方程的 X ² - （A + b）X + AB 的。因此，考虑的 P + Q 的和的 PQ 的 P 的和q 的通过解二次方程获得的

Thus, you get p+q = n + 1 - phi(n). You also have pq. It is time to remember that for all real numbers a and b, a and b are the two solutions of the quadratic equation X²-(a+b)X+ab. So, given p+q and pq, p and q are obtained by solving the quadratic equation:

p =（（p + q）+ SQRT（（p + q） ² - 4 * PQ））/ 2

p = ((p+q) + sqrt((p+q)² - 4*pq))/2

的 q =（（p + q） - 开方（（p + q） ² - 4 * PQ）） / 2 的

q = ((p+q) - sqrt((p+q)² - 4*pq))/2

在一般情况下，的电子的和的 D 的可能有任意大小（可能更大比的 N 的），因为所有RSA需要的是的 ED = 1 的MOD的（p-1）的和的 ED = 1 MOD的（q-1）的。有这看起来有点像米勒 - 拉宾检验一个通用（和快速）的方法。它在应用密码学（第8章8.2.2的手册中描述， 287页）。该方法在概念上是有点复杂（它涉及模幂），但可以是更简单的实现（因为没有平方根）。

In the general case, e and d may have arbitrary sizes (possibly greater than n), because all that RSA needs is that ed = 1 mod (p-1) and ed = 1 mod (q-1). There is a generic (and fast) method which looks a bit like the Miller-Rabin primality test. It is described in the Handbook of Applied Cryptography (chapter 8, section 8.2.2, page 287). That method is conceptually a bit more complex (it involves modular exponentiation) but may be simpler to implement (because there is no square root).

这篇关于计算从私人指数（d）中，公共指数（e）和模数（n）的素数p和q的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！