001: /*
002: * @(#)DSAParameterGenerator.java 1.15 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package sun.security.provider;
029:
030: import java.math.BigInteger;
031: import java.security.AlgorithmParameterGeneratorSpi;
032: import java.security.AlgorithmParameters;
033: import java.security.InvalidAlgorithmParameterException;
034: import java.security.NoSuchAlgorithmException;
035: import java.security.NoSuchProviderException;
036: import java.security.InvalidParameterException;
037: import java.security.SecureRandom;
038: import java.security.spec.AlgorithmParameterSpec;
039: import java.security.spec.InvalidParameterSpecException;
040: import java.security.spec.DSAParameterSpec;
041:
042: /*
043: * This class generates parameters for the DSA algorithm. It uses a default
044: * prime modulus size of 1024 bits, which can be overwritten during
045: * initialization.
046: *
047: * @author Jan Luehe
048: *
049: * @version 1.9, 02/02/00
050: *
051: * @see java.security.AlgorithmParameters
052: * @see java.security.spec.AlgorithmParameterSpec
053: * @see DSAParameters
054: *
055: * @since JDK1.2
056: */
057:
058: public class DSAParameterGenerator extends
059: AlgorithmParameterGeneratorSpi {
060:
061: // the modulus length
062: private int modLen = 1024; // default
063:
064: // the source of randomness
065: private SecureRandom random;
066:
067: // useful constants
068: private static final BigInteger ZERO = BigInteger.valueOf(0);
069: private static final BigInteger ONE = BigInteger.valueOf(1);
070: private static final BigInteger TWO = BigInteger.valueOf(2);
071:
072: // Make a SHA-1 hash function
073: private SHA sha;
074:
075: public DSAParameterGenerator() {
076: this .sha = new SHA();
077: }
078:
079: /**
080: * Initializes this parameter generator for a certain strength
081: * and source of randomness.
082: *
083: * @param strength the strength (size of prime) in bits
084: * @param random the source of randomness
085: */
086: protected void engineInit(int strength, SecureRandom random) {
087: /*
088: * Bruce Schneier, "Applied Cryptography", 2nd Edition,
089: * Description of DSA:
090: * [...] The algorithm uses the following parameter:
091: * p=a prime number L bits long, when L ranges from 512 to 1024 and is
092: * a multiple of 64. [...]
093: */
094: if ((strength < 512) || (strength > 1024)
095: || (strength % 64 != 0)) {
096: throw new InvalidParameterException(
097: "Prime size must range from 512 to 1024 "
098: + "and be a multiple of 64");
099: }
100: this .modLen = strength;
101: this .random = random;
102: }
103:
104: /**
105: * Initializes this parameter generator with a set of
106: * algorithm-specific parameter generation values.
107: *
108: * @param params the set of algorithm-specific parameter generation values
109: * @param random the source of randomness
110: *
111: * @exception InvalidAlgorithmParameterException if the given parameter
112: * generation values are inappropriate for this parameter generator
113: */
114: protected void engineInit(AlgorithmParameterSpec genParamSpec,
115: SecureRandom random)
116: throws InvalidAlgorithmParameterException {
117: throw new InvalidAlgorithmParameterException(
118: "Invalid parameter");
119: }
120:
121: /**
122: * Generates the parameters.
123: *
124: * @return the new AlgorithmParameters object
125: */
126: protected AlgorithmParameters engineGenerateParameters() {
127: AlgorithmParameters algParams = null;
128: try {
129: if (this .random == null) {
130: this .random = new SecureRandom();
131: }
132:
133: BigInteger[] pAndQ = generatePandQ(this .random, this .modLen);
134: BigInteger paramP = pAndQ[0];
135: BigInteger paramQ = pAndQ[1];
136: BigInteger paramG = generateG(paramP, paramQ);
137:
138: DSAParameterSpec dsaParamSpec = new DSAParameterSpec(
139: paramP, paramQ, paramG);
140: algParams = AlgorithmParameters.getInstance("DSA", "SUN");
141: algParams.init(dsaParamSpec);
142: } catch (InvalidParameterSpecException e) {
143: // this should never happen
144: throw new RuntimeException(e.getMessage());
145: } catch (NoSuchAlgorithmException e) {
146: // this should never happen, because we provide it
147: throw new RuntimeException(e.getMessage());
148: } catch (NoSuchProviderException e) {
149: // this should never happen, because we provide it
150: throw new RuntimeException(e.getMessage());
151: }
152:
153: return algParams;
154: }
155:
156: /*
157: * Generates the prime and subprime parameters for DSA,
158: * using the provided source of randomness.
159: * This method will generate new seeds until a suitable
160: * seed has been found.
161: *
162: * @param random the source of randomness to generate the
163: * seed
164: * @param L the size of <code>p</code>, in bits.
165: *
166: * @return an array of BigInteger, with <code>p</code> at index 0 and
167: * <code>q</code> at index 1.
168: */
169: BigInteger[] generatePandQ(SecureRandom random, int L) {
170: BigInteger[] result = null;
171: byte[] seed = new byte[20];
172:
173: while (result == null) {
174: for (int i = 0; i < 20; i++) {
175: seed[i] = (byte) random.nextInt();
176: }
177: result = generatePandQ(seed, L);
178: }
179: return result;
180: }
181:
182: /*
183: * Generates the prime and subprime parameters for DSA.
184: *
185: * <p>The seed parameter corresponds to the <code>SEED</code> parameter
186: * referenced in the FIPS specification of the DSA algorithm,
187: * and L is the size of <code>p</code>, in bits.
188: *
189: * @param seed the seed to generate the parameters
190: * @param L the size of <code>p</code>, in bits.
191: *
192: * @return an array of BigInteger, with <code>p</code> at index 0,
193: * <code>q</code> at index 1, the seed at index 2, and the counter value
194: * at index 3, or null if the seed does not yield suitable numbers.
195: */
196: BigInteger[] generatePandQ(byte[] seed, int L) {
197:
198: /* Useful variables */
199: int g = seed.length * 8;
200: int n = (L - 1) / 160;
201: int b = (L - 1) % 160;
202:
203: BigInteger SEED = new BigInteger(1, seed);
204: BigInteger TWOG = TWO.pow(2 * g);
205:
206: /* Step 2 (Step 1 is getting seed). */
207: byte[] U1 = SHA(seed);
208: byte[] U2 = SHA(toByteArray((SEED.add(ONE)).mod(TWOG)));
209:
210: xor(U1, U2);
211: byte[] U = U1;
212:
213: /* Step 3: For q by setting the msb and lsb to 1 */
214: U[0] |= 0x80;
215: U[19] |= 1;
216: BigInteger q = new BigInteger(1, U);
217:
218: /* Step 5 */
219: if (!q.isProbablePrime(80)) {
220: return null;
221:
222: } else {
223: BigInteger V[] = new BigInteger[n + 1];
224: BigInteger offset = TWO;
225:
226: /* Step 6 */
227: for (int counter = 0; counter < 4096; counter++) {
228:
229: /* Step 7 */
230: for (int k = 0; k <= n; k++) {
231: BigInteger K = BigInteger.valueOf(k);
232: BigInteger tmp = (SEED.add(offset).add(K))
233: .mod(TWOG);
234: V[k] = new BigInteger(1, SHA(toByteArray(tmp)));
235: }
236:
237: /* Step 8 */
238: BigInteger W = V[0];
239: for (int i = 1; i < n; i++) {
240: W = W.add(V[i].multiply(TWO.pow(i * 160)));
241: }
242: W = W.add((V[n].mod(TWO.pow(b))).multiply(TWO
243: .pow(n * 160)));
244:
245: BigInteger TWOLm1 = TWO.pow(L - 1);
246: BigInteger X = W.add(TWOLm1);
247:
248: /* Step 9 */
249: BigInteger c = X.mod(q.multiply(TWO));
250: BigInteger p = X.subtract(c.subtract(ONE));
251:
252: /* Step 10 - 13 */
253: if (p.compareTo(TWOLm1) > -1 && p.isProbablePrime(80)) {
254: BigInteger[] result = { p, q, SEED,
255: BigInteger.valueOf(counter) };
256: return result;
257: }
258: offset = offset.add(BigInteger.valueOf(n)).add(ONE);
259: }
260: return null;
261: }
262: }
263:
264: /*
265: * Generates the <code>g</code> parameter for DSA.
266: *
267: * @param p the prime, <code>p</code>.
268: * @param q the subprime, <code>q</code>.
269: *
270: * @param the <code>g</code>
271: */
272: BigInteger generateG(BigInteger p, BigInteger q) {
273: BigInteger h = ONE;
274: BigInteger pMinusOneOverQ = (p.subtract(ONE)).divide(q);
275: BigInteger g = ONE;
276: while (g.compareTo(TWO) < 0) {
277: g = h.modPow(pMinusOneOverQ, p);
278: h = h.add(ONE);
279: }
280: return g;
281: }
282:
283: /*
284: * Returns the SHA-1 digest of some data
285: */
286: private byte[] SHA(byte[] array) {
287: sha.engineReset();
288: sha.engineUpdate(array, 0, array.length);
289: return sha.engineDigest();
290: }
291:
292: /*
293: * Converts the result of a BigInteger.toByteArray call to an exact
294: * signed magnitude representation for any positive number.
295: */
296: private byte[] toByteArray(BigInteger bigInt) {
297: byte[] result = bigInt.toByteArray();
298: if (result[0] == 0) {
299: byte[] tmp = new byte[result.length - 1];
300: System.arraycopy(result, 1, tmp, 0, tmp.length);
301: result = tmp;
302: }
303: return result;
304: }
305:
306: /*
307: * XORs U2 into U1
308: */
309: private void xor(byte[] U1, byte[] U2) {
310: for (int i = 0; i < U1.length; i++) {
311: U1[i] ^= U2[i];
312: }
313: }
314: }
|