diff options
Diffstat (limited to 'base/util/src/netscape/security/provider/DSA.java')
-rw-r--r-- | base/util/src/netscape/security/provider/DSA.java | 660 |
1 files changed, 660 insertions, 0 deletions
diff --git a/base/util/src/netscape/security/provider/DSA.java b/base/util/src/netscape/security/provider/DSA.java new file mode 100644 index 000000000..262095576 --- /dev/null +++ b/base/util/src/netscape/security/provider/DSA.java @@ -0,0 +1,660 @@ +// --- 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.io.IOException; +import java.io.PrintStream; +import java.math.BigInteger; +import java.security.InvalidKeyException; +import java.security.InvalidParameterException; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.security.PrivateKey; +import java.security.PublicKey; +import java.security.SecureRandom; +import java.security.Signature; +import java.security.SignatureException; +import java.security.interfaces.DSAParams; + +import netscape.security.util.BigInt; +import netscape.security.util.DerInputStream; +import netscape.security.util.DerOutputStream; +import netscape.security.util.DerValue; + +/** + * The Digital Signature Standard (using the Digital Signature + * Algorithm), as described in fips186 of the National Instute of + * Standards and Technology (NIST), using fips180-1 (SHA-1). + * + * @author Benjamin Renaud + * + * @version 1.86, 97/09/17 + * + * @see DSAPublicKey + * @see DSAPrivateKey + */ + +public final class DSA extends Signature { + + /* Are we debugging? */ + private static boolean debug = false; + + /* The parameter object */ + private DSAParams params; + + /* algorithm parameters */ + private BigInteger presetP, presetQ, presetG; + + /* The public key, if any */ + private BigInteger presetY; + + /* The private key, if any */ + private BigInteger presetX; + + /* The SHA hash for the data */ + private MessageDigest dataSHA; + + /* The random seed used to generate k */ + private int[] Kseed; + + /* The random seed used to generate k (specified by application) */ + private byte[] KseedAsByteArray; + + /* + * The random seed used to generate k + * (prevent the same Kseed from being used twice in a row + */ + private int[] previousKseed; + + /* The RNG used to output a seed for generating k */ + private SecureRandom signingRandom; + + /** + * Construct a blank DSA object. It can generate keys, but must be + * initialized before being usable for signing or verifying. + */ + public DSA() throws NoSuchAlgorithmException { + super("SHA/DSA"); + dataSHA = MessageDigest.getInstance("SHA"); + } + + /** + * Initialize the DSA object with a DSA private key. + * + * @param privateKey the DSA private key + * + * @exception InvalidKeyException if the key is not a valid DSA private + * key. + */ + protected void engineInitSign(PrivateKey privateKey) + throws InvalidKeyException { + if (!(privateKey instanceof java.security.interfaces.DSAPrivateKey)) { + throw new InvalidKeyException("not a DSA private key: " + + privateKey); + } + java.security.interfaces.DSAPrivateKey priv = + (java.security.interfaces.DSAPrivateKey) privateKey; + + this.presetX = priv.getX(); + initialize(priv.getParams()); + } + + /** + * Initialize the DSA object with a DSA public key. + * + * @param publicKey the DSA public key. + * + * @exception InvalidKeyException if the key is not a valid DSA public + * key. + */ + protected void engineInitVerify(PublicKey publicKey) + throws InvalidKeyException { + if (!(publicKey instanceof java.security.interfaces.DSAPublicKey)) { + throw new InvalidKeyException("not a DSA public key: " + + publicKey); + } + java.security.interfaces.DSAPublicKey pub = + (java.security.interfaces.DSAPublicKey) publicKey; + this.presetY = pub.getY(); + initialize(pub.getParams()); + } + + private void initialize(DSAParams params) { + dataSHA.reset(); + setParams(params); + } + + /** + * Sign all the data thus far updated. The signature is formatted + * according to the Canonical Encoding Rules, returned as a DER + * sequence of Integer, r and s. + * + * @return a signature block formatted according to the Canonical + * Encoding Rules. + * + * @exception SignatureException if the signature object was not + * properly initialized, or if another exception occurs. + * + * @see netscape.security.provider.DSA#engineUpdate + * @see netscape.security.provider.DSA#engineVerify + */ + protected byte[] engineSign() throws SignatureException { + BigInteger k = generateK(presetQ); + BigInteger r = generateR(presetP, presetQ, presetG, k); + BigInteger s = generateS(presetX, presetQ, r, k); + + // got to convert to BigInt... + BigInt rAsBigInt = new BigInt(r.toByteArray()); + BigInt sAsBigInt = new BigInt(s.toByteArray()); + + try { + DerOutputStream outseq = new DerOutputStream(100); + outseq.putInteger(rAsBigInt); + outseq.putInteger(sAsBigInt); + DerValue result = new DerValue(DerValue.tag_Sequence, + outseq.toByteArray()); + + return result.toByteArray(); + + } catch (IOException e) { + throw new SignatureException("error encoding signature"); + } + } + + /** + * Verify all the data thus far updated. + * + * @param signature the alledged signature, encoded using the + * Canonical Encoding Rules, as a sequence of integers, r and s. + * + * @exception SignatureException if the signature object was not + * properly initialized, or if another exception occurs. + * + * @see netscape.security.provider.DSA#engineUpdate + * @see netscape.security.provider.DSA#engineSign + */ + protected boolean engineVerify(byte[] signature) + throws SignatureException { + + BigInteger r = null; + BigInteger s = null; + // first decode the signature. + try { + DerInputStream in = new DerInputStream(signature); + DerValue[] values = in.getSequence(2); + + r = values[0].getInteger().toBigInteger(); + s = values[1].getInteger().toBigInteger(); + + } catch (IOException e) { + throw new SignatureException("invalid encoding for signature"); + } + BigInteger w = generateW(presetP, presetQ, presetG, s); + BigInteger v = generateV(presetY, presetP, presetQ, presetG, w, r); + + return v.equals(r); + } + + BigInteger generateR(BigInteger p, BigInteger q, BigInteger g, + BigInteger k) { + BigInteger temp = g.modPow(k, p); + return temp.remainder(q); + + } + + BigInteger generateS(BigInteger x, BigInteger q, + BigInteger r, BigInteger k) { + + byte[] s2 = dataSHA.digest(); + BigInteger temp = new BigInteger(1, s2); + BigInteger k1 = k.modInverse(q); + + BigInteger s = x.multiply(r); + s = temp.add(s); + s = k1.multiply(s); + return s.remainder(q); + } + + BigInteger generateW(BigInteger p, BigInteger q, + BigInteger g, BigInteger s) { + return s.modInverse(q); + } + + BigInteger generateV(BigInteger y, BigInteger p, + BigInteger q, BigInteger g, + BigInteger w, BigInteger r) { + + byte[] s2 = dataSHA.digest(); + BigInteger temp = new BigInteger(1, s2); + + temp = temp.multiply(w); + BigInteger u1 = temp.remainder(q); + + BigInteger u2 = (r.multiply(w)).remainder(q); + + BigInteger t1 = g.modPow(u1, p); + BigInteger t2 = y.modPow(u2, p); + BigInteger t3 = t1.multiply(t2); + BigInteger t5 = t3.remainder(p); + return t5.remainder(q); + } + + /* + * Please read bug report 4044247 for an alternative, faster, + * NON-FIPS approved method to generate K + */ + BigInteger generateK(BigInteger q) { + + BigInteger k = null; + + // The application specified a Kseed for us to use. + // Note that we do not allow usage of the same Kseed twice in a row + if (Kseed != null && compareSeeds(Kseed, previousKseed) != 0) { + k = generateK(Kseed, q); + if (k.signum() > 0 && k.compareTo(q) < 0) { + previousKseed = new int[Kseed.length]; + System.arraycopy(Kseed, 0, previousKseed, 0, Kseed.length); + return k; + } + } + + // The application did not specify a Kseed for us to use. + // We'll generate a new Kseed by getting random bytes from + // a SecureRandom object. + SecureRandom random = getSigningRandom(); + + while (true) { + int[] seed = new int[5]; + + for (int i = 0; i < 5; i++) + seed[i] = random.nextInt(); + k = generateK(seed, q); + if (k.signum() > 0 && k.compareTo(q) < 0) { + previousKseed = new int[seed.length]; + System.arraycopy(seed, 0, previousKseed, 0, seed.length); + return k; + } + } + } + + // Use the application-specified SecureRandom Object if provided. + // Otherwise, use our default SecureRandom Object. + private SecureRandom getSigningRandom() { + if (signingRandom == null) { + if (appRandom != null) + signingRandom = appRandom; + else + signingRandom = new SecureRandom(); + } + return signingRandom; + } + + /* + * return 0 if equal + * return 1 if not equal + */ + private int compareSeeds(int[] seed1, int[] seed2) { + + if ((seed1 == null && seed1 == null) || + (seed1 == null && seed2 != null) || + (seed1 != null && seed2 == null) || + seed1.length != seed2.length) + return 1; + + for (int i = 0; i < seed1.length; i++) { + if (seed1[i] != seed2[i]) + return 1; + } + + return 0; + + } + + /** + * Compute k for a DSA signature. + * + * @param seed the seed for generating k. This seed should be + * secure. This is what is refered to as the KSEED in the DSA + * specification. + * + * @param g the g parameter from the DSA key pair. + */ + BigInteger generateK(int[] seed, BigInteger q) { + + // check out t in the spec. + int[] t = { 0xEFCDAB89, 0x98BADCFE, 0x10325476, + 0xC3D2E1F0, 0x67452301 }; + // + int[] tmp = DSA.SHA_7(seed, t); + byte[] tmpBytes = new byte[tmp.length * 4]; + for (int i = 0; i < tmp.length; i++) { + int k = tmp[i]; + for (int j = 0; j < 4; j++) { + tmpBytes[(i * 4) + j] = (byte) (k >>> (24 - (j * 8))); + } + } + BigInteger k = new BigInteger(1, tmpBytes).mod(q); + return k; + } + + // Constants for each round + private static final int round1_kt = 0x5a827999; + private static final int round2_kt = 0x6ed9eba1; + private static final int round3_kt = 0x8f1bbcdc; + private static final int round4_kt = 0xca62c1d6; + + /** + * Computes set 1 thru 7 of SHA-1 on m1. + */ + static int[] SHA_7(int[] m1, int[] h) { + + int[] W = new int[80]; + System.arraycopy(m1, 0, W, 0, m1.length); + int temp = 0; + + for (int t = 16; t <= 79; t++) { + temp = W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16]; + W[t] = ((temp << 1) | (temp >>> (32 - 1))); + } + + int a = h[0], b = h[1], c = h[2], d = h[3], e = h[4]; + for (int i = 0; i < 20; i++) { + temp = ((a << 5) | (a >>> (32 - 5))) + + ((b & c) | ((~b) & d)) + e + W[i] + round1_kt; + e = d; + d = c; + c = ((b << 30) | (b >>> (32 - 30))); + b = a; + a = temp; + } + + // Round 2 + for (int i = 20; i < 40; i++) { + temp = ((a << 5) | (a >>> (32 - 5))) + + (b ^ c ^ d) + e + W[i] + round2_kt; + e = d; + d = c; + c = ((b << 30) | (b >>> (32 - 30))); + b = a; + a = temp; + } + + // Round 3 + for (int i = 40; i < 60; i++) { + temp = ((a << 5) | (a >>> (32 - 5))) + + ((b & c) | (b & d) | (c & d)) + e + W[i] + round3_kt; + e = d; + d = c; + c = ((b << 30) | (b >>> (32 - 30))); + b = a; + a = temp; + } + + // Round 4 + for (int i = 60; i < 80; i++) { + temp = ((a << 5) | (a >>> (32 - 5))) + + (b ^ c ^ d) + e + W[i] + round4_kt; + e = d; + d = c; + c = ((b << 30) | (b >>> (32 - 30))); + b = a; + a = temp; + } + int[] md = new int[5]; + md[0] = h[0] + a; + md[1] = h[1] + b; + md[2] = h[2] + c; + md[3] = h[3] + d; + md[4] = h[4] + e; + return md; + } + + /** + * This implementation recognizes the following parameter: + * <dl> + * + * <dt><tt>Kseed</tt> + * + * <dd>a byte array. + * + * </dl> + * + * @deprecated + */ + protected void engineSetParameter(String key, Object param) { + + if (key.equals("KSEED")) { + + if (param instanceof byte[]) { + + Kseed = byteArray2IntArray((byte[]) param); + KseedAsByteArray = (byte[]) param; + + } else { + debug("unrecognized param: " + key); + throw new InvalidParameterException("Kseed not a byte array"); + } + + } else { + throw new InvalidParameterException("invalid parameter"); + } + } + + /** + * Return the value of the requested parameter. Recognized + * parameters are: + * + * <dl> + * + * <dt><tt>Kseed</tt> + * + * <dd>a byte array. + * + * </dl> + * + * @return the value of the requested parameter. + * + * @deprecated + */ + protected Object engineGetParameter(String key) { + if (key.equals("KSEED")) { + return KseedAsByteArray; + } else { + return null; + } + } + + /** + * Set the algorithm object. + */ + private void setParams(DSAParams params) { + this.params = params; + this.presetP = params.getP(); + this.presetQ = params.getQ(); + this.presetG = params.getG(); + } + + /** + * Update a byte to be signed or verified. + * + * @param b the byte to updated. + */ + protected void engineUpdate(byte b) { + dataSHA.update(b); + } + + /** + * Update an array of bytes to be signed or verified. + * + * @param data the bytes to be updated. + */ + protected void engineUpdate(byte[] data, int off, int len) { + dataSHA.update(data, off, len); + } + + /** + * Return a human readable rendition of the engine. + */ + public String toString() { + String printable = "DSA Signature"; + if (presetP != null && presetQ != null && presetG != null) { + printable += "\n\tp: " + presetP.toString(16); + printable += "\n\tq: " + presetQ.toString(16); + printable += "\n\tg: " + presetG.toString(16); + } else { + printable += "\n\t P, Q or G not initialized."; + } + if (presetY != null) { + printable += "\n\ty: " + presetY.toString(16); + } + if (presetY == null && presetX == null) { + printable += "\n\tUNINIIALIZED"; + } + return printable; + } + + /* + * Utility routine for converting a byte array into an int array + */ + private int[] byteArray2IntArray(byte[] byteArray) { + + int j = 0; + byte[] newBA; + int mod = byteArray.length % 4; + + // guarantee that the incoming byteArray is a multiple of 4 + // (pad with 0's) + switch (mod) { + case 3: + newBA = new byte[byteArray.length + 1]; + break; + case 2: + newBA = new byte[byteArray.length + 2]; + break; + case 1: + newBA = new byte[byteArray.length + 3]; + break; + default: + newBA = new byte[byteArray.length + 0]; + break; + } + System.arraycopy(byteArray, 0, newBA, 0, byteArray.length); + + // copy each set of 4 bytes in the byte array into an integer + int[] newSeed = new int[newBA.length / 4]; + for (int i = 0; i < newBA.length; i += 4) { + newSeed[j] = newBA[i + 3] & 0xFF; + newSeed[j] |= (newBA[i + 2] << 8) & 0xFF00; + newSeed[j] |= (newBA[i + 1] << 16) & 0xFF0000; + newSeed[j] |= (newBA[i + 0] << 24) & 0xFF000000; + j++; + } + + return newSeed; + } + + /* We include the test vectors from the DSA specification, FIPS + 186, and the FIPS 186 Change No 1, which updates the test + vector using SHA-1 instead of SHA (for both the G function and + the message hash. */ + + static void testDSA() throws Exception { + PrintStream p = System.out; + + DSA dsa = new DSA(); + int[] Kseed = { 0x687a66d9, 0x0648f993, 0x867e121f, + 0x4ddf9ddb, 0x1205584 }; + BigInteger k = dsa.generateK(Kseed, q512); + p.println("k: " + k.toString(16)); + BigInteger r = dsa.generateR(p512, q512, g512, k); + p.println("r: " + r.toString(16)); + byte[] abc = { 0x61, 0x62, 0x63 }; + dsa.dataSHA.update(abc); + BigInteger s = dsa.generateS(x512, q512, r, k); + p.println("s: " + s.toString(16)); + + dsa.dataSHA.update(abc); + BigInteger w = dsa.generateW(p512, q512, g512, s); + p.println("w: " + w.toString(16)); + BigInteger v = dsa.generateV(y512, p512, q512, g512, w, r); + p.println("v: " + v.toString(16)); + if (v.equals(r)) { + p.println("signature verifies."); + } else { + p.println("signature does not verify."); + } + } + + /* Test vector: 512-bit keys generated by our key generator. */ + + static BigInteger p512 = + new BigInteger("fca682ce8e12caba26efccf7110e526db078b05edecb" + + "cd1eb4a208f3ae1617ae01f35b91a47e6df63413c5e1" + + "2ed0899bcd132acd50d99151bdc43ee737592e17", 16); + + static BigInteger q512 = + new BigInteger("962eddcc369cba8ebb260ee6b6a126d9346e38c5", 16); + + static BigInteger g512 = + new BigInteger("678471b27a9cf44ee91a49c5147db1a9aaf244f05a43" + + "4d6486931d2d14271b9e35030b71fd73da179069b32e" + + "2935630e1c2062354d0da20a6c416e50be794ca4", 16); + + static BigInteger x512 = + new BigInteger("3406c2d71b04b5fc0db62afcad58a6607d3de688", 16); + + static BigInteger y512 = + new BigInteger("2d335d76b8ec9d610aa8f2cbb4b149fd96fdd" + + "3a9a6e62bd6c2e01d406be4d1d72718a2fe08bea6d12f5e452474461f70f4" + + "dea60508e9fe2eaec23d2ec5d1a866", 16); + + /* Official NIST 512-bit test keys */ + + static String pString = "8df2a494492276aa3d25759bb06869cbeac0d83afb8d0" + + "cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec" + + "0736ee31c80291"; + + static BigInteger testP = new BigInteger(pString, 16); + + static String gString = "626d027839ea0a13413163a55b4cb500299d5522956ce" + + "fcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc5" + + "72af53e6d78802"; + + static BigInteger testG = new BigInteger(gString, 16); + + static BigInteger testQ = new BigInteger("c773218c737ec8ee993b4f2ded30" + + "f48edace915f", 16); + + static BigInteger testX = new BigInteger("2070b3223dba372fde1c0ffc7b2e" + + "3b498b260614", 16); + + static String yString = "19131871d75b1612a819f29d78d1b0d7346f7aa77" + + "bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06" + + "699630a76b030ee333"; + + static BigInteger testY = new BigInteger(yString, 16); + + /* End test vector values */ + + private static void debug(String s) { + if (debug) { + System.err.println(s); + } + } + +} |