問題描述
如何根據 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 是二次方程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)，因為 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的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！