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