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