// --- 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:
*
*
* - Kseed
*
*
- a byte array.
*
*
*
* @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:
*
*
*
* - Kseed
*
*
- a byte array.
*
*
*
* @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);
}
}
}