diff options
Diffstat (limited to 'base/util/src/netscape/security/provider/DSAParameterGenerator.java')
-rwxr-xr-x | base/util/src/netscape/security/provider/DSAParameterGenerator.java | 299 |
1 files changed, 299 insertions, 0 deletions
diff --git a/base/util/src/netscape/security/provider/DSAParameterGenerator.java b/base/util/src/netscape/security/provider/DSAParameterGenerator.java new file mode 100755 index 000000000..cd7b8de33 --- /dev/null +++ b/base/util/src/netscape/security/provider/DSAParameterGenerator.java @@ -0,0 +1,299 @@ +// --- BEGIN COPYRIGHT BLOCK --- +// This program is free software; you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation; version 2 of the License. +// +// This program 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 for more details. +// +// You should have received a copy of the GNU General Public License along +// with this program; if not, write to the Free Software Foundation, Inc., +// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +// +// (C) 2007 Red Hat, Inc. +// All rights reserved. +// --- END COPYRIGHT BLOCK --- +package netscape.security.provider; + +import java.math.BigInteger; +import java.security.AlgorithmParameterGeneratorSpi; +import java.security.AlgorithmParameters; +import java.security.InvalidAlgorithmParameterException; +import java.security.InvalidParameterException; +import java.security.NoSuchAlgorithmException; +import java.security.NoSuchProviderException; +import java.security.SecureRandom; +import java.security.spec.AlgorithmParameterSpec; +import java.security.spec.DSAParameterSpec; +import java.security.spec.InvalidParameterSpecException; + +/* + * 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 + * + * @version 1.4, 97/12/10 + * + * @see java.security.AlgorithmParameters + * @see java.security.spec.AlgorithmParameterSpec + * @see DSAParameters + * + * @since JDK1.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(40)) { + 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(15)) { + 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]; + } + } +} |