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	"errors"
9	"io"
10	"math/big"
11)
12
13var bigZero = big.NewInt(0)
14var bigOne = big.NewInt(1)
15var bigTwo = big.NewInt(2)
16
17// smallPrimes is a list of small, prime numbers that allows us to rapidly
18// exclude some fraction of composite candidates when searching for a random
19// prime. This list is truncated at the point where smallPrimesProduct exceeds
20// a uint64. It does not include two because we ensure that the candidates are
21// odd by construction.
22var smallPrimes = []uint8{
23	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
24}
25
26// smallPrimesProduct is the product of the values in smallPrimes and allows us
27// to reduce a candidate prime by this number and then determine whether it's
28// coprime to all the elements of smallPrimes without further big.Int
29// operations.
30var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365)
31
32var mediumPrimes = []uint16{
33	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
34	59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
35	103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
36	157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
37	211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
38	269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
39	331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
40	389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
41	449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
42	509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
43	587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
44	643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
45	709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
46	773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
47	853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
48	919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
49	991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
50	1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
51	1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
52	1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
53	1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
54	1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
55	1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
56	1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
57	1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
58	1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
59	1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
60	1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
61	1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
62	1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
63	1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
64	1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
65	1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
66	1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
67	2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
68	2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
69	2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
70	2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
71	2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
72	2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
73	2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
74	2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
75	2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
76	2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
77	2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
78	2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
79	2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
80	2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
81	2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
82	3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
83	3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
84	3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
85	3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
86	3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
87	3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
88	3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
89	3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
90	3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
91	3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
92	3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
93	3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
94	3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
95	3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
96	3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
97	4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
98	4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
99	4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
100	4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
101	4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
102	4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
103	4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
104	4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
105	4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
106	4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
107	4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
108	4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
109	4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
110	4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
111	4957, 4967, 4969, 4973, 4987, 4993, 4999,
112}
113
114// Prime returns a number, p, of the given size, such that p is prime
115// with high probability.
116// Prime will return error for any error returned by rand.Read or if bits < 2.
117func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
118	if bits < 2 {
119		err = errors.New("crypto/rand: prime size must be at least 2-bit")
120		return
121	}
122
123	p, err = initializeRandom(rand, bits)
124	if err != nil {
125		return
126	}
127
128	bigMod := new(big.Int)
129
130	for {
131		if (p.BitLen() > bits) {
132			p, err = initializeRandom(rand, bits)
133			if err != nil {
134				return
135			}
136		} else {
137			p = p.Add(p, bigTwo)
138		}
139
140	DeltaAgain:
141		for {
142			// Calculate the value mod the product of smallPrimes. If it's
143			// a multiple of any of these primes we add two until it isn't.
144			// The probability of overflowing is minimal and can be ignored
145			// because we still perform Miller-Rabin tests on the result.
146			bigMod.Mod(p, smallPrimesProduct)
147			mod := bigMod.Uint64()
148
149		NextDelta:
150			for delta := uint64(0); delta < 1<<20; delta += 2 {
151				m := mod + delta
152				for _, prime := range smallPrimes {
153					if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) {
154						continue NextDelta
155					}
156				}
157
158				if delta > 0 {
159					bigMod.SetUint64(delta)
160					p.Add(p, bigMod)
161				}
162				break
163			}
164
165			bigPrime := new(big.Int)
166			for _, prime := range mediumPrimes {
167				bigPrime.SetUint64(uint64(prime))
168				if bigMod.Mod(p, bigPrime).Cmp(bigZero) == 0 {
169					p.Add(p, bigTwo)
170					continue DeltaAgain
171				}
172			}
173			break
174		}
175		// There is a tiny possibility that, by adding delta, we caused
176		// the number to be one bit too long. Thus we check BitLen
177		// here.
178		if p.ProbablyPrime(20) && p.BitLen() == bits {
179			return
180		}
181	}
182}
183
184// Int returns a uniform random value in [0, max). It panics if max <= 0.
185func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
186	if max.Sign() <= 0 {
187		panic("crypto/rand: argument to Int is <= 0")
188	}
189	n = new(big.Int)
190	n.Sub(max, n.SetUint64(1))
191	// bitLen is the maximum bit length needed to encode a value < max.
192	bitLen := n.BitLen()
193	if bitLen == 0 {
194		// the only valid result is 0
195		return
196	}
197	// k is the maximum byte length needed to encode a value < max.
198	k := (bitLen + 7) / 8
199	// b is the number of bits in the most significant byte of max-1.
200	b := uint(bitLen % 8)
201	if b == 0 {
202		b = 8
203	}
204
205	bytes := make([]byte, k)
206
207	for {
208		_, err = io.ReadFull(rand, bytes)
209		if err != nil {
210			return nil, err
211		}
212
213		// Clear bits in the first byte to increase the probability
214		// that the candidate is < max.
215		bytes[0] &= uint8(int(1<<b) - 1)
216
217		n.SetBytes(bytes)
218		if n.Cmp(max) < 0 {
219			return
220		}
221	}
222}
223
224func initializeRandom(rand io.Reader, bits int) (p *big.Int, err error){
225	p = new(big.Int)
226
227	b := uint(bits % 8)
228	if b == 0 {
229		b = 8
230	}
231
232	bytes := make([]byte, (bits+7)/8)
233
234	_, err = io.ReadFull(rand, bytes)
235	if err != nil {
236		return nil, err
237	}
238
239	// Clear bits in the first byte to make sure the candidate has a size <= bits.
240	bytes[0] &= uint8(int(1<<b) - 1)
241	// Don't let the value be too small, i.e, set the most significant two bits.
242	// Setting the top two bits, rather than just the top bit,
243	// means that when two of these values are multiplied together,
244	// the result isn't ever one bit short.
245	if b >= 2 {
246		bytes[0] |= 3 << (b - 2)
247	} else {
248		// Here b==1, because b cannot be zero.
249		bytes[0] |= 1
250		if len(bytes) > 1 {
251			bytes[1] |= 0x80
252		}
253	}
254	// Make the value odd since an even number this large certainly isn't prime.
255	bytes[len(bytes)-1] |= 1
256
257	p.SetBytes(bytes)
258
259	return
260}
261