Source file src/pkg/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 // Prime returns a number, p, of the given size, such that p is prime 14 // with high probability. 15 func Prime(rand io.Reader, bits int) (p *big.Int, err error) { 16 if bits < 1 { 17 err = errors.New("crypto/rand: prime size must be positive") 18 } 19 20 b := uint(bits % 8) 21 if b == 0 { 22 b = 8 23 } 24 25 bytes := make([]byte, (bits+7)/8) 26 p = new(big.Int) 27 28 for { 29 _, err = io.ReadFull(rand, bytes) 30 if err != nil { 31 return nil, err 32 } 33 34 // Clear bits in the first byte to make sure the candidate has a size <= bits. 35 bytes[0] &= uint8(int(1<<b) - 1) 36 // Don't let the value be too small, i.e, set the most significant bit. 37 bytes[0] |= 1 << (b - 1) 38 // Make the value odd since an even number this large certainly isn't prime. 39 bytes[len(bytes)-1] |= 1 40 41 p.SetBytes(bytes) 42 if p.ProbablyPrime(20) { 43 return 44 } 45 } 46 47 return 48 } 49 50 // Int returns a uniform random value in [0, max). 51 func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) { 52 k := (max.BitLen() + 7) / 8 53 54 // b is the number of bits in the most significant byte of max. 55 b := uint(max.BitLen() % 8) 56 if b == 0 { 57 b = 8 58 } 59 60 bytes := make([]byte, k) 61 n = new(big.Int) 62 63 for { 64 _, err = io.ReadFull(rand, bytes) 65 if err != nil { 66 return nil, err 67 } 68 69 // Clear bits in the first byte to increase the probability 70 // that the candidate is < max. 71 bytes[0] &= uint8(int(1<<b) - 1) 72 73 n.SetBytes(bytes) 74 if n.Cmp(max) < 0 { 75 return 76 } 77 } 78 79 return 80 }