/*
* Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package sun.security.provider;
import java.math.BigInteger;
import java.security.AlgorithmParameterGeneratorSpi;
import java.security.AlgorithmParameters;
import java.security.InvalidAlgorithmParameterException;
import java.security.NoSuchAlgorithmException;
import java.security.NoSuchProviderException;
import java.security.InvalidParameterException;
import java.security.SecureRandom;
import java.security.spec.AlgorithmParameterSpec;
import java.security.spec.InvalidParameterSpecException;
import java.security.spec.DSAParameterSpec;
/**
* This class generates parameters for the DSA algorithm. It uses a default
* prime modulus size of 1024 bits, which can be overwritten during
* initialization.
*
* @author Jan Luehe
*
*
* @see java.security.AlgorithmParameters
* @see java.security.spec.AlgorithmParameterSpec
* @see DSAParameters
*
* @since 1.2
*/
public class DSAParameterGenerator extends AlgorithmParameterGeneratorSpi {
// the modulus length
private int modLen = 1024; // default
// the source of randomness
private SecureRandom random;
// useful constants
private static final BigInteger ZERO = BigInteger.valueOf(0);
private static final BigInteger ONE = BigInteger.valueOf(1);
private static final BigInteger TWO = BigInteger.valueOf(2);
// Make a SHA-1 hash function
private SHA sha;
public DSAParameterGenerator() {
this.sha = new SHA();
}
/**
* Initializes this parameter generator for a certain strength
* and source of randomness.
*
* @param strength the strength (size of prime) in bits
* @param random the source of randomness
*/
protected void engineInit(int strength, SecureRandom random) {
/*
* Bruce Schneier, "Applied Cryptography", 2nd Edition,
* Description of DSA:
* [...] The algorithm uses the following parameter:
* p=a prime number L bits long, when L ranges from 512 to 1024 and is
* a multiple of 64. [...]
*/
if ((strength < 512) || (strength > 1024) || (strength % 64 != 0)) {
throw new InvalidParameterException
("Prime size must range from 512 to 1024 "
+ "and be a multiple of 64");
}
this.modLen = strength;
this.random = random;
}
/**
* Initializes this parameter generator with a set of
* algorithm-specific parameter generation values.
*
* @param params the set of algorithm-specific parameter generation values
* @param random the source of randomness
*
* @exception InvalidAlgorithmParameterException if the given parameter
* generation values are inappropriate for this parameter generator
*/
protected void engineInit(AlgorithmParameterSpec genParamSpec,
SecureRandom random)
throws InvalidAlgorithmParameterException {
throw new InvalidAlgorithmParameterException("Invalid parameter");
}
/**
* Generates the parameters.
*
* @return the new AlgorithmParameters object
*/
protected AlgorithmParameters engineGenerateParameters() {
AlgorithmParameters algParams = null;
try {
if (this.random == null) {
this.random = new SecureRandom();
}
BigInteger[] pAndQ = generatePandQ(this.random, this.modLen);
BigInteger paramP = pAndQ[0];
BigInteger paramQ = pAndQ[1];
BigInteger paramG = generateG(paramP, paramQ);
DSAParameterSpec dsaParamSpec = new DSAParameterSpec(paramP,
paramQ,
paramG);
algParams = AlgorithmParameters.getInstance("DSA", "SUN");
algParams.init(dsaParamSpec);
} catch (InvalidParameterSpecException e) {
// this should never happen
throw new RuntimeException(e.getMessage());
} catch (NoSuchAlgorithmException e) {
// this should never happen, because we provide it
throw new RuntimeException(e.getMessage());
} catch (NoSuchProviderException e) {
// this should never happen, because we provide it
throw new RuntimeException(e.getMessage());
}
return algParams;
}
/*
* Generates the prime and subprime parameters for DSA,
* using the provided source of randomness.
* This method will generate new seeds until a suitable
* seed has been found.
*
* @param random the source of randomness to generate the
* seed
* @param L the size of <code>p</code>, in bits.
*
* @return an array of BigInteger, with <code>p</code> at index 0 and
* <code>q</code> at index 1.
*/
BigInteger[] generatePandQ(SecureRandom random, int L) {
BigInteger[] result = null;
byte[] seed = new byte[20];
while(result == null) {
for (int i = 0; i < 20; i++) {
seed[i] = (byte)random.nextInt();
}
result = generatePandQ(seed, L);
}
return result;
}
/*
* Generates the prime and subprime parameters for DSA.
*
* <p>The seed parameter corresponds to the <code>SEED</code> parameter
* referenced in the FIPS specification of the DSA algorithm,
* and L is the size of <code>p</code>, in bits.
*
* @param seed the seed to generate the parameters
* @param L the size of <code>p</code>, in bits.
*
* @return an array of BigInteger, with <code>p</code> at index 0,
* <code>q</code> at index 1, the seed at index 2, and the counter value
* at index 3, or null if the seed does not yield suitable numbers.
*/
BigInteger[] generatePandQ(byte[] seed, int L) {
/* Useful variables */
int g = seed.length * 8;
int n = (L - 1) / 160;
int b = (L - 1) % 160;
BigInteger SEED = new BigInteger(1, seed);
BigInteger TWOG = TWO.pow(2 * g);
/* Step 2 (Step 1 is getting seed). */
byte[] U1 = SHA(seed);
byte[] U2 = SHA(toByteArray((SEED.add(ONE)).mod(TWOG)));
xor(U1, U2);
byte[] U = U1;
/* Step 3: For q by setting the msb and lsb to 1 */
U[0] |= 0x80;
U[19] |= 1;
BigInteger q = new BigInteger(1, U);
/* Step 5 */
if (!q.isProbablePrime(80)) {
return null;
} else {
BigInteger V[] = new BigInteger[n + 1];
BigInteger offset = TWO;
/* Step 6 */
for (int counter = 0; counter < 4096; counter++) {
/* Step 7 */
for (int k = 0; k <= n; k++) {
BigInteger K = BigInteger.valueOf(k);
BigInteger tmp = (SEED.add(offset).add(K)).mod(TWOG);
V[k] = new BigInteger(1, SHA(toByteArray(tmp)));
}
/* Step 8 */
BigInteger W = V[0];
for (int i = 1; i < n; i++) {
W = W.add(V[i].multiply(TWO.pow(i * 160)));
}
W = W.add((V[n].mod(TWO.pow(b))).multiply(TWO.pow(n * 160)));
BigInteger TWOLm1 = TWO.pow(L - 1);
BigInteger X = W.add(TWOLm1);
/* Step 9 */
BigInteger c = X.mod(q.multiply(TWO));
BigInteger p = X.subtract(c.subtract(ONE));
/* Step 10 - 13 */
if (p.compareTo(TWOLm1) > -1 && p.isProbablePrime(80)) {
BigInteger[] result = {p, q, SEED,
BigInteger.valueOf(counter)};
return result;
}
offset = offset.add(BigInteger.valueOf(n)).add(ONE);
}
return null;
}
}
/*
* Generates the <code>g</code> parameter for DSA.
*
* @param p the prime, <code>p</code>.
* @param q the subprime, <code>q</code>.
*
* @param the <code>g</code>
*/
BigInteger generateG(BigInteger p, BigInteger q) {
BigInteger h = ONE;
BigInteger pMinusOneOverQ = (p.subtract(ONE)).divide(q);
BigInteger g = ONE;
while (g.compareTo(TWO) < 0) {
g = h.modPow(pMinusOneOverQ, p);
h = h.add(ONE);
}
return g;
}
/*
* Returns the SHA-1 digest of some data
*/
private byte[] SHA(byte[] array) {
sha.engineReset();
sha.engineUpdate(array, 0, array.length);
return sha.engineDigest();
}
/*
* Converts the result of a BigInteger.toByteArray call to an exact
* signed magnitude representation for any positive number.
*/
private byte[] toByteArray(BigInteger bigInt) {
byte[] result = bigInt.toByteArray();
if (result[0] == 0) {
byte[] tmp = new byte[result.length - 1];
System.arraycopy(result, 1, tmp, 0, tmp.length);
result = tmp;
}
return result;
}
/*
* XORs U2 into U1
*/
private void xor(byte[] U1, byte[] U2) {
for (int i = 0; i < U1.length; i++) {
U1[i] ^= U2[i];
}
}
}