path: root/base/util/src/netscape/security/provider/DSAParameterGenerator.java

// --- 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];
        }
    }
}