/*

 * 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];

        }

    }

}