diff options
Diffstat (limited to 'src/pkg/crypto/rand')
| -rw-r--r-- | src/pkg/crypto/rand/example_test.go | 29 | ||||
| -rw-r--r-- | src/pkg/crypto/rand/rand_test.go | 16 | ||||
| -rw-r--r-- | src/pkg/crypto/rand/rand_unix.go | 20 | ||||
| -rw-r--r-- | src/pkg/crypto/rand/rand_windows.go | 4 | ||||
| -rw-r--r-- | src/pkg/crypto/rand/util.go | 61 |
5 files changed, 120 insertions, 10 deletions
diff --git a/src/pkg/crypto/rand/example_test.go b/src/pkg/crypto/rand/example_test.go new file mode 100644 index 000000000..5af8e46f5 --- /dev/null +++ b/src/pkg/crypto/rand/example_test.go @@ -0,0 +1,29 @@ +// 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_test + +import ( + "bytes" + "crypto/rand" + "fmt" + "io" +) + +// This example reads 10 cryptographically secure pseudorandom numbers from +// rand.Reader and writes them to a byte slice. +func ExampleRead() { + c := 10 + b := make([]byte, c) + n, err := io.ReadFull(rand.Reader, b) + if n != len(b) || err != nil { + fmt.Println("error:", err) + return + } + // The slice should now contain random bytes instead of only zeroes. + fmt.Println(bytes.Equal(b, make([]byte, c))) + + // Output: + // false +} diff --git a/src/pkg/crypto/rand/rand_test.go b/src/pkg/crypto/rand/rand_test.go index be3a5a221..e46e61d37 100644 --- a/src/pkg/crypto/rand/rand_test.go +++ b/src/pkg/crypto/rand/rand_test.go @@ -7,6 +7,7 @@ package rand import ( "bytes" "compress/flate" + "io" "testing" ) @@ -16,9 +17,9 @@ func TestRead(t *testing.T) { n = 1e5 } b := make([]byte, n) - n, err := Read(b) + n, err := io.ReadFull(Reader, b) if n != len(b) || err != nil { - t.Fatalf("Read(buf) = %d, %s", n, err) + t.Fatalf("ReadFull(buf) = %d, %s", n, err) } var z bytes.Buffer @@ -29,3 +30,14 @@ func TestRead(t *testing.T) { t.Fatalf("Compressed %d -> %d", len(b), z.Len()) } } + +func TestReadEmpty(t *testing.T) { + n, err := Reader.Read(make([]byte, 0)) + if n != 0 || err != nil { + t.Fatalf("Read(make([]byte, 0)) = %d, %v", n, err) + } + n, err = Reader.Read(nil) + if n != 0 || err != nil { + t.Fatalf("Read(nil) = %d, %v", n, err) + } +} diff --git a/src/pkg/crypto/rand/rand_unix.go b/src/pkg/crypto/rand/rand_unix.go index 5eb4cda2b..18f482472 100644 --- a/src/pkg/crypto/rand/rand_unix.go +++ b/src/pkg/crypto/rand/rand_unix.go @@ -2,7 +2,7 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -// +build darwin freebsd linux netbsd openbsd +// +build darwin freebsd linux netbsd openbsd plan9 // Unix cryptographically secure pseudorandom number // generator. @@ -15,6 +15,7 @@ import ( "crypto/cipher" "io" "os" + "runtime" "sync" "time" ) @@ -22,7 +23,13 @@ import ( // Easy implementation: read from /dev/urandom. // This is sufficient on Linux, OS X, and FreeBSD. -func init() { Reader = &devReader{name: "/dev/urandom"} } +func init() { + if runtime.GOOS == "plan9" { + Reader = newReader(nil) + } else { + Reader = &devReader{name: "/dev/urandom"} + } +} // A devReader satisfies reads by reading the file named name. type devReader struct { @@ -39,14 +46,17 @@ func (r *devReader) Read(b []byte) (n int, err error) { if f == nil { return 0, err } - r.f = bufio.NewReader(f) + if runtime.GOOS == "plan9" { + r.f = f + } else { + r.f = bufio.NewReader(f) + } } return r.f.Read(b) } // Alternate pseudo-random implementation for use on -// systems without a reliable /dev/urandom. So far we -// haven't needed it. +// systems without a reliable /dev/urandom. // newReader returns a new pseudorandom generator that // seeds itself by reading from entropy. If entropy == nil, diff --git a/src/pkg/crypto/rand/rand_windows.go b/src/pkg/crypto/rand/rand_windows.go index 2b2bd4bba..82b39b64a 100644 --- a/src/pkg/crypto/rand/rand_windows.go +++ b/src/pkg/crypto/rand/rand_windows.go @@ -35,6 +35,10 @@ func (r *rngReader) Read(b []byte) (n int, err error) { } } r.mu.Unlock() + + if len(b) == 0 { + return 0, nil + } err = syscall.CryptGenRandom(r.prov, uint32(len(b)), &b[0]) if err != nil { return 0, os.NewSyscallError("CryptGenRandom", err) diff --git a/src/pkg/crypto/rand/util.go b/src/pkg/crypto/rand/util.go index 5391c1829..50e5b162b 100644 --- a/src/pkg/crypto/rand/util.go +++ b/src/pkg/crypto/rand/util.go @@ -10,6 +10,21 @@ import ( "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. func Prime(rand io.Reader, bits int) (p *big.Int, err error) { @@ -25,6 +40,8 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err error) { bytes := make([]byte, (bits+7)/8) p = new(big.Int) + bigMod := new(big.Int) + for { _, err = io.ReadFull(rand, bytes) if err != nil { @@ -33,13 +50,51 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err error) { // 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 bit. - bytes[0] |= 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) - if p.ProbablyPrime(20) { + + // 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 { + 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 } } |