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
5package rand
6
7import (
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.
16func 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
21	randutil.MaybeReadByte(rand)
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.
62func 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