Black Lives Matter. Support the Equal Justice Initiative.

# Source file src/crypto/rand/util.go

## Documentation: crypto/rand

```     1  // Copyright 2011 The Go Authors. All rights reserved.
2  // Use of this source code is governed by a BSD-style
3  // license that can be found in the LICENSE file.
4
5  package rand
6
7  import (
8  	"errors"
9  	"io"
10  	"math/big"
11  )
12
13  // smallPrimes is a list of small, prime numbers that allows us to rapidly
14  // exclude some fraction of composite candidates when searching for a random
15  // prime. This list is truncated at the point where smallPrimesProduct exceeds
16  // a uint64. It does not include two because we ensure that the candidates are
17  // odd by construction.
18  var smallPrimes = []uint8{
19  	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
20  }
21
22  // smallPrimesProduct is the product of the values in smallPrimes and allows us
23  // to reduce a candidate prime by this number and then determine whether it's
24  // coprime to all the elements of smallPrimes without further big.Int
25  // operations.
26  var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365)
27
28  // Prime returns a number, p, of the given size, such that p is prime
29  // with high probability.
30  // Prime will return error for any error returned by rand.Read or if bits < 2.
31  func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
32  	if bits < 2 {
33  		err = errors.New("crypto/rand: prime size must be at least 2-bit")
34  		return
35  	}
36
37  	b := uint(bits % 8)
38  	if b == 0 {
39  		b = 8
40  	}
41
42  	bytes := make([]byte, (bits+7)/8)
43  	p = new(big.Int)
44
45  	bigMod := new(big.Int)
46
47  	for {
48  		_, err = io.ReadFull(rand, bytes)
49  		if err != nil {
50  			return nil, err
51  		}
52
53  		// Clear bits in the first byte to make sure the candidate has a size <= bits.
54  		bytes &= uint8(int(1<<b) - 1)
55  		// Don't let the value be too small, i.e, set the most significant two bits.
56  		// Setting the top two bits, rather than just the top bit,
57  		// means that when two of these values are multiplied together,
58  		// the result isn't ever one bit short.
59  		if b >= 2 {
60  			bytes |= 3 << (b - 2)
61  		} else {
62  			// Here b==1, because b cannot be zero.
63  			bytes |= 1
64  			if len(bytes) > 1 {
65  				bytes |= 0x80
66  			}
67  		}
68  		// Make the value odd since an even number this large certainly isn't prime.
69  		bytes[len(bytes)-1] |= 1
70
71  		p.SetBytes(bytes)
72
73  		// Calculate the value mod the product of smallPrimes. If it's
74  		// a multiple of any of these primes we add two until it isn't.
75  		// The probability of overflowing is minimal and can be ignored
76  		// because we still perform Miller-Rabin tests on the result.
77  		bigMod.Mod(p, smallPrimesProduct)
78  		mod := bigMod.Uint64()
79
80  	NextDelta:
81  		for delta := uint64(0); delta < 1<<20; delta += 2 {
82  			m := mod + delta
83  			for _, prime := range smallPrimes {
84  				if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) {
85  					continue NextDelta
86  				}
87  			}
88
89  			if delta > 0 {
90  				bigMod.SetUint64(delta)
91  				p.Add(p, bigMod)
92  			}
93  			break
94  		}
95
96  		// There is a tiny possibility that, by adding delta, we caused
97  		// the number to be one bit too long. Thus we check BitLen
98  		// here.
99  		if p.ProbablyPrime(20) && p.BitLen() == bits {
100  			return
101  		}
102  	}
103  }
104
105  // Int returns a uniform random value in [0, max). It panics if max <= 0.
106  func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
107  	if max.Sign() <= 0 {
108  		panic("crypto/rand: argument to Int is <= 0")
109  	}
110  	n = new(big.Int)
111  	n.Sub(max, n.SetUint64(1))
112  	// bitLen is the maximum bit length needed to encode a value < max.
113  	bitLen := n.BitLen()
114  	if bitLen == 0 {
115  		// the only valid result is 0
116  		return
117  	}
118  	// k is the maximum byte length needed to encode a value < max.
119  	k := (bitLen + 7) / 8
120  	// b is the number of bits in the most significant byte of max-1.
121  	b := uint(bitLen % 8)
122  	if b == 0 {
123  		b = 8
124  	}
125
126  	bytes := make([]byte, k)
127
128  	for {
129  		_, err = io.ReadFull(rand, bytes)
130  		if err != nil {
131  			return nil, err
132  		}
133
134  		// Clear bits in the first byte to increase the probability
135  		// that the candidate is < max.
136  		bytes &= uint8(int(1<<b) - 1)
137
138  		n.SetBytes(bytes)
139  		if n.Cmp(max) < 0 {
140  			return
141  		}
142  	}
143  }
144
```

View as plain text