1 /*
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package sun.security.provider;
27
28 import java.math.BigInteger;
29 import java.security.AlgorithmParameterGeneratorSpi;
30 import java.security.AlgorithmParameters;
31 import java.security.InvalidAlgorithmParameterException;
32 import java.security.NoSuchAlgorithmException;
33 import java.security.NoSuchProviderException;
34 import java.security.InvalidParameterException;
35 import java.security.MessageDigest;
36 import java.security.SecureRandom;
37 import java.security.spec.AlgorithmParameterSpec;
38 import java.security.spec.InvalidParameterSpecException;
39 import java.security.spec.DSAParameterSpec;
40 import java.security.spec.DSAGenParameterSpec;
41
42 /**
43 * This class generates parameters for the DSA algorithm. It uses a default
44 * prime modulus size of 1024 bits, which can be overwritten during
45 * initialization.
46 *
47 * @author Jan Luehe
48 *
49 *
50 * @see java.security.AlgorithmParameters
51 * @see java.security.spec.AlgorithmParameterSpec
52 * @see DSAParameters
53 *
54 * @since 1.2
55 */
56
57 public class DSAParameterGenerator extends AlgorithmParameterGeneratorSpi {
58
59 // the default parameters
60 private static final DSAGenParameterSpec DEFAULTS =
61 new DSAGenParameterSpec(1024, 160, 160);
62
63 // the length of prime P, subPrime Q, and seed in bits
64 private int valueL = -1;
65 private int valueN = -1;
66 private int seedLen = -1;
67
68 // the source of randomness
69 private SecureRandom random;
70
71 // useful constants
72 private static final BigInteger ZERO = BigInteger.valueOf(0);
73 private static final BigInteger ONE = BigInteger.valueOf(1);
74 private static final BigInteger TWO = BigInteger.valueOf(2);
75
76 public DSAParameterGenerator() {
77 }
78
79 /**
80 * Initializes this parameter generator for a certain strength
81 * and source of randomness.
82 *
83 * @param strength the strength (size of prime) in bits
84 * @param random the source of randomness
85 */
86 protected void engineInit(int strength, SecureRandom random) {
87 if ((strength >= 512) && (strength <= 1024) && (strength % 64 == 0)) {
88 this.valueN = 160;
89 } else if (strength == 2048) {
90 this.valueN = 224;
91 // } else if (strength == 3072) {
92 // this.valueN = 256;
93 } else {
94 throw new InvalidParameterException
95 ("Prime size should be 512 - 1024, or 2048");
96 }
97 this.valueL = strength;
98 this.seedLen = valueN;
99 this.random = random;
100 }
101
102 /**
103 * Initializes this parameter generator with a set of
104 * algorithm-specific parameter generation values.
105 *
106 * @param genParamSpec the set of algorithm-specific parameter generation values
107 * @param random the source of randomness
108 *
109 * @exception InvalidAlgorithmParameterException if the given parameter
110 * generation values are inappropriate for this parameter generator
111 */
112 protected void engineInit(AlgorithmParameterSpec genParamSpec,
113 SecureRandom random)
114 throws InvalidAlgorithmParameterException {
115 if (!(genParamSpec instanceof DSAGenParameterSpec)) {
116 throw new InvalidAlgorithmParameterException("Invalid parameter");
117 }
118 DSAGenParameterSpec dsaGenParams = (DSAGenParameterSpec) genParamSpec;
119 int primePLen = dsaGenParams.getPrimePLength();
120 if (primePLen > 2048) {
121 throw new InvalidParameterException
122 ("No support for prime size " + primePLen);
123 }
124 // directly initialize using the already validated values
125 this.valueL = primePLen;
126 this.valueN = dsaGenParams.getSubprimeQLength();
127 this.seedLen = dsaGenParams.getSeedLength();
128 this.random = random;
129 }
130
131 /**
132 * Generates the parameters.
133 *
134 * @return the new AlgorithmParameters object
135 */
136 protected AlgorithmParameters engineGenerateParameters() {
137 AlgorithmParameters algParams = null;
138 try {
139 if (this.random == null) {
140 this.random = new SecureRandom();
141 }
142 if (valueL == -1) {
143 try {
144 engineInit(DEFAULTS, this.random);
145 } catch (InvalidAlgorithmParameterException iape) {
146 // should never happen
147 }
148 }
149 BigInteger[] pAndQ = generatePandQ(this.random, valueL,
150 valueN, seedLen);
151 BigInteger paramP = pAndQ[0];
152 BigInteger paramQ = pAndQ[1];
153 BigInteger paramG = generateG(paramP, paramQ);
154
155 DSAParameterSpec dsaParamSpec =
156 new DSAParameterSpec(paramP, paramQ, paramG);
157 algParams = AlgorithmParameters.getInstance("DSA", "SUN");
158 algParams.init(dsaParamSpec);
159 } catch (InvalidParameterSpecException e) {
160 // this should never happen
161 throw new RuntimeException(e.getMessage());
162 } catch (NoSuchAlgorithmException e) {
163 // this should never happen, because we provide it
164 throw new RuntimeException(e.getMessage());
165 } catch (NoSuchProviderException e) {
166 // this should never happen, because we provide it
167 throw new RuntimeException(e.getMessage());
168 }
169
170 return algParams;
171 }
172
173 /*
174 * Generates the prime and subprime parameters for DSA,
175 * using the provided source of randomness.
176 * This method will generate new seeds until a suitable
177 * seed has been found.
178 *
179 * @param random the source of randomness to generate the
180 * seed
181 * @param valueL the size of <code>p</code>, in bits.
182 * @param valueN the size of <code>q</code>, in bits.
183 * @param seedLen the length of <code>seed</code>, in bits.
184 *
185 * @return an array of BigInteger, with <code>p</code> at index 0 and
186 * <code>q</code> at index 1, the seed at index 2, and the counter value
187 * at index 3.
188 */
189 private static BigInteger[] generatePandQ(SecureRandom random, int valueL,
190 int valueN, int seedLen) {
191 String hashAlg = null;
192 if (valueN == 160) {
193 hashAlg = "SHA";
194 } else if (valueN == 224) {
195 hashAlg = "SHA-224";
196 } else if (valueN == 256) {
197 hashAlg = "SHA-256";
198 }
199 MessageDigest hashObj = null;
200 try {
201 hashObj = MessageDigest.getInstance(hashAlg);
202 } catch (NoSuchAlgorithmException nsae) {
203 // should never happen
204 nsae.printStackTrace();
205 }
206
207 /* Step 3, 4: Useful variables */
208 int outLen = hashObj.getDigestLength()*8;
209 int n = (valueL - 1) / outLen;
210 int b = (valueL - 1) % outLen;
211 byte[] seedBytes = new byte[seedLen/8];
212 BigInteger twoSl = TWO.pow(seedLen);
213 int primeCertainty = 80; // for 1024-bit prime P
214 if (valueL == 2048) {
215 primeCertainty = 112;
216 //} else if (valueL == 3072) {
217 // primeCertainty = 128;
218 }
219
220 BigInteger resultP, resultQ, seed = null;
221 int counter;
222 while (true) {
223 do {
224 /* Step 5 */
225 random.nextBytes(seedBytes);
226 seed = new BigInteger(1, seedBytes);
227
228 /* Step 6 */
229 BigInteger U = new BigInteger(1, hashObj.digest(seedBytes)).
230 mod(TWO.pow(valueN - 1));
231
232 /* Step 7 */
233 resultQ = TWO.pow(valueN - 1).add(U).add(ONE). subtract(U.mod(TWO));
234 } while (!resultQ.isProbablePrime(primeCertainty));
235
236 /* Step 10 */
237 BigInteger offset = ONE;
238 /* Step 11 */
239 for (counter = 0; counter < 4*valueL; counter++) {
240 BigInteger V[] = new BigInteger[n + 1];
241 /* Step 11.1 */
242 for (int j = 0; j <= n; j++) {
243 BigInteger J = BigInteger.valueOf(j);
244 BigInteger tmp = (seed.add(offset).add(J)).mod(twoSl);
245 byte[] vjBytes = hashObj.digest(toByteArray(tmp));
246 V[j] = new BigInteger(1, vjBytes);
247 }
248 /* Step 11.2 */
249 BigInteger W = V[0];
250 for (int i = 1; i < n; i++) {
251 W = W.add(V[i].multiply(TWO.pow(i * outLen)));
252 }
253 W = W.add((V[n].mod(TWO.pow(b))).multiply(TWO.pow(n * outLen)));
254 /* Step 11.3 */
255 BigInteger twoLm1 = TWO.pow(valueL - 1);
256 BigInteger X = W.add(twoLm1);
257 /* Step 11.4, 11.5 */
258 BigInteger c = X.mod(resultQ.multiply(TWO));
259 resultP = X.subtract(c.subtract(ONE));
260 /* Step 11.6, 11.7 */
261 if (resultP.compareTo(twoLm1) > -1
262 && resultP.isProbablePrime(primeCertainty)) {
263 /* Step 11.8 */
264 BigInteger[] result = {resultP, resultQ, seed,
265 BigInteger.valueOf(counter)};
266 return result;
267 }
268 /* Step 11.9 */
269 offset = offset.add(BigInteger.valueOf(n)).add(ONE);
270 }
271 }
272
273 }
274
275 /*
276 * Generates the <code>g</code> parameter for DSA.
277 *
278 * @param p the prime, <code>p</code>.
279 * @param q the subprime, <code>q</code>.
280 *
281 * @param the <code>g</code>
282 */
283 private static BigInteger generateG(BigInteger p, BigInteger q) {
284 BigInteger h = ONE;
285 /* Step 1 */
286 BigInteger pMinusOneOverQ = (p.subtract(ONE)).divide(q);
287 BigInteger resultG = ONE;
288 while (resultG.compareTo(TWO) < 0) {
289 /* Step 3 */
290 resultG = h.modPow(pMinusOneOverQ, p);
291 h = h.add(ONE);
292 }
293 return resultG;
294 }
295
296 /*
297 * Converts the result of a BigInteger.toByteArray call to an exact
298 * signed magnitude representation for any positive number.
299 */
300 private static byte[] toByteArray(BigInteger bigInt) {
301 byte[] result = bigInt.toByteArray();
302 if (result[0] == 0) {
303 byte[] tmp = new byte[result.length - 1];
304 System.arraycopy(result, 1, tmp, 0, tmp.length);
305 result = tmp;
306 }
307 return result;
308 }
309 }