libgo/go/crypto/rand/util.go

   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 }