crypto/rsa: ensure that generating toy RSA keys doesn't loop.

If there are too few primes of the given length then it can be
impossible to generate an RSA key with n distinct primes.

This change approximates the expected number of candidate primes and
causes key generation to return an error if it's unlikely to succeed.

Fixes #16596.

Change-Id: I53b60d0cb90e2d0e6f0662befa64d13f24af51a7
Reviewed-on: https://go-review.googlesource.com/28969
Reviewed-by: Minux Ma <minux@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Minux Ma <minux@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 16 insertions, 0 deletions

diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
index d79c9b23fc..94862597dc 100644
--- a/src/crypto/rsa/rsa.go
+++ b/src/crypto/rsa/rsa.go
@@ -27,6 +27,7 @@ import (
 	"errors"
 	"hash"
 	"io"
+	"math"
 	"math/big"
 )
 
@@ -214,6 +215,21 @@ func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey
 		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
 	}
 
+	if bits < 64 {
+		primeLimit := float64(uint64(1) << uint(bits/nprimes))
+		// pi approximates the number of primes less than primeLimit
+		pi := primeLimit / (math.Log(primeLimit) - 1)
+		// Generated primes start with 11 (in binary) so we can only
+		// use a quarter of them.
+		pi /= 4
+		// Use a factor of two to ensure that key generation terminates
+		// in a reasonable amount of time.
+		pi /= 2
+		if pi <= float64(nprimes) {
+			return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
+		}
+	}
+
 	primes := make([]*big.Int, nprimes)
 
 NextSetOfPrimes: