1 package org.bouncycastle.crypto.generators; 2 3 import java.math.BigInteger; 4 5 import org.bouncycastle.crypto.AsymmetricCipherKeyPair; 6 import org.bouncycastle.crypto.AsymmetricCipherKeyPairGenerator; 7 import org.bouncycastle.crypto.KeyGenerationParameters; 8 import org.bouncycastle.crypto.params.RSAKeyGenerationParameters; 9 import org.bouncycastle.crypto.params.RSAKeyParameters; 10 import org.bouncycastle.crypto.params.RSAPrivateCrtKeyParameters; 11 import org.bouncycastle.math.Primes; 12 import org.bouncycastle.math.ec.WNafUtil; 13 14 /** 15 * an RSA key pair generator. 16 */ 17 public class RSAKeyPairGenerator 18 implements AsymmetricCipherKeyPairGenerator 19 { 20 private static final BigInteger ONE = BigInteger.valueOf(1); 21 22 private RSAKeyGenerationParameters param; 23 private int iterations; 24 25 public void init(KeyGenerationParameters param) 26 { 27 this.param = (RSAKeyGenerationParameters)param; 28 this.iterations = getNumberOfIterations(this.param.getStrength(), this.param.getCertainty()); 29 } 30 31 public AsymmetricCipherKeyPair generateKeyPair() 32 { 33 AsymmetricCipherKeyPair result = null; 34 boolean done = false; 35 36 // 37 // p and q values should have a length of half the strength in bits 38 // 39 int strength = param.getStrength(); 40 int pbitlength = (strength + 1) / 2; 41 int qbitlength = strength - pbitlength; 42 int mindiffbits = (strength / 2) - 100; 43 44 if (mindiffbits < strength / 3) 45 { 46 mindiffbits = strength / 3; 47 } 48 49 int minWeight = strength >> 2; 50 51 // d lower bound is 2^(strength / 2) 52 BigInteger dLowerBound = BigInteger.valueOf(2).pow(strength / 2); 53 // squared bound (sqrt(2)*2^(nlen/2-1))^2 54 BigInteger squaredBound = ONE.shiftLeft(strength - 1); 55 // 2^(nlen/2 - 100) 56 BigInteger minDiff = ONE.shiftLeft(mindiffbits); 57 58 while (!done) 59 { 60 BigInteger p, q, n, d, e, pSub1, qSub1, gcd, lcm; 61 62 e = param.getPublicExponent(); 63 64 p = chooseRandomPrime(pbitlength, e, squaredBound); 65 66 // 67 // generate a modulus of the required length 68 // 69 for (; ; ) 70 { 71 q = chooseRandomPrime(qbitlength, e, squaredBound); 72 73 // p and q should not be too close together (or equal!) 74 BigInteger diff = q.subtract(p).abs(); 75 if (diff.bitLength() < mindiffbits || diff.compareTo(minDiff) <= 0) 76 { 77 continue; 78 } 79 80 // 81 // calculate the modulus 82 // 83 n = p.multiply(q); 84 85 if (n.bitLength() != strength) 86 { 87 // 88 // if we get here our primes aren't big enough, make the largest 89 // of the two p and try again 90 // 91 p = p.max(q); 92 continue; 93 } 94 95 /* 96 * Require a minimum weight of the NAF representation, since low-weight composites may 97 * be weak against a version of the number-field-sieve for factoring. 98 * 99 * See "The number field sieve for integers of low weight", Oliver Schirokauer. 100 */ 101 if (WNafUtil.getNafWeight(n) < minWeight) 102 { 103 p = chooseRandomPrime(pbitlength, e, squaredBound); 104 continue; 105 } 106 107 break; 108 } 109 110 if (p.compareTo(q) < 0) 111 { 112 gcd = p; 113 p = q; 114 q = gcd; 115 } 116 117 pSub1 = p.subtract(ONE); 118 qSub1 = q.subtract(ONE); 119 gcd = pSub1.gcd(qSub1); 120 lcm = pSub1.divide(gcd).multiply(qSub1); 121 122 // 123 // calculate the private exponent 124 // 125 d = e.modInverse(lcm); 126 127 if (d.compareTo(dLowerBound) <= 0) 128 { 129 continue; 130 } 131 else 132 { 133 done = true; 134 } 135 136 // 137 // calculate the CRT factors 138 // 139 BigInteger dP, dQ, qInv; 140 141 dP = d.remainder(pSub1); 142 dQ = d.remainder(qSub1); 143 qInv = q.modInverse(p); 144 145 result = new AsymmetricCipherKeyPair( 146 new RSAKeyParameters(false, n, e), 147 new RSAPrivateCrtKeyParameters(n, e, d, p, q, dP, dQ, qInv)); 148 } 149 150 return result; 151 } 152 153 /** 154 * Choose a random prime value for use with RSA 155 * 156 * @param bitlength the bit-length of the returned prime 157 * @param e the RSA public exponent 158 * @return A prime p, with (p-1) relatively prime to e 159 */ 160 protected BigInteger chooseRandomPrime(int bitlength, BigInteger e, BigInteger sqrdBound) 161 { 162 for (int i = 0; i != 5 * bitlength; i++) 163 { 164 BigInteger p = new BigInteger(bitlength, 1, param.getRandom()); 165 166 if (p.mod(e).equals(ONE)) 167 { 168 continue; 169 } 170 171 if (p.multiply(p).compareTo(sqrdBound) < 0) 172 { 173 continue; 174 } 175 176 if (!isProbablePrime(p)) 177 { 178 continue; 179 } 180 181 if (!e.gcd(p.subtract(ONE)).equals(ONE)) 182 { 183 continue; 184 } 185 186 return p; 187 } 188 189 throw new IllegalStateException("unable to generate prime number for RSA key"); 190 } 191 192 protected boolean isProbablePrime(BigInteger x) 193 { 194 /* 195 * Primes class for FIPS 186-4 C.3 primality checking 196 */ 197 return !Primes.hasAnySmallFactors(x) && Primes.isMRProbablePrime(x, param.getRandom(), iterations); 198 } 199 200 private static int getNumberOfIterations(int bits, int certainty) 201 { 202 /* 203 * NOTE: We enforce a minimum 'certainty' of 100 for bits >= 1024 (else 80). Where the 204 * certainty is higher than the FIPS 186-4 tables (C.2/C.3) cater to, extra iterations 205 * are added at the "worst case rate" for the excess. 206 */ 207 if (bits >= 1536) 208 { 209 return certainty <= 100 ? 3 210 : certainty <= 128 ? 4 211 : 4 + (certainty - 128 + 1) / 2; 212 } 213 else if (bits >= 1024) 214 { 215 return certainty <= 100 ? 4 216 : certainty <= 112 ? 5 217 : 5 + (certainty - 112 + 1) / 2; 218 } 219 else if (bits >= 512) 220 { 221 return certainty <= 80 ? 5 222 : certainty <= 100 ? 7 223 : 7 + (certainty - 100 + 1) / 2; 224 } 225 else 226 { 227 return certainty <= 80 ? 40 228 : 40 + (certainty - 80 + 1) / 2; 229 } 230 } 231 } 232
