Home | History | Annotate | Download | only in rand 
      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