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

问题描述

如何根据 e(公钥)、d(私钥)和模数计算 p 和 q 参数?

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

我手头有 BigInteger 键，我可以将粘贴复制到代码中.一个公钥，一个私钥和一个模数.

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.

所以归结为计算 (p+q)

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 小时后... :)

5 hours later... :)

好的.如何从 Zn* (http://en.wikipedia.org/wiki/C# 中的 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#?

推荐答案

假设 e 很小(这是常见的情况；传统的公共指数是 65537).我们还假设 ed = 1 mod phi(n)，其中 phi(n) = (p-1)(q-1)(不一定是这种情况；RSA 要求是 ed = 1 mod lcm(p-1,q-1) 和 phi(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*phi(n)+1 用于某个整数 k.因为 d 小于 phi(n)，所以你知道 k <e.所以你只有少量的 k 可以尝试.实际上，phi(n) 与 n 很接近(差别在 sqrt(n) 的量级上；换句话说，当写成phi(n) 的上半部分与 n) 的上半部分相同，因此您可以使用以下公式计算 k':k'=round(ed/n).k' 与 k 非常接近(即 |k'-k| <= 1)，只要 的大小e 不超过 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，你很容易得到 phi(n) = (ed-1)/k.碰巧的是:

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)

因此，您得到 p+q = n + 1 - phi(n).你也有pq.是时候记住对于所有实数 a 和 b，a 和 b 是二次方程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) - sqrt((p+q)² - 4*pq))/2

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

在一般情况下，e 和 d 可能具有任意大小(可能大于 n)，因为 RSA 所需要的只是ed = 1 mod (p-1) 和 ed = 1 mod (q-1).有一种通用(且快速)的方法，看起来有点像 Miller-Rabin 素数测试.Handbook of Applied Cryptography(第 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屋！