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  }
   144
View as plain text