Geek Answers Handbook

Calculate the prime numbers p and q from the private indicator (d), the public indicator (e) and the module (n)

How to calculate p and q parameters from e (publickey), d (privatekey) and module?

I have BigInteger keys on hand, I can copy the paste into the code. One publisher, one private key and module.

I need to calculate the RSA p and q parameters. But I suspect there is a library for what I could not find with Google. Any ideas? Thanks.

This should not be brute force, since I am not behind a private key. I just have an outdated system that stores a public pair of private keys and a module, and I need to get them in C # for use with RSACryptoServiceProvider.

So, it comes down to computing (p + q) on

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 does not seem to work. Can you spot the problem?

After 5 hours...:)

Ok How to choose a random number from Zn * ( http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n ) in C #?

+7
c # cryptography rsa
source share
4 answers

Suppose that e is small (general case, the traditional public indicator is 65537). Suppose also 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 less than phi (n), you know that k <e. Therefore, you only have a small amount of k to try. In fact, phi (n) is close to n (the difference is of the order of sqrt (n), in other words, when writing in bits, the upper half of phi (n) is identical to the upper part of n), so you can calculate k 's: k' = round ( ed / n). k 'is very close to k (that is, | k'-k | <= 1), while the size of e is not more than half the size of n.

Given k, you can easily get phi (n) = (ed-1) / k. It so happened that:

phi (n) = (p-1) (q-1) = pq - (p + q) + 1 = n + 1 - (p + q)

So you get p + q = n + 1 - phi (n). You also have pq. It is time to remember that for all real numbers a and ba and b are two solutions of the quadratic equation X 2 - (a + b) X + ab. So, for p + q and pq, p and q are obtained by solving the quadratic equation:

(p + q) 2 - 4 * pq)) / 2 (p + q) 2 - 4 * pq)) / 2

In the general case, e and d can have arbitrary sizes (possibly greater than n), since all that RSA requires is ed = 1 mod (p-1) and ed = 1 mod (q-1). There is a general (and quick) method that is a bit like the Miller-Rabin primitive test. It is described in the Handbook of Applied Cryptography (Chapter 8, Section 8.2.2, p. 287). This method is conceptually a bit more complicated (it includes modular exponentiation), but it can be easier to implement (since there is no square root).

+4
source share

There is a procedure for recovering p and q from n, e, and d described in NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Basic Creation Schemes Using Integer Factorization Cryptography in Appendix C.

Stages:

  • Let k = de - 1. If k is odd, go to step 4.
  • Write k as k = 2 t r, where r is the largest odd integer dividing k and t ≥ 1. Or, in simpler terms, divide k again by 2 until you reach the odd number.
  • For i = 1 to 100 do:
    • Generate a random integer g in the range [0, n-1].
    • Let y = g r mod n
    • If y = 1 or y = n - 1, go to step 3.1 (i.e. repeat this cycle).
    • For j = 1 - t - 1 do:
      • Let x = y 2 mod n
      • If x = 1, go to (external) Step 5.
      • If x = n - 1, go to step 3.1.
      • Let y = x.
    • Let x = y 2 mod n
    • If x = 1, go to (external) Step 5.
    • Proceed
  • Print "main factors not found" and stop.
  • Let p = GCD (y - 1, n) and q = n / p
  • Conclusion (p, q) as simple factors.

I recently wrote an implementation in Java. Not very useful for C #, I understand, but maybe it can be easily ported:

 // 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");

This code uses several helper definitions / methods:

 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; }
+3
source share

I adapted the Java code provided by Duncan in C # if anyone is interested:

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

In this case, the standard class System.Numerics.BigInteger is used.

This has been tested with the following unit test:

 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);
+1
source share

I implemented the method described by Thomas Pornin.

The BigInteger class is a version of Chew Keong TAN C # (checking code comments for bug fixes)

  /// 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"); } "  /// 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"); } 18B44A3D155C61EBF4E3261C8BB157E36F63FE30E9AF28892B59E2ADEB18CC8C8BAD284B9165819CA4DEC94AA06B69BCE81706D1C1B668EB128695E5F7FEDE18A908A3011A646A481D3EA71D8A387D474609BD57A882B182E047DE80E04B4221416BD39DFA1FAC0300641962ADB109E28CAF50061B68C9CABD9B00313C0F46ED"  /// 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"); }
0
source share

More articles:


All Articles