DSAParametersGenerator.java revision a198e1ecc615e26a167d0f2dca9fa7e5fc62de10
1package org.bouncycastle.crypto.generators; 2 3import java.math.BigInteger; 4import java.security.SecureRandom; 5 6import org.bouncycastle.crypto.Digest; 7// BEGIN android-changed 8import org.bouncycastle.crypto.digests.AndroidDigestFactory; 9// END android-changed 10import org.bouncycastle.crypto.params.DSAParameterGenerationParameters; 11import org.bouncycastle.crypto.params.DSAParameters; 12import org.bouncycastle.crypto.params.DSAValidationParameters; 13import org.bouncycastle.util.Arrays; 14import org.bouncycastle.util.BigIntegers; 15import org.bouncycastle.util.encoders.Hex; 16 17/** 18 * Generate suitable parameters for DSA, in line with FIPS 186-2, or FIPS 186-3. 19 */ 20public class DSAParametersGenerator 21{ 22 private Digest digest; 23 private int L, N; 24 private int certainty; 25 private SecureRandom random; 26 27 private static final BigInteger ZERO = BigInteger.valueOf(0); 28 private static final BigInteger ONE = BigInteger.valueOf(1); 29 private static final BigInteger TWO = BigInteger.valueOf(2); 30 31 private boolean use186_3; 32 private int usageIndex; 33 34 public DSAParametersGenerator() 35 { 36 // BEGIN android-changed 37 this(AndroidDigestFactory.getSHA1()); 38 // END android-changed 39 } 40 41 public DSAParametersGenerator(Digest digest) 42 { 43 this.digest = digest; 44 } 45 46 /** 47 * initialise the key generator. 48 * 49 * @param size size of the key (range 2^512 -> 2^1024 - 64 bit increments) 50 * @param certainty measure of robustness of prime (for FIPS 186-2 compliance this should be at least 80). 51 * @param random random byte source. 52 */ 53 public void init( 54 int size, 55 int certainty, 56 SecureRandom random) 57 { 58 this.use186_3 = false; 59 this.L = size; 60 this.N = getDefaultN(size); 61 this.certainty = certainty; 62 this.random = random; 63 } 64 65 /** 66 * Initialise the key generator for DSA 2. 67 * <p> 68 * Use this init method if you need to generate parameters for DSA 2 keys. 69 * </p> 70 * 71 * @param params DSA 2 key generation parameters. 72 */ 73 public void init( 74 DSAParameterGenerationParameters params) 75 { 76 // TODO Should we enforce the minimum 'certainty' values as per C.3 Table C.1? 77 this.use186_3 = true; 78 this.L = params.getL(); 79 this.N = params.getN(); 80 this.certainty = params.getCertainty(); 81 this.random = params.getRandom(); 82 this.usageIndex = params.getUsageIndex(); 83 84 if ((L < 1024 || L > 3072) || L % 1024 != 0) 85 { 86 throw new IllegalArgumentException("L values must be between 1024 and 3072 and a multiple of 1024"); 87 } 88 else if (L == 1024 && N != 160) 89 { 90 throw new IllegalArgumentException("N must be 160 for L = 1024"); 91 } 92 else if (L == 2048 && (N != 224 && N != 256)) 93 { 94 throw new IllegalArgumentException("N must be 224 or 256 for L = 2048"); 95 } 96 else if (L == 3072 && N != 256) 97 { 98 throw new IllegalArgumentException("N must be 256 for L = 3072"); 99 } 100 101 if (digest.getDigestSize() * 8 < N) 102 { 103 throw new IllegalStateException("Digest output size too small for value of N"); 104 } 105 } 106 107 /** 108 * which generates the p and g values from the given parameters, 109 * returning the DSAParameters object. 110 * <p> 111 * Note: can take a while... 112 */ 113 public DSAParameters generateParameters() 114 { 115 return (use186_3) 116 ? generateParameters_FIPS186_3() 117 : generateParameters_FIPS186_2(); 118 } 119 120 private DSAParameters generateParameters_FIPS186_2() 121 { 122 byte[] seed = new byte[20]; 123 byte[] part1 = new byte[20]; 124 byte[] part2 = new byte[20]; 125 byte[] u = new byte[20]; 126 int n = (L - 1) / 160; 127 byte[] w = new byte[L / 8]; 128 129 // BEGIN android-changed 130 if (!(digest.getAlgorithmName().equals("SHA-1"))) 131 // END android-changed 132 { 133 throw new IllegalStateException("can only use SHA-1 for generating FIPS 186-2 parameters"); 134 } 135 136 for (;;) 137 { 138 random.nextBytes(seed); 139 140 hash(digest, seed, part1); 141 System.arraycopy(seed, 0, part2, 0, seed.length); 142 inc(part2); 143 hash(digest, part2, part2); 144 145 for (int i = 0; i != u.length; i++) 146 { 147 u[i] = (byte)(part1[i] ^ part2[i]); 148 } 149 150 u[0] |= (byte)0x80; 151 u[19] |= (byte)0x01; 152 153 BigInteger q = new BigInteger(1, u); 154 155 if (!q.isProbablePrime(certainty)) 156 { 157 continue; 158 } 159 160 byte[] offset = Arrays.clone(seed); 161 inc(offset); 162 163 for (int counter = 0; counter < 4096; ++counter) 164 { 165 for (int k = 0; k < n; k++) 166 { 167 inc(offset); 168 hash(digest, offset, part1); 169 System.arraycopy(part1, 0, w, w.length - (k + 1) * part1.length, part1.length); 170 } 171 172 inc(offset); 173 hash(digest, offset, part1); 174 System.arraycopy(part1, part1.length - ((w.length - (n) * part1.length)), w, 0, w.length - n * part1.length); 175 176 w[0] |= (byte)0x80; 177 178 BigInteger x = new BigInteger(1, w); 179 180 BigInteger c = x.mod(q.shiftLeft(1)); 181 182 BigInteger p = x.subtract(c.subtract(ONE)); 183 184 if (p.bitLength() != L) 185 { 186 continue; 187 } 188 189 if (p.isProbablePrime(certainty)) 190 { 191 BigInteger g = calculateGenerator_FIPS186_2(p, q, random); 192 193 return new DSAParameters(p, q, g, new DSAValidationParameters(seed, counter)); 194 } 195 } 196 } 197 } 198 199 private static BigInteger calculateGenerator_FIPS186_2(BigInteger p, BigInteger q, SecureRandom r) 200 { 201 BigInteger e = p.subtract(ONE).divide(q); 202 BigInteger pSub2 = p.subtract(TWO); 203 204 for (;;) 205 { 206 BigInteger h = BigIntegers.createRandomInRange(TWO, pSub2, r); 207 BigInteger g = h.modPow(e, p); 208 if (g.bitLength() > 1) 209 { 210 return g; 211 } 212 } 213 } 214 215 /** 216 * generate suitable parameters for DSA, in line with 217 * <i>FIPS 186-3 A.1 Generation of the FFC Primes p and q</i>. 218 */ 219 private DSAParameters generateParameters_FIPS186_3() 220 { 221// A.1.1.2 Generation of the Probable Primes p and q Using an Approved Hash Function 222 // FIXME This should be configurable (digest size in bits must be >= N) 223 Digest d = digest; 224 int outlen = d.getDigestSize() * 8; 225 226// 1. Check that the (L, N) pair is in the list of acceptable (L, N pairs) (see Section 4.2). If 227// the pair is not in the list, then return INVALID. 228 // Note: checked at initialisation 229 230// 2. If (seedlen < N), then return INVALID. 231 // FIXME This should be configurable (must be >= N) 232 int seedlen = N; 233 byte[] seed = new byte[seedlen / 8]; 234 235// 3. n = ceiling(L ⁄ outlen) – 1. 236 int n = (L - 1) / outlen; 237 238// 4. b = L – 1 – (n ∗ outlen). 239 int b = (L - 1) % outlen; 240 241 byte[] output = new byte[d.getDigestSize()]; 242 for (;;) 243 { 244// 5. Get an arbitrary sequence of seedlen bits as the domain_parameter_seed. 245 random.nextBytes(seed); 246 247// 6. U = Hash (domain_parameter_seed) mod 2^(N–1). 248 hash(d, seed, output); 249 250 BigInteger U = new BigInteger(1, output).mod(ONE.shiftLeft(N - 1)); 251 252// 7. q = 2^(N–1) + U + 1 – ( U mod 2). 253 BigInteger q = ONE.shiftLeft(N - 1).add(U).add(ONE).subtract(U.mod(TWO)); 254 255// 8. Test whether or not q is prime as specified in Appendix C.3. 256 // TODO Review C.3 for primality checking 257 if (!q.isProbablePrime(certainty)) 258 { 259// 9. If q is not a prime, then go to step 5. 260 continue; 261 } 262 263// 10. offset = 1. 264 // Note: 'offset' value managed incrementally 265 byte[] offset = Arrays.clone(seed); 266 267// 11. For counter = 0 to (4L – 1) do 268 int counterLimit = 4 * L; 269 for (int counter = 0; counter < counterLimit; ++counter) 270 { 271// 11.1 For j = 0 to n do 272// Vj = Hash ((domain_parameter_seed + offset + j) mod 2^seedlen). 273// 11.2 W = V0 + (V1 ∗ 2^outlen) + ... + (V^(n–1) ∗ 2^((n–1) ∗ outlen)) + ((Vn mod 2^b) ∗ 2^(n ∗ outlen)). 274 // TODO Assemble w as a byte array 275 BigInteger W = ZERO; 276 for (int j = 0, exp = 0; j <= n; ++j, exp += outlen) 277 { 278 inc(offset); 279 hash(d, offset, output); 280 281 BigInteger Vj = new BigInteger(1, output); 282 if (j == n) 283 { 284 Vj = Vj.mod(ONE.shiftLeft(b)); 285 } 286 287 W = W.add(Vj.shiftLeft(exp)); 288 } 289 290// 11.3 X = W + 2^(L–1). Comment: 0 ≤ W < 2L–1; hence, 2L–1 ≤ X < 2L. 291 BigInteger X = W.add(ONE.shiftLeft(L - 1)); 292 293// 11.4 c = X mod 2q. 294 BigInteger c = X.mod(q.shiftLeft(1)); 295 296// 11.5 p = X - (c - 1). Comment: p ≡ 1 (mod 2q). 297 BigInteger p = X.subtract(c.subtract(ONE)); 298 299// 11.6 If (p < 2^(L - 1)), then go to step 11.9 300 if (p.bitLength() != L) 301 { 302 continue; 303 } 304 305// 11.7 Test whether or not p is prime as specified in Appendix C.3. 306 // TODO Review C.3 for primality checking 307 if (p.isProbablePrime(certainty)) 308 { 309// 11.8 If p is determined to be prime, then return VALID and the values of p, q and 310// (optionally) the values of domain_parameter_seed and counter. 311 if (usageIndex >= 0) 312 { 313 BigInteger g = calculateGenerator_FIPS186_3_Verifiable(d, p, q, seed, usageIndex); 314 if (g != null) 315 { 316 return new DSAParameters(p, q, g, new DSAValidationParameters(seed, counter, usageIndex)); 317 } 318 } 319 320 BigInteger g = calculateGenerator_FIPS186_3_Unverifiable(p, q, random); 321 322 return new DSAParameters(p, q, g, new DSAValidationParameters(seed, counter)); 323 } 324 325// 11.9 offset = offset + n + 1. Comment: Increment offset; then, as part of 326// the loop in step 11, increment counter; if 327// counter < 4L, repeat steps 11.1 through 11.8. 328 // Note: 'offset' value already incremented in inner loop 329 } 330// 12. Go to step 5. 331 } 332 } 333 334 private static BigInteger calculateGenerator_FIPS186_3_Unverifiable(BigInteger p, BigInteger q, 335 SecureRandom r) 336 { 337 return calculateGenerator_FIPS186_2(p, q, r); 338 } 339 340 private static BigInteger calculateGenerator_FIPS186_3_Verifiable(Digest d, BigInteger p, BigInteger q, 341 byte[] seed, int index) 342 { 343// A.2.3 Verifiable Canonical Generation of the Generator g 344 BigInteger e = p.subtract(ONE).divide(q); 345 byte[] ggen = Hex.decode("6767656E"); 346 347 // 7. U = domain_parameter_seed || "ggen" || index || count. 348 byte[] U = new byte[seed.length + ggen.length + 1 + 2]; 349 System.arraycopy(seed, 0, U, 0, seed.length); 350 System.arraycopy(ggen, 0, U, seed.length, ggen.length); 351 U[U.length - 3] = (byte)index; 352 353 byte[] w = new byte[d.getDigestSize()]; 354 for (int count = 1; count < (1 << 16); ++count) 355 { 356 inc(U); 357 hash(d, U, w); 358 BigInteger W = new BigInteger(1, w); 359 BigInteger g = W.modPow(e, p); 360 if (g.compareTo(TWO) >= 0) 361 { 362 return g; 363 } 364 } 365 366 return null; 367 } 368 369 private static void hash(Digest d, byte[] input, byte[] output) 370 { 371 d.update(input, 0, input.length); 372 d.doFinal(output, 0); 373 } 374 375 private static int getDefaultN(int L) 376 { 377 return L > 1024 ? 256 : 160; 378 } 379 380 private static void inc(byte[] buf) 381 { 382 for (int i = buf.length - 1; i >= 0; --i) 383 { 384 byte b = (byte)((buf[i] + 1) & 0xff); 385 buf[i] = b; 386 387 if (b != 0) 388 { 389 break; 390 } 391 } 392 } 393} 394