added support for RFC 6979 deterministic DSA/ECDSA

5 files changed, 309 insertions, 19 deletions

diff --git a/core/src/main/java/org/bouncycastle/crypto/signers/DSAKCalculator.java b/core/src/main/java/org/bouncycastle/crypto/signers/DSAKCalculator.java
new file mode 100644
index 00000000..fced06ea
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/crypto/signers/DSAKCalculator.java
@@ -0,0 +1,41 @@
+package org.bouncycastle.crypto.signers;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+
+/**
+ * Interface define calculators of K values for DSA/ECDSA.
+ */
+public interface DSAKCalculator
+{
+    /**
+     * Return true if this calculator is deterministic, false otherwise.
+     *
+     * @return true if deterministic, otherwise false.
+     */
+    boolean isDeterministic();
+
+    /**
+     * Non-deterministic initialiser.
+     *
+     * @param n the order of the DSA group.
+     * @param random a source of randomness.
+     */
+    void init(BigInteger n, SecureRandom random);
+
+    /**
+     * Deterministic initialiser.
+     *
+     * @param n the order of the DSA group.
+     * @param d the DSA private value.
+     * @param message the message being signed.
+     */
+    void init(BigInteger n, BigInteger d, byte[] message);
+
+    /**
+     * Return the next valid value of K.
+     *
+     * @return a K value.
+     */
+    BigInteger nextK();
+}
diff --git a/core/src/main/java/org/bouncycastle/crypto/signers/DSASigner.java b/core/src/main/java/org/bouncycastle/crypto/signers/DSASigner.java
index a96cef07..292c4087 100644
--- a/core/src/main/java/org/bouncycastle/crypto/signers/DSASigner.java
+++ b/core/src/main/java/org/bouncycastle/crypto/signers/DSASigner.java
@@ -1,5 +1,8 @@
 package org.bouncycastle.crypto.signers;
 
+import java.math.BigInteger;
+import java.security.SecureRandom;
+
 import org.bouncycastle.crypto.CipherParameters;
 import org.bouncycastle.crypto.DSA;
 import org.bouncycastle.crypto.params.DSAKeyParameters;
@@ -8,9 +11,6 @@ import org.bouncycastle.crypto.params.DSAPrivateKeyParameters;
 import org.bouncycastle.crypto.params.DSAPublicKeyParameters;
 import org.bouncycastle.crypto.params.ParametersWithRandom;
 
