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

问题描述

如何从e（publickey），d（privatekey）和模数计算p和q参数？

我有BigInteger键，我可以将粘贴代码复制。一个公钥，一个私钥和一个模数。

我需要从这里计算RSA参数p和q。但我怀疑有一个图书馆，我无法找到与谷歌。有任何想法吗？谢谢。

这不必是暴力的，因为我不是私人密钥。我只是有一个遗留系统存储一个公共，私人密钥对和一个模数，我需要让他们进入c＃使用RSACryptoServiceProvider。

---

因此，由

计算（p + q）

  public BigInteger _pPlusq b {
 int k =（this.getExponent（）* this.getD（）/ this.getModulus（））IntValue（）; 
 
 BigInteger phiN =（this.getExponent（）* this.getD（） -  1）/ k; 
 
 return phiN  -  this.getModulus（） -  1; 
 
} 
  

但这似乎不起作用。您能找到问题吗？

---

5小时后...：）

好的。如何从Zn *中选择随机数字（ http://en.wikipedia.org/wiki/ Multiplicative_group_of_integers_modulo_n ）in C＃？

解决方案

让我们假设 e 很小（这是常见的情况;传统的公共指数是65537 ）。让我们还假设 phi（n）=（p-1）（q-1） （这不一定是这种情况; RSA要求是 ed = 1 mod lcm（p-1，q-1） / em>只是 lcm（p-1，q-1）的倍数。

k * phi（n）+1 为某个整数 k 。由于 d 小于 phi（n），您知道 k < e 。因此，您只需要少量的 k 即可尝试。实际上， phi（n）接近 n （差异在于 sqrt（n）的顺序;换句话说， （n）的上半部分与 n 的上半部分相同），因此您可以用下式计算 k'： > k'= round（ed / n）。只要 k> 的大小 k 给予 k ，您可以轻松地获得 phi（n）=（ed-1）/ k 。这样发生：

phi（n）=（p-1）（q-1）= pq-（p + q）+ 1 = n + 1 - （p + q）

因此，您得到 p + q = n + 1 - phi 。您也有 pq 。现在是时候记住对于所有的实数和 b ， 和 b 二次方程 X ² - （a + b）X + ab 。因此，通过求解二次方程式，得到 p + q 和 pq ， p 和 q p>

p =（（p + q）+ sqrt（（p + q）2 p-4 * pq））/ 2

q =（（p + q）-sqrt（（p + q） ^{2 <= 4 * pq）） / 2>}

在一般情况下， e 和 d 可能有任意大小因为所有RSA需要的是 ed = 1 mod

（p-1）和 ed = 1 em> mod （q-1）。有一个通用（和快速）方法，看起来有点像米勒 - 拉宾素性测试。在 Handbook of Applied Cryptography （第8章，第8.2.2节） ，第287页）。该方法在概念上有点复杂（它涉及模幂运算），但可能更容易实现（因为没有平方根）。

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

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

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.

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.

---

So it comes down to calculating (p+q) by

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 hours later... :)

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

解决方案

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)).

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.

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

phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = n + 1 - (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

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

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屋！