math/big: return nil for nonexistent ModInverse

Currently, the behavior of z.ModInverse(g, n) is undefined
when g and n are not relatively prime.  In that case, no
ModInverse exists which can be easily checked during the
computation of the ModInverse.  Because the ModInverse does
not indicate whether the inverse exists, there are reimplementations
of a "checked" ModInverse in crypto/rsa.  This change removes the
undefined behavior.  If the ModInverse does not exist, the receiver z
is unchanged and the return value is nil. This matches the behavior of
ModSqrt for the case where the square root does not exist.

name          old time/op    new time/op    delta
ModInverse-4    2.40µs ± 4%    2.22µs ± 0%   -7.74%  (p=0.016 n=5+4)

name          old alloc/op   new alloc/op   delta
ModInverse-4    1.36kB ± 0%    1.17kB ± 0%  -14.12%  (p=0.008 n=5+5)

name          old allocs/op  new allocs/op  delta
ModInverse-4      10.0 ± 0%       9.0 ± 0%  -10.00%  (p=0.008 n=5+5)

Fixes #24922

Change-Id: If7f9d491858450bdb00f1e317152f02493c9c8a8
Reviewed-on: https://go-review.googlesource.com/108996
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

1 files changed, 5 insertions, 34 deletions

diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
index 38cd568437..83d74967aa 100644
--- a/src/crypto/rsa/rsa.go
+++ b/src/crypto/rsa/rsa.go
@@ -292,18 +292,13 @@ NextSetOfPrimes:
 			continue NextSetOfPrimes
 		}
 
-		g := new(big.Int)
 		priv.D = new(big.Int)
 		e := big.NewInt(int64(priv.E))
-		g.GCD(priv.D, nil, e, totient)
+		ok := priv.D.ModInverse(e, totient)
 
-		if g.Cmp(bigOne) == 0 {
-			if priv.D.Sign() < 0 {
-				priv.D.Add(priv.D, totient)
-			}
+		if ok != nil {
 			priv.Primes = primes
 			priv.N = n
-
 			break
 		}
 	}
@@ -427,29 +422,6 @@ var ErrDecryption = errors.New("crypto/rsa: decryption error")
 // It is deliberately vague to avoid adaptive attacks.
 var ErrVerification = errors.New("crypto/rsa: verification error")
 
-// modInverse returns ia, the inverse of a in the multiplicative group of prime
-// order n. It requires that a be a member of the group (i.e. less than n).
-func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
-	g := new(big.Int)
-	x := new(big.Int)
-	g.GCD(x, nil, a, n)
-	if g.Cmp(bigOne) != 0 {
-		// In this case, a and n aren't coprime and we cannot calculate
-		// the inverse. This happens because the values of n are nearly
-		// prime (being the product of two primes) rather than truly
-		// prime.
-		return
-	}
-
-	if x.Cmp(bigOne) < 0 {
-		// 0 is not the multiplicative inverse of any element so, if x
-		// < 1, then x is negative.
-		x.Add(x, n)
-	}
-
-	return x, true
-}
-
 // Precompute performs some calculations that speed up private key operations
 // in the future.
 func (priv *PrivateKey) Precompute() {
@@ -501,7 +473,7 @@ func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err er
 		// by multiplying by the multiplicative inverse of r.
 
 		var r *big.Int
-
+		ir = new(big.Int)
 		for {
 			r, err = rand.Int(random, priv.N)
 			if err != nil {
@@ -510,9 +482,8 @@ func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err er
 			if r.Cmp(bigZero) == 0 {
 				r = bigOne
 			}
-			var ok bool
-			ir, ok = modInverse(r, priv.N)
-			if ok {
+			ok := ir.ModInverse(r, priv.N)
+			if ok != nil {
 				break
 			}
 		}