001: /*
002: * @(#)DSA.java 1.94 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.io.*;
031: import java.util.*;
032: import java.math.BigInteger;
033: import java.security.AlgorithmParameters;
034: import java.security.InvalidAlgorithmParameterException;
035: import java.security.InvalidKeyException;
036: import java.security.InvalidParameterException;
037: import java.security.MessageDigest;
038: import java.security.NoSuchAlgorithmException;
039: import java.security.PublicKey;
040: import java.security.PrivateKey;
041: import java.security.SecureRandom;
042: import java.security.Signature;
043: import java.security.SignatureException;
044: import java.security.interfaces.*;
045: import java.security.spec.DSAParameterSpec;
046: import java.security.spec.InvalidParameterSpecException;
047: import sun.security.util.Debug;
048: import sun.security.util.DerValue;
049: import sun.security.util.DerInputStream;
050: import sun.security.util.DerOutputStream;
051: import sun.security.x509.AlgIdDSA;
052:
053: /**
054: * The Digital Signature Standard (using the Digital Signature
055: * Algorithm), as described in fips186 of the National Instute of
056: * Standards and Technology (NIST), using fips180-1 (SHA-1).
057: *
058: * @author Benjamin Renaud
059: *
060: * @version 1.88, 02/02/00
061: *
062: * @see DSAPublicKey
063: * @see DSAPrivateKey
064: */
065:
066: public final class DSA extends Signature {
067:
068: /* Are we debugging? */
069: private static final boolean debug = false;
070:
071: /* The parameter object */
072: private DSAParams params;
073:
074: /* algorithm parameters */
075: private BigInteger presetP, presetQ, presetG;
076:
077: /* The public key, if any */
078: private BigInteger presetY;
079:
080: /* The private key, if any */
081: private BigInteger presetX;
082:
083: /* The SHA hash for the data */
084: private MessageDigest dataSHA;
085:
086: /* The random seed used to generate k */
087: private int[] Kseed;
088:
089: /* The random seed used to generate k (specified by application) */
090: private byte[] KseedAsByteArray;
091:
092: /*
093: * The random seed used to generate k
094: * (prevent the same Kseed from being used twice in a row
095: */
096: private int[] previousKseed;
097:
098: /* The RNG used to output a seed for generating k */
099: private SecureRandom signingRandom;
100:
101: /**
102: * Construct a blank DSA object. It can generate keys, but must be
103: * initialized before being usable for signing or verifying.
104: */
105: public DSA() throws NoSuchAlgorithmException {
106: super ("SHA1withDSA");
107: dataSHA = MessageDigest.getInstance("SHA");
108: }
109:
110: /**
111: * Initialize the DSA object with a DSA private key.
112: *
113: * @param privateKey the DSA private key
114: *
115: * @exception InvalidKeyException if the key is not a valid DSA private
116: * key.
117: */
118: protected void engineInitSign(PrivateKey privateKey)
119: throws InvalidKeyException {
120: if (!(privateKey instanceof java.security.interfaces.DSAPrivateKey)) {
121: throw new InvalidKeyException("not a DSA private key: "
122: + privateKey);
123: }
124: java.security.interfaces.DSAPrivateKey priv = (java.security.interfaces.DSAPrivateKey) privateKey;
125: this .presetX = priv.getX();
126: initialize(priv.getParams());
127: }
128:
129: /**
130: * Initialize the DSA object with a DSA public key.
131: *
132: * @param publicKey the DSA public key.
133: *
134: * @exception InvalidKeyException if the key is not a valid DSA public
135: * key.
136: */
137: protected void engineInitVerify(PublicKey publicKey)
138: throws InvalidKeyException {
139: if (!(publicKey instanceof java.security.interfaces.DSAPublicKey)) {
140: throw new InvalidKeyException("not a DSA public key: "
141: + publicKey);
142: }
143: java.security.interfaces.DSAPublicKey pub = (java.security.interfaces.DSAPublicKey) publicKey;
144: this .presetY = pub.getY();
145: initialize(pub.getParams());
146: }
147:
148: private void initialize(DSAParams params)
149: throws InvalidKeyException {
150: dataSHA.reset();
151: setParams(params);
152: }
153:
154: /**
155: * Sign all the data thus far updated. The signature is formatted
156: * according to the Canonical Encoding Rules, returned as a DER
157: * sequence of Integer, r and s.
158: *
159: * @return a signature block formatted according to the Canonical
160: * Encoding Rules.
161: *
162: * @exception SignatureException if the signature object was not
163: * properly initialized, or if another exception occurs.
164: *
165: * @see sun.security.DSA#engineUpdate
166: * @see sun.security.DSA#engineVerify
167: */
168: protected byte[] engineSign() throws SignatureException {
169: BigInteger k = generateK(presetQ);
170: BigInteger r = generateR(presetP, presetQ, presetG, k);
171: BigInteger s = generateS(presetX, presetQ, r, k);
172:
173: try {
174: DerOutputStream outseq = new DerOutputStream(100);
175: outseq.putInteger(r);
176: outseq.putInteger(s);
177: DerValue result = new DerValue(DerValue.tag_Sequence,
178: outseq.toByteArray());
179:
180: return result.toByteArray();
181:
182: } catch (IOException e) {
183: throw new SignatureException("error encoding signature");
184: }
185: }
186:
187: /**
188: * Verify all the data thus far updated.
189: *
190: * @param signature the alledged signature, encoded using the
191: * Canonical Encoding Rules, as a sequence of integers, r and s.
192: *
193: * @exception SignatureException if the signature object was not
194: * properly initialized, or if another exception occurs.
195: *
196: * @see sun.security.DSA#engineUpdate
197: * @see sun.security.DSA#engineSign
198: */
199: protected boolean engineVerify(byte[] signature)
200: throws SignatureException {
201: return engineVerify(signature, 0, signature.length);
202: }
203:
204: /**
205: * Verify all the data thus far updated.
206: *
207: * @param signature the alledged signature, encoded using the
208: * Canonical Encoding Rules, as a sequence of integers, r and s.
209: *
210: * @param offset the offset to start from in the array of bytes.
211: *
212: * @param length the number of bytes to use, starting at offset.
213: *
214: * @exception SignatureException if the signature object was not
215: * properly initialized, or if another exception occurs.
216: *
217: * @see sun.security.DSA#engineUpdate
218: * @see sun.security.DSA#engineSign
219: */
220:
221: protected boolean engineVerify(byte[] signature, int offset,
222: int length) throws SignatureException {
223:
224: BigInteger r = null;
225: BigInteger s = null;
226: // first decode the signature.
227: try {
228: DerInputStream in = new DerInputStream(signature, offset,
229: length);
230: DerValue[] values = in.getSequence(2);
231:
232: r = values[0].getBigInteger();
233: s = values[1].getBigInteger();
234:
235: } catch (IOException e) {
236: throw new SignatureException(
237: "invalid encoding for signature");
238: }
239:
240: if ((r.compareTo(BigInteger.ZERO) == 1)
241: && (r.compareTo(presetQ) == -1)
242: && (s.compareTo(BigInteger.ZERO) == 1)
243: && (s.compareTo(presetQ) == -1)) {
244: BigInteger w = generateW(presetP, presetQ, presetG, s);
245: BigInteger v = generateV(presetY, presetP, presetQ,
246: presetG, w, r);
247:
248: return v.equals(r);
249: } else {
250: throw new SignatureException(
251: "invalid signature: out of range values");
252: }
253: }
254:
255: private void reset() {
256: dataSHA.reset();
257: }
258:
259: BigInteger generateR(BigInteger p, BigInteger q, BigInteger g,
260: BigInteger k) {
261: BigInteger temp = g.modPow(k, p);
262: return temp.remainder(q);
263:
264: }
265:
266: BigInteger generateS(BigInteger x, BigInteger q, BigInteger r,
267: BigInteger k) {
268:
269: byte[] s2 = dataSHA.digest();
270: BigInteger temp = new BigInteger(1, s2);
271: BigInteger k1 = k.modInverse(q);
272:
273: BigInteger s = x.multiply(r);
274: s = temp.add(s);
275: s = k1.multiply(s);
276: return s.remainder(q);
277: }
278:
279: BigInteger generateW(BigInteger p, BigInteger q, BigInteger g,
280: BigInteger s) {
281: return s.modInverse(q);
282: }
283:
284: BigInteger generateV(BigInteger y, BigInteger p, BigInteger q,
285: BigInteger g, BigInteger w, BigInteger r) {
286:
287: byte[] s2 = dataSHA.digest();
288: BigInteger temp = new BigInteger(1, s2);
289:
290: temp = temp.multiply(w);
291: BigInteger u1 = temp.remainder(q);
292:
293: BigInteger u2 = (r.multiply(w)).remainder(q);
294:
295: BigInteger t1 = g.modPow(u1, p);
296: BigInteger t2 = y.modPow(u2, p);
297: BigInteger t3 = t1.multiply(t2);
298: BigInteger t5 = t3.remainder(p);
299: return t5.remainder(q);
300: }
301:
302: /*
303: * Please read bug report 4044247 for an alternative, faster,
304: * NON-FIPS approved method to generate K
305: */
306: BigInteger generateK(BigInteger q) {
307:
308: BigInteger k = null;
309:
310: // The application specified a Kseed for us to use.
311: // Note that we do not allow usage of the same Kseed twice in a row
312: if (Kseed != null && !Arrays.equals(Kseed, previousKseed)) {
313: k = generateK(Kseed, q);
314: if (k.signum() > 0 && k.compareTo(q) < 0) {
315: previousKseed = new int[Kseed.length];
316: System.arraycopy(Kseed, 0, previousKseed, 0,
317: Kseed.length);
318: return k;
319: }
320: }
321:
322: // The application did not specify a Kseed for us to use.
323: // We'll generate a new Kseed by getting random bytes from
324: // a SecureRandom object.
325: SecureRandom random = getSigningRandom();
326:
327: while (true) {
328: int[] seed = new int[5];
329:
330: for (int i = 0; i < 5; i++)
331: seed[i] = random.nextInt();
332: k = generateK(seed, q);
333: if (k.signum() > 0 && k.compareTo(q) < 0) {
334: previousKseed = new int[seed.length];
335: System
336: .arraycopy(seed, 0, previousKseed, 0,
337: seed.length);
338: return k;
339: }
340: }
341: }
342:
343: // Use the application-specified SecureRandom Object if provided.
344: // Otherwise, use our default SecureRandom Object.
345: private SecureRandom getSigningRandom() {
346: if (signingRandom == null) {
347: if (appRandom != null)
348: signingRandom = appRandom;
349: else
350: signingRandom = new SecureRandom();
351: }
352: return signingRandom;
353: }
354:
355: /**
356: * Compute k for a DSA signature.
357: *
358: * @param seed the seed for generating k. This seed should be
359: * secure. This is what is refered to as the KSEED in the DSA
360: * specification.
361: *
362: * @param g the g parameter from the DSA key pair.
363: */
364: BigInteger generateK(int[] seed, BigInteger q) {
365:
366: // check out t in the spec.
367: int[] t = { 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0,
368: 0x67452301 };
369: //
370: int[] tmp = DSA.SHA_7(seed, t);
371: byte[] tmpBytes = new byte[tmp.length * 4];
372: for (int i = 0; i < tmp.length; i++) {
373: int k = tmp[i];
374: for (int j = 0; j < 4; j++) {
375: tmpBytes[(i * 4) + j] = (byte) (k >>> (24 - (j * 8)));
376: }
377: }
378: BigInteger k = new BigInteger(1, tmpBytes).mod(q);
379: return k;
380: }
381:
382: // Constants for each round
383: private static final int round1_kt = 0x5a827999;
384: private static final int round2_kt = 0x6ed9eba1;
385: private static final int round3_kt = 0x8f1bbcdc;
386: private static final int round4_kt = 0xca62c1d6;
387:
388: /**
389: * Computes set 1 thru 7 of SHA-1 on m1. */
390: static int[] SHA_7(int[] m1, int[] h) {
391:
392: int[] W = new int[80];
393: System.arraycopy(m1, 0, W, 0, m1.length);
394: int temp = 0;
395:
396: for (int t = 16; t <= 79; t++) {
397: temp = W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16];
398: W[t] = ((temp << 1) | (temp >>> (32 - 1)));
399: }
400:
401: int a = h[0], b = h[1], c = h[2], d = h[3], e = h[4];
402: for (int i = 0; i < 20; i++) {
403: temp = ((a << 5) | (a >>> (32 - 5)))
404: + ((b & c) | ((~b) & d)) + e + W[i] + round1_kt;
405: e = d;
406: d = c;
407: c = ((b << 30) | (b >>> (32 - 30)));
408: b = a;
409: a = temp;
410: }
411:
412: // Round 2
413: for (int i = 20; i < 40; i++) {
414: temp = ((a << 5) | (a >>> (32 - 5))) + (b ^ c ^ d) + e
415: + W[i] + round2_kt;
416: e = d;
417: d = c;
418: c = ((b << 30) | (b >>> (32 - 30)));
419: b = a;
420: a = temp;
421: }
422:
423: // Round 3
424: for (int i = 40; i < 60; i++) {
425: temp = ((a << 5) | (a >>> (32 - 5)))
426: + ((b & c) | (b & d) | (c & d)) + e + W[i]
427: + round3_kt;
428: e = d;
429: d = c;
430: c = ((b << 30) | (b >>> (32 - 30)));
431: b = a;
432: a = temp;
433: }
434:
435: // Round 4
436: for (int i = 60; i < 80; i++) {
437: temp = ((a << 5) | (a >>> (32 - 5))) + (b ^ c ^ d) + e
438: + W[i] + round4_kt;
439: e = d;
440: d = c;
441: c = ((b << 30) | (b >>> (32 - 30)));
442: b = a;
443: a = temp;
444: }
445: int[] md = new int[5];
446: md[0] = h[0] + a;
447: md[1] = h[1] + b;
448: md[2] = h[2] + c;
449: md[3] = h[3] + d;
450: md[4] = h[4] + e;
451: return md;
452: }
453:
454: /**
455: * This implementation recognizes the following parameter:<dl>
456: *
457: * <dt><tt>Kseed</tt>
458: *
459: * <dd>a byte array.
460: *
461: * </dl>
462: *
463: * @deprecated
464: */
465: protected void engineSetParameter(String key, Object param) {
466:
467: if (key.equals("KSEED")) {
468:
469: if (param instanceof byte[]) {
470:
471: Kseed = byteArray2IntArray((byte[]) param);
472: KseedAsByteArray = (byte[]) param;
473:
474: } else {
475: debug("unrecognized param: " + key);
476: throw new InvalidParameterException(
477: "Kseed not a byte array");
478: }
479:
480: } else {
481: throw new InvalidParameterException("invalid parameter");
482: }
483: }
484:
485: /**
486: * Return the value of the requested parameter. Recognized
487: * parameters are:
488: *
489: * <dl>
490: *
491: * <dt><tt>Kseed</tt>
492: *
493: * <dd>a byte array.
494: *
495: * </dl>
496: *
497: * @return the value of the requested parameter.
498: *
499: * @see java.security.SignatureEngine
500: *
501: * @deprecated
502: */
503: protected Object engineGetParameter(String key) {
504: if (key.equals("KSEED")) {
505: return KseedAsByteArray;
506: } else {
507: return null;
508: }
509: }
510:
511: /**
512: * Set the algorithm object.
513: */
514: private void setParams(DSAParams params) throws InvalidKeyException {
515: if (params == null)
516: throw new InvalidKeyException(
517: "DSA public key lacks parameters");
518: this .params = params;
519: this .presetP = params.getP();
520: this .presetQ = params.getQ();
521: this .presetG = params.getG();
522: }
523:
524: /**
525: * Update a byte to be signed or verified.
526: *
527: * @param b the byte to updated.
528: */
529: protected void engineUpdate(byte b) {
530: dataSHA.update(b);
531: }
532:
533: /**
534: * Update an array of bytes to be signed or verified.
535: *
536: * @param data the bytes to be updated.
537: */
538: protected void engineUpdate(byte[] data, int off, int len) {
539: dataSHA.update(data, off, len);
540: }
541:
542: /**
543: * Return a human readable rendition of the engine.
544: */
545: public String toString() {
546: String printable = "DSA Signature";
547: if (presetP != null && presetQ != null && presetG != null) {
548: printable += "\n\tp: " + Debug.toHexString(presetP);
549: printable += "\n\tq: " + Debug.toHexString(presetQ);
550: printable += "\n\tg: " + Debug.toHexString(presetG);
551: } else {
552: printable += "\n\t P, Q or G not initialized.";
553: }
554: if (presetY != null) {
555: printable += "\n\ty: " + Debug.toHexString(presetY);
556: }
557: if (presetY == null && presetX == null) {
558: printable += "\n\tUNINIIALIZED";
559: }
560: return printable;
561: }
562:
563: /*
564: * Utility routine for converting a byte array into an int array
565: */
566: private int[] byteArray2IntArray(byte[] byteArray) {
567:
568: int j = 0;
569: byte[] newBA;
570: int mod = byteArray.length % 4;
571:
572: // guarantee that the incoming byteArray is a multiple of 4
573: // (pad with 0's)
574: switch (mod) {
575: case 3:
576: newBA = new byte[byteArray.length + 1];
577: break;
578: case 2:
579: newBA = new byte[byteArray.length + 2];
580: break;
581: case 1:
582: newBA = new byte[byteArray.length + 3];
583: break;
584: default:
585: newBA = new byte[byteArray.length + 0];
586: break;
587: }
588: System.arraycopy(byteArray, 0, newBA, 0, byteArray.length);
589:
590: // copy each set of 4 bytes in the byte array into an integer
591: int[] newSeed = new int[newBA.length / 4];
592: for (int i = 0; i < newBA.length; i += 4) {
593: newSeed[j] = newBA[i + 3] & 0xFF;
594: newSeed[j] |= (newBA[i + 2] << 8) & 0xFF00;
595: newSeed[j] |= (newBA[i + 1] << 16) & 0xFF0000;
596: newSeed[j] |= (newBA[i + 0] << 24) & 0xFF000000;
597: j++;
598: }
599:
600: return newSeed;
601: }
602:
603: private static void debug(Exception e) {
604: if (debug) {
605: e.printStackTrace();
606: }
607: }
608:
609: private static void debug(String s) {
610: if (debug) {
611: System.err.println(s);
612: }
613: }
614: }
|