-import java.math.BigInteger;
-import java.security.SecureRandom;
-
 /**
  * The Digital Signature Algorithm - as described in "Handbook of Applied
  * Cryptography", pages 452 - 453.
@@ -18,9 +18,28 @@ import java.security.SecureRandom;
 public class DSASigner
     implements DSA
 {
-    DSAKeyParameters key;
+    private final DSAKCalculator kCalculator;
 
-    SecureRandom    random;
+    private DSAKeyParameters key;
+    private SecureRandom    random;
+
+    /**
+     * Default configuration, random K values.
+     */
+    public DSASigner()
+    {
+        this.kCalculator = new RandomDSAKCalculator();
+    }
+
+    /**
+     * Configuration with an alternate, possibly deterministic calculator of K.
+     *
+     * @param kCalculator a K value calculator.
+     */
+    public DSASigner(DSAKCalculator kCalculator)
+    {
+        this.kCalculator = kCalculator;
+    }
 
     public void init(
         boolean                 forSigning,
@@ -59,14 +78,17 @@ public class DSASigner
     {
         DSAParameters   params = key.getParameters();
         BigInteger      m = calculateE(params.getQ(), message);
-        BigInteger      k;
-        int                  qBitLength = params.getQ().bitLength();
 
-        do 
+        if (kCalculator.isDeterministic())
         {
-            k = new BigInteger(qBitLength, random);
+            kCalculator.init(params.getQ(), ((DSAPrivateKeyParameters)key).getX(), message);
         }
-        while (k.compareTo(params.getQ()) >= 0);
+        else
+        {
+            kCalculator.init(params.getQ(), random);
+        }
+
+        BigInteger  k = kCalculator.nextK();
 
         BigInteger  r = params.getG().modPow(k, params.getP()).mod(params.getQ());
 
diff --git a/core/src/main/java/org/bouncycastle/crypto/signers/ECDSASigner.java b/core/src/main/java/org/bouncycastle/crypto/signers/ECDSASigner.java
index 9156de40..2a1f98eb 100644
--- a/core/src/main/java/org/bouncycastle/crypto/signers/ECDSASigner.java
+++ b/core/src/main/java/org/bouncycastle/crypto/signers/ECDSASigner.java
@@ -19,9 +19,28 @@ import org.bouncycastle.math.ec.ECPoint;
 public class ECDSASigner
     implements ECConstants, DSA
 {
-    ECKeyParameters key;
+    private final DSAKCalculator kCalculator;
 
-    SecureRandom    random;
+    private ECKeyParameters key;
+    private SecureRandom    random;
+
+    /**
+     * Default configuration, random K values.
+     */
+    public ECDSASigner()
+    {
+        this.kCalculator = new RandomDSAKCalculator();
+    }
+
+    /**
+     * Configuration with an alternate, possibly deterministic calculator of K.
+     *
+     * @param kCalculator a K value calculator.
+     */
+    public ECDSASigner(DSAKCalculator kCalculator)
+    {
+        this.kCalculator = kCalculator;
+    }
 
     public void init(
         boolean                 forSigning,
@@ -64,19 +83,23 @@ public class ECDSASigner
         BigInteger r = null;
         BigInteger s = null;
 
+        if (kCalculator.isDeterministic())
+        {
+            kCalculator.init(n, ((ECPrivateKeyParameters)key).getD(), message);
+        }
+        else
+        {
+            kCalculator.init(n, random);
+        }
+
         // 5.3.2
         do // generate s
         {
             BigInteger k = null;
-            int        nBitLength = n.bitLength();
 
             do // generate r
             {
-                do
-                {
-                    k = new BigInteger(nBitLength, random);
-                }
-                while (k.equals(ZERO) || k.compareTo(n) >= 0);
+                k = kCalculator.nextK();
 
                 ECPoint p = key.getParameters().getG().multiply(k).normalize();
 
@@ -153,7 +176,7 @@ public class ECDSASigner
         int log2n = n.bitLength();
         int messageBitLength = message.length * 8;
 
-        BigInteger e = new BigInteger(1, message); 
+        BigInteger e = new BigInteger(1, message);
         if (log2n < messageBitLength)
         {
             e = e.shiftRight(messageBitLength - log2n);
diff --git a/core/src/main/java/org/bouncycastle/crypto/signers/HMacDSAKCalculator.java b/core/src/main/java/org/bouncycastle/crypto/signers/HMacDSAKCalculator.java
new file mode 100644
index 00000000..b96e3f37
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/crypto/signers/HMacDSAKCalculator.java
@@ -0,0 +1,161 @@
+package org.bouncycastle.crypto.signers;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+
+import org.bouncycastle.crypto.Digest;
+import org.bouncycastle.crypto.macs.HMac;
+import org.bouncycastle.crypto.params.KeyParameter;
+import org.bouncycastle.util.Arrays;
+import org.bouncycastle.util.BigIntegers;
+
+/**
+ * A deterministic K calculator based on the algorithm in section 3.2 of RFC 6979.
+ */
+public class HMacDSAKCalculator
+    implements DSAKCalculator
+{
+    private static final BigInteger ZERO = BigInteger.valueOf(0);
+
+    private final HMac hMac;
+    private final byte[] K;
+    private final byte[] V;
+
+    private BigInteger n;
+
+    /**
+     * Base constructor.
+     *
+     * @param digest digest to build the HMAC on.
+     */
+    public HMacDSAKCalculator(Digest digest)
+    {
+        this.hMac = new HMac(digest);
+        this.V = new byte[hMac.getMacSize()];
+        this.K = new byte[hMac.getMacSize()];
+    }
+
+    public boolean isDeterministic()
+    {
+        return true;
+    }
+
+    public void init(BigInteger n, SecureRandom random)
+    {
+        throw new IllegalStateException("Operation not supported");
+    }
+
+    public void init(BigInteger n, BigInteger d, byte[] message)
+    {
+        this.n = n;
+
+        Arrays.fill(V, (byte)0x01);
+        Arrays.fill(K, (byte)0);
+
+        byte[] x = new byte[(n.bitLength() + 7) / 8];
+        byte[] dVal = BigIntegers.asUnsignedByteArray(d);
+
+        System.arraycopy(dVal, 0, x, x.length - dVal.length, dVal.length);
+
+        byte[] m = new byte[(n.bitLength() + 7) / 8];
+
+        BigInteger mInt = bitsToInt(message);
+
+        if (mInt.compareTo(n) > 0)
+        {
+            mInt = mInt.subtract(n);
+        }
+
+        byte[] mVal = BigIntegers.asUnsignedByteArray(mInt);
+
+        System.arraycopy(mVal, 0, m, m.length - mVal.length, mVal.length);
+
+        hMac.init(new KeyParameter(K));
+
+        hMac.update(V, 0, V.length);
+        hMac.update((byte)0x00);
+        hMac.update(x, 0, x.length);
+        hMac.update(m, 0, m.length);
+
+        hMac.doFinal(K, 0);
+
+        hMac.init(new KeyParameter(K));
+
+        hMac.update(V, 0, V.length);
+
+        hMac.doFinal(V, 0);
+
+        hMac.update(V, 0, V.length);
+        hMac.update((byte)0x01);
+        hMac.update(x, 0, x.length);
+        hMac.update(m, 0, m.length);
+
+        hMac.doFinal(K, 0);
+
+        hMac.init(new KeyParameter(K));
+
+        hMac.update(V, 0, V.length);
+
+        hMac.doFinal(V, 0);
+    }
+
+    public BigInteger nextK()
+    {
+        byte[] t = new byte[((n.bitLength() + 7) / 8)];
+
+        for (;;)
+        {
+            int tOff = 0;
+
+            while (tOff < t.length)
+            {
+                hMac.update(V, 0, V.length);
+
+                hMac.doFinal(V, 0);
+
+                if (t.length - tOff < V.length)
+                {
+                    System.arraycopy(V, 0, t, tOff, t.length - tOff);
+                    tOff += t.length - tOff;
+                }
+                else
+                {
+                    System.arraycopy(V, 0, t, tOff, V.length);
+                    tOff += V.length;
+                }
+            }
+
+            BigInteger k = bitsToInt(t);
+
+            if (k.equals(ZERO) || k.compareTo(n) >= 0)
+            {
+                hMac.update(V, 0, V.length);
+                hMac.update((byte)0x00);
+
+                hMac.doFinal(K, 0);
+
+                hMac.init(new KeyParameter(K));
+
+                hMac.update(V, 0, V.length);
+
+                hMac.doFinal(V, 0);
+            }
+            else
+            {
+                return k;
+            }
+        }
+    }
+
+    private BigInteger bitsToInt(byte[] t)
+    {
+        BigInteger v = new BigInteger(1, t);
+
+        if (t.length * 8 > n.bitLength())
+        {
+            v = v.shiftRight(t.length * 8 - n.bitLength());
+        }
+
+        return v;
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/crypto/signers/RandomDSAKCalculator.java b/core/src/main/java/org/bouncycastle/crypto/signers/RandomDSAKCalculator.java
new file mode 100644
index 00000000..bbd8cda6
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/crypto/signers/RandomDSAKCalculator.java
@@ -0,0 +1,43 @@
+package org.bouncycastle.crypto.signers;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+
+class RandomDSAKCalculator
+    implements DSAKCalculator
+{
+    private static final BigInteger ZERO = BigInteger.valueOf(0);
+
+    private BigInteger q;
+    private SecureRandom random;
+
+    public boolean isDeterministic()
+    {
+        return false;
+    }
+
+    public void init(BigInteger n, SecureRandom random)
+    {
+        this.q = n;
+        this.random = random;
+    }
+
+    public void init(BigInteger n, BigInteger d, byte[] message)
+    {
+        throw new IllegalStateException("Operation not supported");
+    }
+
+    public BigInteger nextK()
+    {
+        int qBitLength = q.bitLength();
+
+        BigInteger k;
+        do
+        {
+            k = new BigInteger(qBitLength, random);
+        }
+        while (k.equals(ZERO) || k.compareTo(q) >= 0);
+
+        return k;
+    }
+}