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

2  // Use of this source code is governed by a BSD-style
4
5  package rand
6
7  import (
8  	"crypto/internal/randutil"
9  	"errors"
10  	"io"
11  	"math/big"
12  )
13
14  // Prime returns a number of the given bit length that is prime with high probability.
15  // Prime will return error for any error returned by [rand.Read] or if bits < 2.
16  func Prime(rand io.Reader, bits int) (*big.Int, error) {
17  	if bits < 2 {
18  		return nil, errors.New("crypto/rand: prime size must be at least 2-bit")
19  	}
20
22
23  	b := uint(bits % 8)
24  	if b == 0 {
25  		b = 8
26  	}
27
28  	bytes := make([]byte, (bits+7)/8)
29  	p := new(big.Int)
30
31  	for {
32  		if _, err := io.ReadFull(rand, bytes); err != nil {
33  			return nil, err
34  		}
35
36  		// Clear bits in the first byte to make sure the candidate has a size <= bits.
37  		bytes[0] &= uint8(int(1<<b) - 1)
38  		// Don't let the value be too small, i.e, set the most significant two bits.
39  		// Setting the top two bits, rather than just the top bit,
40  		// means that when two of these values are multiplied together,
41  		// the result isn't ever one bit short.
42  		if b >= 2 {
43  			bytes[0] |= 3 << (b - 2)
44  		} else {
45  			// Here b==1, because b cannot be zero.
46  			bytes[0] |= 1
47  			if len(bytes) > 1 {
48  				bytes[1] |= 0x80
49  			}
50  		}
51  		// Make the value odd since an even number this large certainly isn't prime.
52  		bytes[len(bytes)-1] |= 1
53
54  		p.SetBytes(bytes)
55  		if p.ProbablyPrime(20) {
56  			return p, nil
57  		}
58  	}
59  }
60
61  // Int returns a uniform random value in [0, max). It panics if max <= 0.
62  func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
63  	if max.Sign() <= 0 {
64  		panic("crypto/rand: argument to Int is <= 0")
65  	}
66  	n = new(big.Int)
67  	n.Sub(max, n.SetUint64(1))
68  	// bitLen is the maximum bit length needed to encode a value < max.
69  	bitLen := n.BitLen()
70  	if bitLen == 0 {
71  		// the only valid result is 0
72  		return
73  	}
74  	// k is the maximum byte length needed to encode a value < max.
75  	k := (bitLen + 7) / 8
76  	// b is the number of bits in the most significant byte of max-1.
77  	b := uint(bitLen % 8)
78  	if b == 0 {
79  		b = 8
80  	}
81
82  	bytes := make([]byte, k)
83
84  	for {
85  		_, err = io.ReadFull(rand, bytes)
86  		if err != nil {
87  			return nil, err
88  		}
89
90  		// Clear bits in the first byte to increase the probability
91  		// that the candidate is < max.
92  		bytes[0] &= uint8(int(1<<b) - 1)
93
94  		n.SetBytes(bytes)
95  		if n.Cmp(max) < 0 {
96  			return
97  		}
98  	}
99  }
100

View as plain text