1b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallampackage org.bouncycastle.crypto.generators; 2b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 3b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport org.bouncycastle.crypto.AsymmetricCipherKeyPair; 4b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator; 5b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport org.bouncycastle.crypto.KeyGenerationParameters; 6b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport org.bouncycastle.crypto.params.RSAKeyGenerationParameters; 7b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport org.bouncycastle.crypto.params.RSAKeyParameters; 8b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallamimport org.bouncycastle.crypto.params.RSAPrivateCrtKeyParameters; 9b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 10c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstromimport java.math.BigInteger; 11c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 12b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam/** 13b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam * an RSA key pair generator. 14b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam */ 15b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallampublic class RSAKeyPairGenerator 16b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam implements AsymmetricCipherKeyPairGenerator 17b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam{ 18c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom private static final BigInteger ONE = BigInteger.valueOf(1); 19b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 20b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam private RSAKeyGenerationParameters param; 21b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 22b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam public void init( 23b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam KeyGenerationParameters param) 24b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 25b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam this.param = (RSAKeyGenerationParameters)param; 26b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 27b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 28b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam public AsymmetricCipherKeyPair generateKeyPair() 29b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 30b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam BigInteger p, q, n, d, e, pSub1, qSub1, phi; 31b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 32b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 33b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // p and q values should have a length of half the strength in bits 34b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 35c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int strength = param.getStrength(); 36c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int pbitlength = (strength + 1) / 2; 37c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int qbitlength = strength - pbitlength; 38c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom int mindiffbits = strength / 3; 39b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 40b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam e = param.getPublicExponent(); 41b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 42c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom // TODO Consider generating safe primes for p, q (see DHParametersHelper.generateSafePrimes) 43c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom // (then p-1 and q-1 will not consist of only small factors - see "Pollard's algorithm") 44c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 45b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 46b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // generate p, prime and (p-1) relatively prime to e 47b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 48b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam for (;;) 49b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 50b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam p = new BigInteger(pbitlength, 1, param.getRandom()); 51b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 52b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (p.mod(e).equals(ONE)) 53b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 54b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam continue; 55b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 56b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 57b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (!p.isProbablePrime(param.getCertainty())) 58b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 59b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam continue; 60b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 61b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 62b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (e.gcd(p.subtract(ONE)).equals(ONE)) 63b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 64b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam break; 65b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 66b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 67b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 68b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 69b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // generate a modulus of the required length 70b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 71b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam for (;;) 72b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 73b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // generate q, prime and (q-1) relatively prime to e, 74b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // and not equal to p 75b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 76b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam for (;;) 77b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 78b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam q = new BigInteger(qbitlength, 1, param.getRandom()); 79c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom 80c37f4a04ef89e73a39a59f3c5a179af8c8ab5974Brian Carlstrom if (q.subtract(p).abs().bitLength() < mindiffbits) 81b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 82b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam continue; 83b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 84b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 85b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (q.mod(e).equals(ONE)) 86b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 87b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam continue; 88b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 89b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 90b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (!q.isProbablePrime(param.getCertainty())) 91b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 92b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam continue; 93b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 94b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 95b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (e.gcd(q.subtract(ONE)).equals(ONE)) 96b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 97b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam break; 98b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 99b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 100b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 101b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 102b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // calculate the modulus 103b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 104b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam n = p.multiply(q); 105b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 106b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (n.bitLength() == param.getStrength()) 107b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 108b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam break; 109b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 110b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 111b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 112b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // if we get here our primes aren't big enough, make the largest 113b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // of the two p and try again 114b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 115b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam p = p.max(q); 116b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 117b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 118b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam if (p.compareTo(q) < 0) 119b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam { 120b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam phi = p; 121b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam p = q; 122b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam q = phi; 123b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 124b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 125b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam pSub1 = p.subtract(ONE); 126b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam qSub1 = q.subtract(ONE); 127b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam phi = pSub1.multiply(qSub1); 128b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 129b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 130b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // calculate the private exponent 131b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 132b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam d = e.modInverse(phi); 133b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 134b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 135b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // calculate the CRT factors 136b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam // 137b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam BigInteger dP, dQ, qInv; 138b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 139b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam dP = d.remainder(pSub1); 140b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam dQ = d.remainder(qSub1); 141b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam qInv = q.modInverse(p); 142b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam 143b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam return new AsymmetricCipherKeyPair( 144b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam new RSAKeyParameters(false, n, e), 145b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam new RSAPrivateCrtKeyParameters(n, e, d, p, q, dP, dQ, qInv)); 146b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam } 147b61a96e7ef1a78acf013bbf08fe537e5b5f129caPeter Hallam} 148