crypto/rsa: handle the case of non-coprime blinds.

We are dealing with the multiplicative group ℤ/pqℤ. Multiples of
either p or q are not members of the group since they cannot have an
inverse. (Such numbers are 0 in the subgroup ℤ/pℤ.)

With p and q of typical size (> 512 bits), the probability of a random
blind [1..pq-1] being a multiple of p or q is negligible. However, in
the unit tests, much smaller sizes are used and the event could occur.

This change checks the result of the ext GCD and deals with this case.

It also increases the size of p and q in the unit test as a large
number of the keys selected were p, q = 227,169.

R=rsc
CC=golang-dev
http://codereview.appspot.com/154141

Committer: Russ Cox <rsc@golang.org>

2 files changed, 26 insertions, 11 deletions

diff --git a/src/pkg/crypto/rsa/rsa.go b/src/pkg/crypto/rsa/rsa.go
index 42a888835..163e412c0 100644
--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -290,18 +290,26 @@ func (DecryptionError) String() string	{ return "RSA decryption 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) {
+func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
 	g := new(big.Int);
 	x := new(big.Int);
 	y := new(big.Int);
 	big.GcdInt(g, x, y, 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;
+	return x, true;
 }
 
 // decrypt performs an RSA decryption, resulting in a plaintext integer. If a
@@ -320,15 +328,22 @@ func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.E
 		// which equals mr mod n. The factor of r can then be removed
 		// by multipling by the multiplicative inverse of r.
 
-		r, err1 := randomNumber(rand, priv.N);
-		if err1 != nil {
-			err = err1;
-			return;
-		}
-		if r.Cmp(bigZero) == 0 {
-			r = bigOne
+		var r *big.Int;
+
+		for {
+			r, err = randomNumber(rand, priv.N);
+			if err != nil {
+				return
+			}
+			if r.Cmp(bigZero) == 0 {
+				r = bigOne
+			}
+			var ok bool;
+			ir, ok = modInverse(r, priv.N);
+			if ok {
+				break
+			}
 		}
-		ir = modInverse(r, priv.N);
 		bigE := big.NewInt(int64(priv.E));
 		rpowe := new(big.Int).Exp(r, bigE, priv.N);
 		c.Mul(c, rpowe);
diff --git a/src/pkg/crypto/rsa/rsa_test.go b/src/pkg/crypto/rsa/rsa_test.go
index ae1aa3e71..cc15b8674 100644
--- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -18,7 +18,7 @@ func TestKeyGeneration(t *testing.T) {
 		t.Errorf("failed to open /dev/urandom")
 	}
 
-	priv, err := GenerateKey(urandom, 16);
+	priv, err := GenerateKey(urandom, 32);
 	if err != nil {
 		t.Errorf("failed to generate key")
 	}