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