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  	"crypto/internal/fips140only"
     9  	"crypto/internal/rand"
    10  	"errors"
    11  	"io"
    12  	"math/big"
    13  )
    14  
    15  // Prime returns a number of the given bit length that is prime with high probability.
    16  // Prime will return error for any error returned by rand.Read or if bits < 2.
    17  //
    18  // Since Go 1.26, a secure source of random bytes is always used, and the Reader is
    19  // ignored unless GODEBUG=cryptocustomrand=1 is set. This setting will be removed
    20  // in a future Go release. Instead, use [testing/cryptotest.SetGlobalRandom].
    21  func Prime(r io.Reader, bits int) (*big.Int, error) {
    22  	if fips140only.Enforced() {
    23  		return nil, errors.New("crypto/rand: use of Prime is not allowed in FIPS 140-only mode")
    24  	}
    25  	if bits < 2 {
    26  		return nil, errors.New("crypto/rand: prime size must be at least 2-bit")
    27  	}
    28  
    29  	r = rand.CustomReader(r)
    30  
    31  	b := uint(bits % 8)
    32  	if b == 0 {
    33  		b = 8
    34  	}
    35  
    36  	bytes := make([]byte, (bits+7)/8)
    37  	p := new(big.Int)
    38  
    39  	for {
    40  		if _, err := io.ReadFull(r, bytes); err != nil {
    41  			return nil, err
    42  		}
    43  
    44  		// Clear bits in the first byte to make sure the candidate has a size <= bits.
    45  		bytes[0] &= uint8(int(1<<b) - 1)
    46  		// Don't let the value be too small, i.e, set the most significant two bits.
    47  		// Setting the top two bits, rather than just the top bit,
    48  		// means that when two of these values are multiplied together,
    49  		// the result isn't ever one bit short.
    50  		if b >= 2 {
    51  			bytes[0] |= 3 << (b - 2)
    52  		} else {
    53  			// Here b==1, because b cannot be zero.
    54  			bytes[0] |= 1
    55  			if len(bytes) > 1 {
    56  				bytes[1] |= 0x80
    57  			}
    58  		}
    59  		// Make the value odd since an even number this large certainly isn't prime.
    60  		bytes[len(bytes)-1] |= 1
    61  
    62  		p.SetBytes(bytes)
    63  		if p.ProbablyPrime(20) {
    64  			return p, nil
    65  		}
    66  	}
    67  }
    68  
    69  // Int returns a uniform random value in [0, max). It panics if max <= 0, and
    70  // returns an error if rand.Read returns one.
    71  func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
    72  	if max.Sign() <= 0 {
    73  		panic("crypto/rand: argument to Int is <= 0")
    74  	}
    75  	n = new(big.Int)
    76  	n.Sub(max, n.SetUint64(1))
    77  	// bitLen is the maximum bit length needed to encode a value < max.
    78  	bitLen := n.BitLen()
    79  	if bitLen == 0 {
    80  		// the only valid result is 0
    81  		return
    82  	}
    83  	// k is the maximum byte length needed to encode a value < max.
    84  	k := (bitLen + 7) / 8
    85  	// b is the number of bits in the most significant byte of max-1.
    86  	b := uint(bitLen % 8)
    87  	if b == 0 {
    88  		b = 8
    89  	}
    90  
    91  	bytes := make([]byte, k)
    92  
    93  	for {
    94  		_, err = io.ReadFull(rand, bytes)
    95  		if err != nil {
    96  			return nil, err
    97  		}
    98  
    99  		// Clear bits in the first byte to increase the probability
   100  		// that the candidate is < max.
   101  		bytes[0] &= uint8(int(1<<b) - 1)
   102  
   103  		n.SetBytes(bytes)
   104  		if n.Cmp(max) < 0 {
   105  			return
   106  		}
   107  	}
   108  }
   109
View as plain text