Source file src/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	}
   144	

View as plain text