1 /*
2  * Copyright (c) 1997, 2017, 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.ProviderException;
38 import java.security.spec.AlgorithmParameterSpec;
39 import java.security.spec.InvalidParameterSpecException;
40 import java.security.spec.DSAParameterSpec;
41 import java.security.spec.DSAGenParameterSpec;
42 
43 import static sun.security.util.SecurityProviderConstants.DEF_DSA_KEY_SIZE;
44 import static sun.security.util.SecurityProviderConstants.getDefDSASubprimeSize;
45 
46 
47 /**
48  * This class generates parameters for the DSA algorithm.
49  *
50  * @author Jan Luehe
51  *
52  *
53  * @see java.security.AlgorithmParameters
54  * @see java.security.spec.AlgorithmParameterSpec
55  * @see DSAParameters
56  *
57  * @since 1.2
58  */
59 
60 public class DSAParameterGenerator extends AlgorithmParameterGeneratorSpi {
61 
62     // the length of prime P, subPrime Q, and seed in bits
63     private int valueL = -1;
64     private int valueN = -1;
65     private int seedLen = -1;
66 
67     // the source of randomness
68     private SecureRandom random;
69 
DSAParameterGenerator()70     public DSAParameterGenerator() {
71     }
72 
73     /**
74      * Initializes this parameter generator for a certain strength
75      * and source of randomness.
76      *
77      * @param strength the strength (size of prime) in bits
78      * @param random the source of randomness
79      */
80     @Override
engineInit(int strength, SecureRandom random)81     protected void engineInit(int strength, SecureRandom random) {
82         if ((strength != 2048) && (strength != 3072) &&
83             ((strength < 512) || (strength > 1024) || (strength % 64 != 0))) {
84             throw new InvalidParameterException(
85                 "Unexpected strength (size of prime): " + strength +
86                 ". Prime size should be 512-1024, 2048, or 3072");
87         }
88         this.valueL = strength;
89         this.valueN = getDefDSASubprimeSize(strength);
90         this.seedLen = valueN;
91         this.random = random;
92     }
93 
94     /**
95      * Initializes this parameter generator with a set of
96      * algorithm-specific parameter generation values.
97      *
98      * @param genParamSpec the set of algorithm-specific parameter
99      *        generation values
100      * @param random the source of randomness
101      *
102      * @exception InvalidAlgorithmParameterException if the given parameter
103      * generation values are inappropriate for this parameter generator
104      */
105     @Override
engineInit(AlgorithmParameterSpec genParamSpec, SecureRandom random)106     protected void engineInit(AlgorithmParameterSpec genParamSpec,
107             SecureRandom random) throws InvalidAlgorithmParameterException {
108         if (!(genParamSpec instanceof DSAGenParameterSpec)) {
109             throw new InvalidAlgorithmParameterException("Invalid parameter");
110         }
111         DSAGenParameterSpec dsaGenParams = (DSAGenParameterSpec)genParamSpec;
112 
113         // directly initialize using the already validated values
114         this.valueL = dsaGenParams.getPrimePLength();
115         this.valueN = dsaGenParams.getSubprimeQLength();
116         this.seedLen = dsaGenParams.getSeedLength();
117         this.random = random;
118     }
119 
120     /**
121      * Generates the parameters.
122      *
123      * @return the new AlgorithmParameters object
124      */
125     @Override
engineGenerateParameters()126     protected AlgorithmParameters engineGenerateParameters() {
127         AlgorithmParameters algParams = null;
128         try {
129             if (this.random == null) {
130                 this.random = new SecureRandom();
131             }
132             if (valueL == -1) {
133                 engineInit(DEF_DSA_KEY_SIZE, this.random);
134             }
135             BigInteger[] pAndQ = generatePandQ(this.random, valueL,
136                                                valueN, seedLen);
137             BigInteger paramP = pAndQ[0];
138             BigInteger paramQ = pAndQ[1];
139             BigInteger paramG = generateG(paramP, paramQ);
140 
141             DSAParameterSpec dsaParamSpec =
142                 new DSAParameterSpec(paramP, paramQ, paramG);
143             algParams = AlgorithmParameters.getInstance("DSA", "SUN");
144             algParams.init(dsaParamSpec);
145         } catch (InvalidParameterSpecException e) {
146             // this should never happen
147             throw new RuntimeException(e.getMessage());
148         } catch (NoSuchAlgorithmException e) {
149             // this should never happen, because we provide it
150             throw new RuntimeException(e.getMessage());
151         } catch (NoSuchProviderException e) {
152             // this should never happen, because we provide it
153             throw new RuntimeException(e.getMessage());
154         }
155 
156         return algParams;
157     }
158 
159     /*
160      * Generates the prime and subprime parameters for DSA,
161      * using the provided source of randomness.
162      * This method will generate new seeds until a suitable
163      * seed has been found.
164      *
165      * @param random the source of randomness to generate the
166      * seed
167      * @param valueL the size of <code>p</code>, in bits.
168      * @param valueN the size of <code>q</code>, in bits.
169      * @param seedLen the length of <code>seed</code>, in bits.
170      *
171      * @return an array of BigInteger, with <code>p</code> at index 0 and
172      * <code>q</code> at index 1, the seed at index 2, and the counter value
173      * at index 3.
174      */
generatePandQ(SecureRandom random, int valueL, int valueN, int seedLen)175     private static BigInteger[] generatePandQ(SecureRandom random, int valueL,
176                                               int valueN, int seedLen) {
177         String hashAlg = null;
178         if (valueN == 160) {
179             hashAlg = "SHA";
180         } else if (valueN == 224) {
181             hashAlg = "SHA-224";
182         } else if (valueN == 256) {
183             hashAlg = "SHA-256";
184         }
185         MessageDigest hashObj = null;
186         try {
187             hashObj = MessageDigest.getInstance(hashAlg);
188         } catch (NoSuchAlgorithmException nsae) {
189             // should never happen
190             nsae.printStackTrace();
191         }
192 
193         /* Step 3, 4: Useful variables */
194         int outLen = hashObj.getDigestLength()*8;
195         int n = (valueL - 1) / outLen;
196         int b = (valueL - 1) % outLen;
197         byte[] seedBytes = new byte[seedLen/8];
198         BigInteger twoSl = BigInteger.TWO.pow(seedLen);
199         int primeCertainty = -1;
200         if (valueL <= 1024) {
201             primeCertainty = 80;
202         } else if (valueL == 2048) {
203             primeCertainty = 112;
204         } else if (valueL == 3072) {
205             primeCertainty = 128;
206         }
207         if (primeCertainty < 0) {
208             throw new ProviderException("Invalid valueL: " + valueL);
209         }
210         BigInteger resultP, resultQ, seed = null;
211         int counter;
212         while (true) {
213             do {
214                 /* Step 5 */
215                 random.nextBytes(seedBytes);
216                 seed = new BigInteger(1, seedBytes);
217 
218                 /* Step 6 */
219                 BigInteger U = new BigInteger(1, hashObj.digest(seedBytes)).
220                     mod(BigInteger.TWO.pow(valueN - 1));
221 
222                 /* Step 7 */
223                 resultQ = BigInteger.TWO.pow(valueN - 1)
224                             .add(U)
225                             .add(BigInteger.ONE)
226                             .subtract(U.mod(BigInteger.TWO));
227             } while (!resultQ.isProbablePrime(primeCertainty));
228 
229             /* Step 10 */
230             BigInteger offset = BigInteger.ONE;
231             /* Step 11 */
232             for (counter = 0; counter < 4*valueL; counter++) {
233                 BigInteger[] V = new BigInteger[n + 1];
234                 /* Step 11.1 */
235                 for (int j = 0; j <= n; j++) {
236                     BigInteger J = BigInteger.valueOf(j);
237                     BigInteger tmp = (seed.add(offset).add(J)).mod(twoSl);
238                     byte[] vjBytes = hashObj.digest(toByteArray(tmp));
239                     V[j] = new BigInteger(1, vjBytes);
240                 }
241                 /* Step 11.2 */
242                 BigInteger W = V[0];
243                 for (int i = 1; i < n; i++) {
244                     W = W.add(V[i].multiply(BigInteger.TWO.pow(i * outLen)));
245                 }
246                 W = W.add((V[n].mod(BigInteger.TWO.pow(b)))
247                                .multiply(BigInteger.TWO.pow(n * outLen)));
248                 /* Step 11.3 */
249                 BigInteger twoLm1 = BigInteger.TWO.pow(valueL - 1);
250                 BigInteger X = W.add(twoLm1);
251                 /* Step 11.4, 11.5 */
252                 BigInteger c = X.mod(resultQ.multiply(BigInteger.TWO));
253                 resultP = X.subtract(c.subtract(BigInteger.ONE));
254                 /* Step 11.6, 11.7 */
255                 if (resultP.compareTo(twoLm1) > -1
256                     && resultP.isProbablePrime(primeCertainty)) {
257                     /* Step 11.8 */
258                     BigInteger[] result = {resultP, resultQ, seed,
259                                            BigInteger.valueOf(counter)};
260                     return result;
261                 }
262                 /* Step 11.9 */
263                 offset = offset.add(BigInteger.valueOf(n)).add(BigInteger.ONE);
264              }
265         }
266 
267     }
268 
269     /*
270      * Generates the <code>g</code> parameter for DSA.
271      *
272      * @param p the prime, <code>p</code>.
273      * @param q the subprime, <code>q</code>.
274      *
275      * @param the <code>g</code>
276      */
generateG(BigInteger p, BigInteger q)277     private static BigInteger generateG(BigInteger p, BigInteger q) {
278         BigInteger h = BigInteger.ONE;
279         /* Step 1 */
280         BigInteger pMinusOneOverQ = (p.subtract(BigInteger.ONE)).divide(q);
281         BigInteger resultG = BigInteger.ONE;
282         while (resultG.compareTo(BigInteger.TWO) < 0) {
283             /* Step 3 */
284             resultG = h.modPow(pMinusOneOverQ, p);
285             h = h.add(BigInteger.ONE);
286         }
287         return resultG;
288     }
289 
290     /*
291      * Converts the result of a BigInteger.toByteArray call to an exact
292      * signed magnitude representation for any positive number.
293      */
toByteArray(BigInteger bigInt)294     private static byte[] toByteArray(BigInteger bigInt) {
295         byte[] result = bigInt.toByteArray();
296         if (result[0] == 0) {
297             byte[] tmp = new byte[result.length - 1];
298             System.arraycopy(result, 1, tmp, 0, tmp.length);
299             result = tmp;
300         }
301         return result;
302     }
303 }
304