...
Run Format

Source file src/crypto/rand/util.go

Documentation: crypto/rand

  // Copyright 2011 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  package rand
  
  import (
  	"errors"
  	"io"
  	"math/big"
  )
  
  // smallPrimes is a list of small, prime numbers that allows us to rapidly
  // exclude some fraction of composite candidates when searching for a random
  // prime. This list is truncated at the point where smallPrimesProduct exceeds
  // a uint64. It does not include two because we ensure that the candidates are
  // odd by construction.
  var smallPrimes = []uint8{
  	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
  }
  
  // smallPrimesProduct is the product of the values in smallPrimes and allows us
  // to reduce a candidate prime by this number and then determine whether it's
  // coprime to all the elements of smallPrimes without further big.Int
  // operations.
  var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365)
  
  // Prime returns a number, p, of the given size, such that p is prime
  // with high probability.
  // Prime will return error for any error returned by rand.Read or if bits < 2.
  func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
  	if bits < 2 {
  		err = errors.New("crypto/rand: prime size must be at least 2-bit")
  		return
  	}
  
  	b := uint(bits % 8)
  	if b == 0 {
  		b = 8
  	}
  
  	bytes := make([]byte, (bits+7)/8)
  	p = new(big.Int)
  
  	bigMod := new(big.Int)
  
  	for {
  		_, err = io.ReadFull(rand, bytes)
  		if err != nil {
  			return nil, err
  		}
  
  		// Clear bits in the first byte to make sure the candidate has a size <= bits.
  		bytes[0] &= uint8(int(1<<b) - 1)
  		// Don't let the value be too small, i.e, set the most significant two bits.
  		// Setting the top two bits, rather than just the top bit,
  		// means that when two of these values are multiplied together,
  		// the result isn't ever one bit short.
  		if b >= 2 {
  			bytes[0] |= 3 << (b - 2)
  		} else {
  			// Here b==1, because b cannot be zero.
  			bytes[0] |= 1
  			if len(bytes) > 1 {
  				bytes[1] |= 0x80
  			}
  		}
  		// Make the value odd since an even number this large certainly isn't prime.
  		bytes[len(bytes)-1] |= 1
  
  		p.SetBytes(bytes)
  
  		// Calculate the value mod the product of smallPrimes. If it's
  		// a multiple of any of these primes we add two until it isn't.
  		// The probability of overflowing is minimal and can be ignored
  		// because we still perform Miller-Rabin tests on the result.
  		bigMod.Mod(p, smallPrimesProduct)
  		mod := bigMod.Uint64()
  
  	NextDelta:
  		for delta := uint64(0); delta < 1<<20; delta += 2 {
  			m := mod + delta
  			for _, prime := range smallPrimes {
  				if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) {
  					continue NextDelta
  				}
  			}
  
  			if delta > 0 {
  				bigMod.SetUint64(delta)
  				p.Add(p, bigMod)
  			}
  			break
  		}
  
  		// There is a tiny possibility that, by adding delta, we caused
  		// the number to be one bit too long. Thus we check BitLen
  		// here.
  		if p.ProbablyPrime(20) && p.BitLen() == bits {
  			return
  		}
  	}
  }
  
  // Int returns a uniform random value in [0, max). It panics if max <= 0.
  func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
  	if max.Sign() <= 0 {
  		panic("crypto/rand: argument to Int is <= 0")
  	}
  	n = new(big.Int)
  	n.Sub(max, n.SetUint64(1))
  	// bitLen is the maximum bit length needed to encode a value < max.
  	bitLen := n.BitLen()
  	if bitLen == 0 {
  		// the only valid result is 0
  		return
  	}
  	// k is the maximum byte length needed to encode a value < max.
  	k := (bitLen + 7) / 8
  	// b is the number of bits in the most significant byte of max-1.
  	b := uint(bitLen % 8)
  	if b == 0 {
  		b = 8
  	}
  
  	bytes := make([]byte, k)
  
  	for {
  		_, err = io.ReadFull(rand, bytes)
  		if err != nil {
  			return nil, err
  		}
  
  		// Clear bits in the first byte to increase the probability
  		// that the candidate is < max.
  		bytes[0] &= uint8(int(1<<b) - 1)
  
  		n.SetBytes(bytes)
  		if n.Cmp(max) < 0 {
  			return
  		}
  	}
  }
  

View as plain text