問題描述
如何根據(jù) e(公鑰)、d(私鑰)和模數(shù)計(jì)算 p 和 q 參數(shù)?
How do I calculate the p and q parameters from e (publickey), d (privatekey) and modulus?
我手頭有 BigInteger 鍵，我可以將粘貼復(fù)制到代碼中.一個(gè)公鑰，一個(gè)私鑰和一個(gè)模數(shù).
I have BigInteger keys at hand I can copy paste into code. One publickey, one privatekey and a modulus.
我需要從中計(jì)算 RSA 參數(shù) p 和 q.但我懷疑有一個(gè)我無法用谷歌找到的圖書館.有任何想法嗎?謝謝.
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.
這不一定是蠻力，因?yàn)槲也皇窃趯ふ宜借€.我只有一個(gè)遺留系統(tǒng)，它存儲(chǔ)了一個(gè)公鑰、私鑰對(duì)和一個(gè)模數(shù)，我需要將它們放入 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.
所以歸結(jié)為計(jì)算 (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;
}
但這似乎不起作用.你能發(fā)現(xiàn)問題嗎?
but this doesn't seem to work. Can you spot the problem?
5 小時(shí)后... :)
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#?
推薦答案
假設(shè) e 很小(這是常見的情況；傳統(tǒng)的公共指數(shù)是 65537).我們還假設(shè) 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)) 的倍數(shù).
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)).
現(xiàn)在你有 ed = k*phi(n)+1 用于某個(gè)整數(shù) k.因?yàn)?d 小于 phi(n)，所以你知道 k <e.所以你只有少量的 k 可以嘗試.實(shí)際上，phi(n) 與 n 很接近(差別在 sqrt(n) 的量級(jí)上；換句話說，當(dāng)寫成phi(n) 的上半部分與 n) 的上半部分相同，因此您可以使用以下公式計(jì)算 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.是時(shí)候記住對(duì)于所有實(shí)數(shù) a 和 b，a 和 b 是二次方程X2-(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 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))/2
p = ((p+q) + sqrt((p+q)2 - 4*pq))/2
q = ((p+q) - sqrt((p+q)2 - 4*pq))/2
q = ((p+q) - sqrt((p+q)2 - 4*pq))/2
在一般情況下，e 和 d 可能具有任意大小(可能大于 n)，因?yàn)?RSA 所需要的只是ed = 1 mod (p-1) 和 ed = 1 mod (q-1).有一種通用(且快速)的方法，看起來有點(diǎn)像 Miller-Rabin 素?cái)?shù)測(cè)試.Handbook of Applied Cryptography(第 8 章，第 8.2.2 節(jié)，第 287 頁).該方法在概念上有點(diǎn)復(fù)雜(它涉及模冪運(yùn)算)，但實(shí)現(xiàn)起來可能更簡(jiǎn)單(因?yàn)闆]有平方根).
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).
這篇關(guān)于根據(jù)私有指數(shù) (d)、公共指數(shù) (e) 和模數(shù) (n) 計(jì)算素?cái)?shù) p 和 q的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！