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

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

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

我需要从中计算RSA参数p和q。 但我怀疑有一个库，我无法用谷歌找到它。 有任何想法吗？ 谢谢。

这不一定是暴力，因为我不是在私钥之后。 我只有一个遗留系统，它存储公钥，私钥对和模数，我需要将它们放入c＃以与RSACryptoServiceProvider一起使用。

---

因此，它归结为计算（p + q）

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; } 

但这似乎不起作用。 你能发现问题吗？

---

5个小时后…… 🙂

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

Answer 1

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

现在你有一些整数k的 ed = k * phi（n）+1 。 由于d小于phi（n） ，你知道k 。 所以你只需要少量的k来尝试。 实际上， phi（n）接近于n （差值在sqrt（n）的数量级 ;换句话说，当用位写出时， phi（n）的上半部分与n的相同）所以你可以用以下公式计算k’ ： k’= round（ed / n） 。 k’非常接近k （即| k’-k | <= 1 ），只要e的大小不超过n的大小的一半即可。

给定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（n） 。 你也有pq 。 现在是时候记住，对于所有实数a和b ， a和b是二次方程X ² – （a + b）X + ab的两个解。 因此，给定p + q和pq ，通过求解二次方程得到p和q ：

p =（（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素性测试。 它在“ 应用密码学手册” （第8章，第8.2.2节，第287页）中有所描述。 该方法在概念上有点复杂（它涉及模幂运算）但可能更容易实现（因为没有平方根）。

Answer 2

有一个程序从附录C中使用整数因子分解密码术的 NIST特刊800-56B R1 推荐的双智能密钥建立方案中描述的n ， e和d中恢复p和q的过程。

涉及的步骤是：

1. 设k = de – 1 。 如果k为奇数，则转到步骤4。
2. 将k写为k = 2 ^t r ，其中r是除以k的最大奇数，并且t≥1 。 或者更简单地说，将k重复除以2直到达到奇数。
3. 对于i = 1到100，请执行以下操作：
   1. 生成[0，n-1]范围内的随机整数g 。
   2. 设y = g ^r mod n
   3. 如果y = 1或y = n – 1 ，则转到步骤3.1（即重复此循环）。
   4. 对于j = 1到t – 1，请执行以下操作：
      1. 设x = y ² mod n
      2. 如果x = 1 ，转到（外部）步骤5。
      3. 如果x = n – 1 ，请转到步骤3.1。
      4. 设y = x 。
   5. 设x = y ² mod n
   6. 如果x = 1 ，转到（外部）步骤5。
   7. 继续
4. 输出“未找到的主要因素”并停止。
5. 令p = GCD（y-1，n）并且令q = n / p
6. 输出（p，q）为主要因素。

我最近用Java编写了一个实现。 我没有直接对C＃有用，但也许可以轻松移植：

 // Step 1: Let k = de – 1. If k is odd, then go to Step 4 BigInteger k = d.multiply(e).subtract(ONE); if (isEven(k)) { // Step 2 (express k as (2^t)r, where r is the largest odd integer // dividing k and t >= 1) BigInteger r = k; BigInteger t = ZERO; do { r = r.divide(TWO); t = t.add(ONE); } while (isEven(r)); // Step 3 Random random = new Random(); boolean success = false; BigInteger y = null; step3loop: for (int i = 1; i <= 100; i++) { // 3a BigInteger g = getRandomBi(n, random); // 3b y = g.modPow(r, n); // 3c if (y.equals(ONE) || y.equals(n.subtract(ONE))) { // 3g continue step3loop; } // 3d for (BigInteger j = ONE; j.compareTo(t) <= 0; j = j.add(ONE)) { // 3d1 BigInteger x = y.modPow(TWO, n); // 3d2 if (x.equals(ONE)) { success = true; break step3loop; } // 3d3 if (x.equals(n.subtract(ONE))) { // 3g continue step3loop; } // 3d4 y = x; } // 3e BigInteger x = y.modPow(TWO, n); if (x.equals(ONE)) { success = true; break step3loop; } // 3g // (loop again) } if (success) { // Step 5 p = y.subtract(ONE).gcd(n); q = n.divide(p); return; } } // Step 4 throw new RuntimeException("Prime factors not found"); 

