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 = new(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 := make([]byte, (bits+7)/8) 43 p = new(big.Int) 44 45 bigMod := new(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 = new(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 := make([]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