1c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrompackage org.bouncycastle.crypto.generators; 2c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 3c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstromimport java.math.BigInteger; 4c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstromimport java.security.SecureRandom; 5c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 6253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson// BEGIN android-added 7253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilsonimport java.util.logging.Logger; 8253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson// END android-added 9c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstromimport org.bouncycastle.util.BigIntegers; 10c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 11c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstromclass DHParametersHelper 12c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom{ 13253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // BEGIN android-added 14253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson private static final Logger logger = Logger.getLogger(DHParametersHelper.class.getName()); 15253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // END android-added 16253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson 17c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom private static final BigInteger ONE = BigInteger.valueOf(1); 18c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom private static final BigInteger TWO = BigInteger.valueOf(2); 19c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 206e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /* 216e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * Finds a pair of prime BigInteger's {p, q: p = 2q + 1} 226e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * 236e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * (see: Handbook of Applied Cryptography 4.86) 246e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 256e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom static BigInteger[] generateSafePrimes(int size, int certainty, SecureRandom random) 26c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 27253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // BEGIN android-added 28253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson logger.info("Generating safe primes. This may take a long time."); 29253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson long start = System.currentTimeMillis(); 30253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson int tries = 0; 31253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // END android-added 32c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger p, q; 33c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int qLength = size - 1; 34c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 35c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom for (;;) 36c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 37253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // BEGIN android-added 38253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson tries++; 39253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // END android-added 40c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom q = new BigInteger(qLength, 2, random); 41c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 42c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom // p <- 2q + 1 43c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom p = q.shiftLeft(1).add(ONE); 44c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 456e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if (p.isProbablePrime(certainty) && (certainty <= 2 || q.isProbablePrime(certainty))) 46c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 476e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom break; 48c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 49c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 50253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // BEGIN android-added 51253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson long end = System.currentTimeMillis(); 52253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson long duration = end - start; 53253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson logger.info("Generated safe primes: " + tries + " tries took " + duration + "ms"); 54253ce5e6c172a18248469ffc62748a31c64e825cJesse Wilson // END android-added 55c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 56c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return new BigInteger[] { p, q }; 57c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 58c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 596e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /* 606e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * Select a high order element of the multiplicative group Zp* 616e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * 626e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * p and q must be s.t. p = 2*q + 1, where p and q are prime (see generateSafePrimes) 636e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 646e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom static BigInteger selectGenerator(BigInteger p, BigInteger q, SecureRandom random) 65c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 66c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger pMinusTwo = p.subtract(TWO); 67c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom BigInteger g; 68c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 696e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /* 706e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * (see: Handbook of Applied Cryptography 4.80) 716e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 726e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom// do 736e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom// { 746e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom// g = BigIntegers.createRandomInRange(TWO, pMinusTwo, random); 756e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom// } 766e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom// while (g.modPow(TWO, p).equals(ONE) || g.modPow(q, p).equals(ONE)); 77c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 786e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 796e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /* 806e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * RFC 2631 2.2.1.2 (and see: Handbook of Applied Cryptography 4.81) 816e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 82c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom do 83c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom { 846e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom BigInteger h = BigIntegers.createRandomInRange(TWO, pMinusTwo, random); 85c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 86c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom g = h.modPow(TWO, p); 87c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 88c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom while (g.equals(ONE)); 896e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 90c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 91c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom return g; 92c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom } 93c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom} 94