此代码使用一些帮助程序定义/方法：

 private static final BigInteger ONE = BigInteger.ONE; private static final BigInteger TWO = BigInteger.valueOf(2); private static final BigInteger ZERO = BigInteger.ZERO; private static boolean isEven(BigInteger bi) { return bi.mod(TWO).equals(ZERO); } private static BigInteger getRandomBi(BigInteger n, Random rnd) { // From http://stackoverflow.com/a/2290089 BigInteger r; do { r = new BigInteger(n.bitLength(), rnd); } while (r.compareTo(n) >= 0); return r; } 

Answer 3

如果有兴趣的话，我已经在C＃中修改了Duncan提供的Java代码 ：

  public static void RecoverPQ( BigInteger n, BigInteger e, BigInteger d, out BigInteger p, out BigInteger q ) { int nBitCount = (int)(BigInteger.Log(n, 2)+1); // Step 1: Let k = de – 1. If k is odd, then go to Step 4 BigInteger k = d * e - 1; if (k.IsEven) { // Step 2 (express k as (2^t)r, where r is the largest odd integer // dividing k and t >= 1) BigInteger r = k; BigInteger t = 0; do { r = r / 2; t = t + 1; } while (r.IsEven); // Step 3 var rng = new RNGCryptoServiceProvider(); bool success = false; BigInteger y = 0; for (int i = 1; i <= 100; i++) { // 3a BigInteger g; do { byte[] randomBytes = new byte[nBitCount / 8 + 1]; // +1 to force a positive number rng.GetBytes(randomBytes); randomBytes[randomBytes.Length - 1] = 0; g = new BigInteger(randomBytes); } while (g >= n); // 3b y = BigInteger.ModPow(g, r, n); // 3c if (y == 1 || y == n-1) { // 3g continue; } // 3d BigInteger x; for (BigInteger j = 1; j < t; j = j + 1) { // 3d1 x = BigInteger.ModPow(y, 2, n); // 3d2 if (x == 1) { success = true; break; } // 3d3 if (x == n-1) { // 3g continue; } // 3d4 y = x; } // 3e x = BigInteger.ModPow(y, 2, n); if (x == 1) { success = true; break; } // 3g // (loop again) } if (success) { // Step 5 p = BigInteger.GreatestCommonDivisor((y - 1), n); q = n / p; return; } } throw new Exception("Cannot compute P and Q"); } 

这使用标准的System.Numerics.BigInteger类。

这通过以下unit testing进行测试：

 BigInteger n = BigInteger.Parse("9086945041514605868879747720094842530294507677354717409873592895614408619688608144774037743497197616416703125668941380866493349088794356554895149433555027"); BigInteger e = 65537; BigInteger d = BigInteger.Parse("8936505818327042395303988587447591295947962354408444794561435666999402846577625762582824202269399672579058991442587406384754958587400493169361356902030209"); BigInteger p; BigInteger q; RecoverPQ(n, e, d, out p, out q); Assert.AreEqual(n, p * q); 

Answer 4

我实施了Thomas Pornin描述的方法 。

BigInteger类是Chew Keong TAN的C＃版本（检查bugprofix的codeproject注释）

  /// EXAMPLE (Hex Strings) /// N(MODULUS) = "DB2CB41E112BACFA2BD7C3D3D7967E84FB9434FC261F9D090A8983947DAF8488D3DF8FBDCC1F92493585E134A1B42DE519F463244D7ED384E26D516CC7A4FF7895B1992140043AACADFC12E856B202346AF8226B1A882137DC3C5A57F0D2815C1FCD4BB46FA9157FDFFD79EC3A10A824CCC1EB3CE0B6B4396AE236590016BA69" /// D(PRIVATE EXPONENT) = "18B44A3D155C61EBF4E3261C8BB157E36F63FE30E9AF28892B59E2ADEB18CC8C8BAD284B9165819CA4DEC94AA06B69BCE81706D1C1B668EB128695E5F7FEDE18A908A3011A646A481D3EA71D8A387D474609BD57A882B182E047DE80E04B4221416BD39DFA1FAC0300641962ADB109E28CAF50061B68C9CABD9B00313C0F46ED" /// E(PUBLIC EXPONENT) = "010001" /// RESULTS: /// DP = "899324E9A8B70CA05612D8BAE70844BBF239D43E2E9CCADFA11EBD43D0603FE70A63963FE3FFA38550B5FEB3DA870D2677927B91542D148FA4BEA6DCD6B2FF57" /// DQ = "E43C98265BF97066FC078FD464BFAC089628765A0CE18904F8C15318A6850174F1A4596D3E8663440115D0EEB9157481E40DCA5EE569B1F7F4EE30AC0439C637" /// INVERSEQ = "395B8CF3240C325B0F5F86A05ABCF0006695FAB9235589A56759ECBF2CD3D3DFDE0D6F16F0BE5C70CEF22348D2D09FA093C01D909D25BC1DB11DF8A4F0CE552" /// P = "ED6CF6699EAC99667E0AFAEF8416F902C00B42D6FFA2C3C18C7BE4CF36013A91F6CF23047529047660DE14A77D13B74FF31DF900541ED37A8EF89340C623759B" /// Q = "EC52382046AA660794CC1A907F8031FDE1A554CDE17E8AA216AEDC92DB2E58B0529C76BD0498E00BAA792058B2766C40FD7A9CC2F6782942D91471905561324B" public static RSACryptoServiceProvider CreateRSAPrivateKey(string mod, string privExponent, string pubExponent) { var rsa = new RSACryptoServiceProvider { PersistKeyInCsp = false }; var n = new BigInteger(mod, 16); var d = new BigInteger(privExponent, 16); var e = new BigInteger(pubExponent, 16); var zero = new BigInteger(0); var one = new BigInteger(1); var two = new BigInteger(2); var four = new BigInteger(4); BigInteger de = e*d; BigInteger modulusplus1 = n + one; BigInteger deminus1 = de - one; BigInteger p = zero; BigInteger q = zero; BigInteger kprima = de/n; var ks = new[] {kprima, kprima - one, kprima + one}; bool bfound = false; foreach (BigInteger k in ks) { BigInteger fi = deminus1/k; BigInteger pplusq = modulusplus1 - fi; BigInteger delta = pplusq*pplusq - n*four; BigInteger sqrt = delta.sqrt(); p = (pplusq + sqrt)/two; if (n%p != zero) continue; q = (pplusq - sqrt)/two; bfound = true; break; } if (bfound) { BigInteger dp = d%(p - one); BigInteger dq = d%(q - one); BigInteger inverseq = q.modInverse(p); var pars = new RSAParameters { D = d.getBytes(), DP = dp.getBytes(), DQ = dq.getBytes(), Exponent = e.getBytes(), Modulus = n.getBytes(), P = p.getBytes(), Q = q.getBytes(), InverseQ = inverseq.getBytes() }; rsa.ImportParameters(pars); return rsa; } throw new CryptographicException("Error generating the private key"); }