jdk/src/share/classes/sun/security/provider/DSAParameterGenerator.java

/*
 * Copyright 1997-2006 Sun Microsystems, Inc.  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.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.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];
        }
    }
}