From f23d3ea85afce3c4940bcf55889625d2e2017128 Mon Sep 17 00:00:00 2001
From: Adam Langley <agl@golang.org>
Date: Tue, 8 Apr 2014 16:32:48 -0700
Subject: [PATCH] crypto/(ec)dsa: use Fermat's inversion.

Now that we have a constant-time P-256 implementation, it's worth
paying more attention elsewhere.

The inversion of k in (EC)DSA was using Euclid's algorithm which isn't
constant-time. This change switches to Fermat's algorithm, which is
much better. However, it's important to note that math/big itself isn't
constant time and is using a 4-bit window for exponentiation with
variable memory access patterns.

(Since math/big depends quite deeply on its values being in minimal (as
opposed to fixed-length) represetation, perhaps crypto/elliptic should
grow a constant-time implementation of exponentiation in the scalar
field.)

R=bradfitz
Fixes #7652.

LGTM=rsc
R=golang-codereviews, bradfitz, rsc
CC=golang-codereviews
https://golang.org/cl/82740043
---
 src/pkg/crypto/dsa/dsa.go     | 12 +++++++++++-
 src/pkg/crypto/ecdsa/ecdsa.go | 12 +++++++++++-
 2 files changed, 22 insertions(+), 2 deletions(-)

diff --git a/src/pkg/crypto/dsa/dsa.go b/src/pkg/crypto/dsa/dsa.go
index 5a2a65744e..b7565a61b0 100644
--- a/src/pkg/crypto/dsa/dsa.go
+++ b/src/pkg/crypto/dsa/dsa.go
@@ -173,6 +173,16 @@ func GenerateKey(priv *PrivateKey, rand io.Reader) error {
 	return nil
 }
 
+// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
+// This has better constant-time properties than Euclid's method (implemented
+// in math/big.Int.ModInverse) although math/big itself isn't strictly
+// constant-time so it's not perfect.
+func fermatInverse(k, P *big.Int) *big.Int {
+	two := big.NewInt(2)
+	pMinus2 := new(big.Int).Sub(P, two)
+	return new(big.Int).Exp(k, pMinus2, P)
+}
+
 // Sign signs an arbitrary length hash (which should be the result of hashing a
 // larger message) using the private key, priv. It returns the signature as a
 // pair of integers. The security of the private key depends on the entropy of
@@ -205,7 +215,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err
 			}
 		}
 
-		kInv := new(big.Int).ModInverse(k, priv.Q)
+		kInv := fermatInverse(k, priv.Q)
 
 		r = new(big.Int).Exp(priv.G, k, priv.P)
 		r.Mod(r, priv.Q)
diff --git a/src/pkg/crypto/ecdsa/ecdsa.go b/src/pkg/crypto/ecdsa/ecdsa.go
index d02f15c34d..1bec7437a5 100644
--- a/src/pkg/crypto/ecdsa/ecdsa.go
+++ b/src/pkg/crypto/ecdsa/ecdsa.go
@@ -84,6 +84,16 @@ func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
 	return ret
 }
 
+// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
+// This has better constant-time properties than Euclid's method (implemented
+// in math/big.Int.ModInverse) although math/big itself isn't strictly
+// constant-time so it's not perfect.
+func fermatInverse(k, N *big.Int) *big.Int {
+	two := big.NewInt(2)
+	nMinus2 := new(big.Int).Sub(N, two)
+	return new(big.Int).Exp(k, nMinus2, N)
+}
+
 // Sign signs an arbitrary length hash (which should be the result of hashing a
 // larger message) using the private key, priv. It returns the signature as a
 // pair of integers. The security of the private key depends on the entropy of
@@ -102,7 +112,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err
 				return
 			}
 
-			kInv = new(big.Int).ModInverse(k, N)
+			kInv = fermatInverse(k, N)
 			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 			r.Mod(r, N)
 			if r.Sign() != 0 {
-- 
2.50.0