从私有指数（d），公共指数（e）和模数（n）计算素数p和q，

本文介绍了从私有指数（d），公共指数（e）和模数（n）计算素数p和q，的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 如何从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 。因此，您只需要少量的 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 2 - （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 在一般情况下， 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) bypublic 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 X2-(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)2 - 4*pq))/2q = ((p+q) - sqrt((p+q)2 - 4*pq))/2In 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，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！