openssl
diff --git a/‎crypto/dsa/dsa_ossl.c‎
Lines changed: 32 additions & 2 deletions b/‎crypto/dsa/dsa_ossl.c‎
Lines changed: 32 additions & 2 deletions
@@ -73,6 +73,8 @@ static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
                          DSA_SIG *sig, DSA *dsa);
 static int dsa_init(DSA *dsa);
 static int dsa_finish(DSA *dsa);
+static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q,
+                                      BN_CTX *ctx);
 
 static DSA_METHOD openssl_dsa_meth = {
     "OpenSSL DSA method",
@@ -333,8 +335,8 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
     if (!BN_mod(r, r, dsa->q, ctx))
         goto err;
 
-    /* Compute  part of 's = inv(k) (m + xr) mod q' */
-    if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL)
+    /* Compute part of 's = inv(k) (m + xr) mod q' */
+    if ((kinv = dsa_mod_inverse_fermat(&k, dsa->q, ctx)) == NULL)
         goto err;
 
     if (*kinvp != NULL)
@@ -468,3 +470,31 @@ static int dsa_finish(DSA *dsa)
         BN_MONT_CTX_free(dsa->method_mont_p);
     return (1);
 }
+
+/*
+ * Compute the inverse of k modulo q.
+ * Since q is prime, Fermat's Little Theorem applies, which reduces this to
+ * mod-exp operation.  Both the exponent and modulus are public information
+ * so a mod-exp that doesn't leak the base is sufficient.  A newly allocated
+ * BIGNUM is returned which the caller must free.
+ */
+static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q,
+                                      BN_CTX *ctx)
+{
+    BIGNUM *res = NULL;
+    BIGNUM *r, e;
+
+    if ((r = BN_new()) == NULL)
+        return NULL;
+
+    BN_init(&e);
+
+    if (BN_set_word(r, 2)
+            && BN_sub(&e, q, r)
+            && BN_mod_exp_mont(r, k, &e, q, ctx, NULL))
+        res = r;
+    else
+        BN_free(r);
+    BN_free(&e);
+    return res;
+}