commit 99c752ad52a42b40efd1654f8d506177c38ee1e1
author David Benjamin <davidben@google.com> Thu Jun 16 15:13:43 2016 -0400
committer Adam Langley <agl@google.com> Mon Jun 20 17:16:18 2016 +0000
tree a813673ae5a65741aa0754420f861e140500b7d0
parent 8cf79af7d1497c07bd684764b96c9659e7b32ae1

Compute kinv in DSA with Fermat's Little Theorem.

It's a prime, so computing a constant-time mod inverse is straight-forward.

Change-Id: Ie09b84363c3d5da827989300a844c470437fd8f2
Reviewed-on: https://boringssl-review.googlesource.com/8308
Reviewed-by: Adam Langley <agl@google.com>

crypto/dsa/dsa.c

diff --git a/crypto/dsa/dsa.c b/crypto/dsa/dsa.c
index 1de0071..26872d2 100644
--- a/crypto/dsa/dsa.c
+++ b/crypto/dsa/dsa.c
@@ -94,7 +94,7 @@
 
   dsa->references = 1;
 
-  CRYPTO_MUTEX_init(&dsa->method_mont_p_lock);
+  CRYPTO_MUTEX_init(&dsa->method_mont_lock);
   CRYPTO_new_ex_data(&dsa->ex_data);
 
   return dsa;
@@ -119,7 +119,8 @@
   BN_clear_free(dsa->kinv);
   BN_clear_free(dsa->r);
   BN_MONT_CTX_free(dsa->method_mont_p);
-  CRYPTO_MUTEX_cleanup(&dsa->method_mont_p_lock);
+  BN_MONT_CTX_free(dsa->method_mont_q);
+  CRYPTO_MUTEX_cleanup(&dsa->method_mont_lock);
   OPENSSL_free(dsa);
 }
 
@@ -662,7 +663,7 @@
   }
 
   if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p,
-                              (CRYPTO_MUTEX *)&dsa->method_mont_p_lock, dsa->p,
+                              (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p,
                               ctx)) {
     goto err;
   }
@@ -788,7 +789,7 @@
 int DSA_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv,
                    BIGNUM **out_r) {
   BN_CTX *ctx;
-  BIGNUM k, kq, *K, *kinv = NULL, *r = NULL;
+  BIGNUM k, kq, qm2, *K, *kinv = NULL, *r = NULL;
   int ret = 0;
 
   if (!dsa->p || !dsa->q || !dsa->g) {
@@ -798,6 +799,7 @@
 
   BN_init(&k);
   BN_init(&kq);
+  BN_init(&qm2);
 
   ctx = ctx_in;
   if (ctx == NULL) {
@@ -822,7 +824,10 @@
   BN_set_flags(&k, BN_FLG_CONSTTIME);
 
   if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p,
-                              (CRYPTO_MUTEX *)&dsa->method_mont_p_lock, dsa->p,
+                              (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p,
+                              ctx) ||
+      !BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_q,
+                              (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->q,
                               ctx)) {
     goto err;
   }
@@ -855,9 +860,13 @@
     goto err;
   }
 
-  /* Compute  part of 's = inv(k) (m + xr) mod q' */
-  kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx);
-  if (kinv == NULL) {
+  /* Compute part of 's = inv(k) (m + xr) mod q' using Fermat's Little
+   * Theorem. */
+  kinv = BN_new();
+  if (kinv == NULL ||
+      !BN_set_word(&qm2, 2) ||
+      !BN_sub(&qm2, dsa->q, &qm2) ||
+      !BN_mod_exp_mont(kinv, &k, &qm2, dsa->q, ctx, dsa->method_mont_q)) {
     goto err;
   }
 
@@ -881,6 +890,7 @@
   }
   BN_clear_free(&k);
   BN_clear_free(&kq);
+  BN_free(&qm2);
   return ret;
 }
 

include/openssl/dsa.h

diff --git a/include/openssl/dsa.h b/include/openssl/dsa.h
index 0077a72..2a621da 100644
--- a/include/openssl/dsa.h
+++ b/include/openssl/dsa.h
@@ -387,8 +387,9 @@
 
   int flags;
   /* Normally used to cache montgomery values */
-  CRYPTO_MUTEX method_mont_p_lock;
+  CRYPTO_MUTEX method_mont_lock;
   BN_MONT_CTX *method_mont_p;
+  BN_MONT_CTX *method_mont_q;
   CRYPTO_refcount_t references;
   CRYPTO_EX_DATA ex_data;
 };