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