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 = (&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 := []byte{:(bits+7)/8}
43 p = &big.Int{}
44 45 bigMod := &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[0] &= 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[0] |= 3 << (b - 2)
61 } else {
62 // Here b==1, because b cannot be zero.
63 bytes[0] |= 1
64 if len(bytes) > 1 {
65 bytes[1] |= 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 = &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 := []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[0] &= uint8(int(1<<b) - 1)
137 138 n.SetBytes(bytes)
139 if n.Cmp(max) < 0 {
140 return
141 }
142 }
143 }
144