Imported Upstream version 1.3upstream/1.3

1 files changed, 11 insertions, 1 deletions

diff --git a/src/pkg/crypto/dsa/dsa.go b/src/pkg/crypto/dsa/dsa.go
index 5a2a65744..b7565a61b 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)