From 0b76afc75ca687fcd9a1a8e0b19670fb8f37fecb Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Tue, 22 Feb 2022 17:07:49 -0500 Subject: [PATCH] crypto/rand: simplify Prime to use only rejection sampling MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The old code picks a random number n and then tests n, n+2, n+4, up to n+(1<<20) for primality before giving up and picking a new n. (The chance of finishing the loop and picking a new n is infinitesimally small.) This approach, called “incremental search” in the Handbook of Applied Cryptography, section 4.51, demands fewer bits from the random source and amortizes some of the cost of the small-prime division checks across the incremented values. This commit deletes the n+2, n+4, ... checks, instead picking a series of random n and stopping at the first one that is probably prime. This approach is called “rejection sampling.” Reasons to make this change, in decreasing order of importance: 1. Rejection sampling is simpler, and simpler is more clearly correct. 2. The main benefit of incremental search was performance, and that is less important than before. Incremental search required fewer random bits and was able to amortize the checks for small primes across the entire sequence. However, both random bit generation and primality checks have gotten faster much quicker than typical primes have gotten longer, so the benefits are not as important today. Also, random prime generation is not typically on the critical path. Negating any lingering concerns about performance, rejection sampling no slower in practice than the incremental search, perhaps because the incremental search was using a somewhat inefficient test to eliminate multiples of small primes; ProbablyPrime does it better. name old time/op new time/op delta Prime/MathRand 69.3ms ±23% 68.0ms ±37% ~ (p=0.531 n=20+19) Prime/CryptoRand 69.2ms ±27% 63.8ms ±36% ~ (p=0.076 n=20+20) (Here, Prime/MathRand is the current Prime benchmark, and Prime/CryptoRand is an adaptation to use crypto/rand.Reader instead of math/rand's non-cryptographic randomness source, just in case the quality of the bits affects the outcome. If anything, rejection sampling is even better with cryptographically random bits, but really the two are statistically indistinguishable over 20 runs.) 3. Incremental search has a clear bias when generating small primes: a prime is more likely to be returned the larger the gap between it and the next smaller prime. Although the bias is negligible in practice for cryptographically large primes, people can measure the bias for smaller prime sizes, and we have received such reports extrapolating the bias to larger sizes and claiming a security bug (which, to be clear, does not exist). However, given that rejection sampling is simpler, more clearly correct and at least no slower than incremental search, the bias is indefensible. 4. Incremental search has a timing leak. If you can tell the incremental search ran 10 times, then you know that p is such that there are no primes in the range [p-20, p). To be clear, there are other timing leaks in our current primality testing, so there's no definitive benefit to eliminating this one, but there's also no reason to keep it around. (See https://bugs.chromium.org/p/boringssl/issues/detail?id=238 for all the work that would be needed to make RSA key generation constant-time, which is definitely not something we have planned for Go crypto.) 5. Rejection sampling moves from matching OpenSSL to matching BoringSSL. As a general rule BoringSSL is the better role model. (Everyone started out using incremental search; BoringSSL switched to rejection sampling in 2019, as part of the constant-time work linked above.) Change-Id: Ie67e572a967c12d8728c752045c7e38f21804f8e Reviewed-on: https://go-review.googlesource.com/c/go/+/387554 Trust: Russ Cox Run-TryBot: Russ Cox Reviewed-by: Peter Weinberger Reviewed-by: Filippo Valsorda TryBot-Result: Gopher Robot Auto-Submit: Russ Cox --- src/crypto/rand/util.go | 61 +++++------------------------------------ 1 file changed, 7 insertions(+), 54 deletions(-) diff --git a/src/crypto/rand/util.go b/src/crypto/rand/util.go index 4dd1711203..0f143a3830 100644 --- a/src/crypto/rand/util.go +++ b/src/crypto/rand/util.go @@ -10,28 +10,11 @@ import ( "math/big" ) -// smallPrimes is a list of small, prime numbers that allows us to rapidly -// exclude some fraction of composite candidates when searching for a random -// prime. This list is truncated at the point where smallPrimesProduct exceeds -// a uint64. It does not include two because we ensure that the candidates are -// odd by construction. -var smallPrimes = []uint8{ - 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, -} - -// smallPrimesProduct is the product of the values in smallPrimes and allows us -// to reduce a candidate prime by this number and then determine whether it's -// coprime to all the elements of smallPrimes without further big.Int -// operations. -var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365) - -// Prime returns a number, p, of the given size, such that p is prime -// with high probability. +// Prime returns a number of the given bit length that is prime with high probability. // Prime will return error for any error returned by rand.Read or if bits < 2. -func Prime(rand io.Reader, bits int) (p *big.Int, err error) { +func Prime(rand io.Reader, bits int) (*big.Int, error) { if bits < 2 { - err = errors.New("crypto/rand: prime size must be at least 2-bit") - return + return nil, errors.New("crypto/rand: prime size must be at least 2-bit") } b := uint(bits % 8) @@ -40,13 +23,10 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err error) { } bytes := make([]byte, (bits+7)/8) - p = new(big.Int) - - bigMod := new(big.Int) + p := new(big.Int) for { - _, err = io.ReadFull(rand, bytes) - if err != nil { + if _, err := io.ReadFull(rand, bytes); err != nil { return nil, err } @@ -69,35 +49,8 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err error) { bytes[len(bytes)-1] |= 1 p.SetBytes(bytes) - - // Calculate the value mod the product of smallPrimes. If it's - // a multiple of any of these primes we add two until it isn't. - // The probability of overflowing is minimal and can be ignored - // because we still perform Miller-Rabin tests on the result. - bigMod.Mod(p, smallPrimesProduct) - mod := bigMod.Uint64() - - NextDelta: - for delta := uint64(0); delta < 1<<20; delta += 2 { - m := mod + delta - for _, prime := range smallPrimes { - if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) { - continue NextDelta - } - } - - if delta > 0 { - bigMod.SetUint64(delta) - p.Add(p, bigMod) - } - break - } - - // There is a tiny possibility that, by adding delta, we caused - // the number to be one bit too long. Thus we check BitLen - // here. - if p.ProbablyPrime(20) && p.BitLen() == bits { - return + if p.ProbablyPrime(20) { + return p, nil } } } -- 2.50.0