Imported Upstream version 1.4upstream/1.4

8 files changed, 526 insertions, 0 deletions

diff --git a/src/crypto/rand/example_test.go b/src/crypto/rand/example_test.go
new file mode 100644
index 000000000..8a2717300
--- /dev/null
+++ b/src/crypto/rand/example_test.go
@@ -0,0 +1,28 @@
+// 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"
+)
+
+// 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)
+	_, err := rand.Read(b)
+	if 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/crypto/rand/rand.go b/src/crypto/rand/rand.go
new file mode 100644
index 000000000..4da3adb70
--- /dev/null
+++ b/src/crypto/rand/rand.go
@@ -0,0 +1,21 @@
+// Copyright 2010 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 implements a cryptographically secure
+// pseudorandom number generator.
+package rand
+
+import "io"
+
+// Reader is a global, shared instance of a cryptographically
+// strong pseudo-random generator.
+// On Unix-like systems, Reader reads from /dev/urandom.
+// On Windows systems, Reader uses the CryptGenRandom API.
+var Reader io.Reader
+
+// Read is a helper function that calls Reader.Read using io.ReadFull.
+// On return, n == len(b) if and only if err == nil.
+func Read(b []byte) (n int, err error) {
+	return io.ReadFull(Reader, b)
+}
diff --git a/src/crypto/rand/rand_linux.go b/src/crypto/rand/rand_linux.go
new file mode 100644
index 000000000..8cb59c75d
--- /dev/null
+++ b/src/crypto/rand/rand_linux.go
@@ -0,0 +1,39 @@
+// Copyright 2014 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
+
+import (
+	"internal/syscall"
+	"sync"
+)
+
+func init() {
+	altGetRandom = getRandomLinux
+}
+
+var (
+	once       sync.Once
+	useSyscall bool
+)
+
+func pickStrategy() {
+	// Test whether we should use the system call or /dev/urandom.
+	// We'll fall back to urandom if:
+	// - the kernel is too old (before 3.17)
+	// - the machine has no entropy available (early boot + no hardware
+	//   entropy source?) and we want to avoid blocking later.
+	var buf [1]byte
+	n, err := syscall.GetRandom(buf[:], syscall.GRND_NONBLOCK)
+	useSyscall = n == 1 && err == nil
+}
+
+func getRandomLinux(p []byte) (ok bool) {
+	once.Do(pickStrategy)
+	if !useSyscall {
+		return false
+	}
+	n, err := syscall.GetRandom(p, 0)
+	return n == len(p) && err == nil
+}
diff --git a/src/crypto/rand/rand_test.go b/src/crypto/rand/rand_test.go
new file mode 100644
index 000000000..e46e61d37
--- /dev/null
+++ b/src/crypto/rand/rand_test.go
@@ -0,0 +1,43 @@
+// Copyright 2010 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
+
+import (
+	"bytes"
+	"compress/flate"
+	"io"
+	"testing"
+)
+
+func TestRead(t *testing.T) {
+	var n int = 4e6
+	if testing.Short() {
+		n = 1e5
+	}
+	b := make([]byte, n)
+	n, err := io.ReadFull(Reader, b)
+	if n != len(b) || err != nil {
+		t.Fatalf("ReadFull(buf) = %d, %s", n, err)
+	}
+
+	var z bytes.Buffer
+	f, _ := flate.NewWriter(&z, 5)
+	f.Write(b)
+	f.Close()
+	if z.Len() < len(b)*99/100 {
+		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/crypto/rand/rand_unix.go b/src/crypto/rand/rand_unix.go
new file mode 100644
index 000000000..62d0fbdb3
--- /dev/null
+++ b/src/crypto/rand/rand_unix.go
@@ -0,0 +1,147 @@
+// Copyright 2010 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.
+
+// +build darwin dragonfly freebsd linux nacl netbsd openbsd plan9 solaris
+
+// Unix cryptographically secure pseudorandom number
+// generator.
+
+package rand
+
+import (
+	"bufio"
+	"crypto/aes"
+	"crypto/cipher"
+	"io"
+	"os"
+	"runtime"
+	"sync"
+	"time"
+)
+
+const urandomDevice = "/dev/urandom"
+
+// Easy implementation: read from /dev/urandom.
+// This is sufficient on Linux, OS X, and FreeBSD.
+
+func init() {
+	if runtime.GOOS == "plan9" {
+		Reader = newReader(nil)
+	} else {
+		Reader = &devReader{name: urandomDevice}
+	}
+}
+
+// A devReader satisfies reads by reading the file named name.
+type devReader struct {
+	name string
+	f    io.Reader
+	mu   sync.Mutex
+}
+
+// altGetRandom if non-nil specifies an OS-specific function to get
+// urandom-style randomness.
+var altGetRandom func([]byte) (ok bool)
+
+func (r *devReader) Read(b []byte) (n int, err error) {
+	if altGetRandom != nil && r.name == urandomDevice && altGetRandom(b) {
+		return len(b), nil
+	}
+	r.mu.Lock()
+	defer r.mu.Unlock()
+	if r.f == nil {
+		f, err := os.Open(r.name)
+		if f == nil {
+			return 0, err
+		}
+		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.
+
+// newReader returns a new pseudorandom generator that
+// seeds itself by reading from entropy.  If entropy == nil,
+// the generator seeds itself by reading from the system's
+// random number generator, typically /dev/random.
+// The Read method on the returned reader always returns
+// the full amount asked for, or else it returns an error.
+//
+// The generator uses the X9.31 algorithm with AES-128,
+// reseeding after every 1 MB of generated data.
+func newReader(entropy io.Reader) io.Reader {
+	if entropy == nil {
+		entropy = &devReader{name: "/dev/random"}
+	}
+	return &reader{entropy: entropy}
+}
+
+type reader struct {
+	mu                   sync.Mutex
+	budget               int // number of bytes that can be generated
+	cipher               cipher.Block
+	entropy              io.Reader
+	time, seed, dst, key [aes.BlockSize]byte
+}
+
+func (r *reader) Read(b []byte) (n int, err error) {
+	r.mu.Lock()
+	defer r.mu.Unlock()
+	n = len(b)
+
+	for len(b) > 0 {
+		if r.budget == 0 {
+			_, err := io.ReadFull(r.entropy, r.seed[0:])
+			if err != nil {
+				return n - len(b), err
+			}
+			_, err = io.ReadFull(r.entropy, r.key[0:])
+			if err != nil {
+				return n - len(b), err
+			}
+			r.cipher, err = aes.NewCipher(r.key[0:])
+			if err != nil {
+				return n - len(b), err
+			}
+			r.budget = 1 << 20 // reseed after generating 1MB
+		}
+		r.budget -= aes.BlockSize
+
+		// ANSI X9.31 (== X9.17) algorithm, but using AES in place of 3DES.
+		//
+		// single block:
+		// t = encrypt(time)
+		// dst = encrypt(t^seed)
+		// seed = encrypt(t^dst)
+		ns := time.Now().UnixNano()
+		r.time[0] = byte(ns >> 56)
+		r.time[1] = byte(ns >> 48)
+		r.time[2] = byte(ns >> 40)
+		r.time[3] = byte(ns >> 32)
+		r.time[4] = byte(ns >> 24)
+		r.time[5] = byte(ns >> 16)
+		r.time[6] = byte(ns >> 8)
+		r.time[7] = byte(ns)
+		r.cipher.Encrypt(r.time[0:], r.time[0:])
+		for i := 0; i < aes.BlockSize; i++ {
+			r.dst[i] = r.time[i] ^ r.seed[i]
+		}
+		r.cipher.Encrypt(r.dst[0:], r.dst[0:])
+		for i := 0; i < aes.BlockSize; i++ {
+			r.seed[i] = r.time[i] ^ r.dst[i]
+		}
+		r.cipher.Encrypt(r.seed[0:], r.seed[0:])
+
+		m := copy(b, r.dst[0:])
+		b = b[m:]
+	}
+
+	return n, nil
+}
diff --git a/src/crypto/rand/rand_windows.go b/src/crypto/rand/rand_windows.go
new file mode 100644
index 000000000..82b39b64a
--- /dev/null
+++ b/src/crypto/rand/rand_windows.go
@@ -0,0 +1,47 @@
+// Copyright 2010 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.
+
+// Windows cryptographically secure pseudorandom number
+// generator.
+
+package rand
+
+import (
+	"os"
+	"sync"
+	"syscall"
+)
+
+// Implemented by using Windows CryptoAPI 2.0.
+
+func init() { Reader = &rngReader{} }
+
+// A rngReader satisfies reads by reading from the Windows CryptGenRandom API.
+type rngReader struct {
+	prov syscall.Handle
+	mu   sync.Mutex
+}
+
+func (r *rngReader) Read(b []byte) (n int, err error) {
+	r.mu.Lock()
+	if r.prov == 0 {
+		const provType = syscall.PROV_RSA_FULL
+		const flags = syscall.CRYPT_VERIFYCONTEXT | syscall.CRYPT_SILENT
+		err := syscall.CryptAcquireContext(&r.prov, nil, nil, provType, flags)
+		if err != nil {
+			r.mu.Unlock()
+			return 0, os.NewSyscallError("CryptAcquireContext", err)
+		}
+	}
+	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)
+	}
+	return len(b), nil
+}
diff --git a/src/crypto/rand/util.go b/src/crypto/rand/util.go
new file mode 100644
index 000000000..5f7440785
--- /dev/null
+++ b/src/crypto/rand/util.go
@@ -0,0 +1,136 @@
+// 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
+
+import (
+	"errors"
+	"io"
+	"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.
+// Prime will return error for any error returned by rand.Read or if bits < 2.
+func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
+	if bits < 2 {
+		err = errors.New("crypto/rand: prime size must be at least 2-bit")
+		return
+	}
+
+	b := uint(bits % 8)
+	if b == 0 {
+		b = 8
+	}
+
+	bytes := make([]byte, (bits+7)/8)
+	p = new(big.Int)
+
+	bigMod := new(big.Int)
+
+	for {
+		_, err = io.ReadFull(rand, bytes)
+		if err != nil {
+			return nil, err
+		}
+
+		// 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 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)
+
+		// 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 && (bits > 6 || m != uint64(prime)) {
+					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
+		}
+	}
+}
+
+// Int returns a uniform random value in [0, max). It panics if max <= 0.
+func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
+	if max.Sign() <= 0 {
+		panic("crypto/rand: argument to Int is <= 0")
+	}
+	k := (max.BitLen() + 7) / 8
+
+	// b is the number of bits in the most significant byte of max.
+	b := uint(max.BitLen() % 8)
+	if b == 0 {
+		b = 8
+	}
+
+	bytes := make([]byte, k)
+	n = new(big.Int)
+
+	for {
+		_, err = io.ReadFull(rand, bytes)
+		if err != nil {
+			return nil, err
+		}
+
+		// Clear bits in the first byte to increase the probability
+		// that the candidate is < max.
+		bytes[0] &= uint8(int(1<<b) - 1)
+
+		n.SetBytes(bytes)
+		if n.Cmp(max) < 0 {
+			return
+		}
+	}
+}
diff --git a/src/crypto/rand/util_test.go b/src/crypto/rand/util_test.go
new file mode 100644
index 000000000..1e2a4dd84
--- /dev/null
+++ b/src/crypto/rand/util_test.go
@@ -0,0 +1,65 @@
+// Copyright 2013 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 (
+	"crypto/rand"
+	"math/big"
+	"testing"
+)
+
+// http://golang.org/issue/6849.
+func TestPrimeSmall(t *testing.T) {
+	for n := 2; n < 10; n++ {
+		p, err := rand.Prime(rand.Reader, n)
+		if err != nil {
+			t.Fatalf("Can't generate %d-bit prime: %v", n, err)
+		}
+		if p.BitLen() != n {
+			t.Fatalf("%v is not %d-bit", p, n)
+		}
+		if !p.ProbablyPrime(32) {
+			t.Fatalf("%v is not prime", p)
+		}
+	}
+}
+
+// Test that passing bits < 2 causes Prime to return nil, error
+func TestPrimeBitsLt2(t *testing.T) {
+	if p, err := rand.Prime(rand.Reader, 1); p != nil || err == nil {
+		t.Errorf("Prime should return nil, error when called with bits < 2")
+	}
+}
+
+func TestInt(t *testing.T) {
+	// start at 128 so the case of (max.BitLen() % 8) == 0 is covered
+	for n := 128; n < 140; n++ {
+		b := new(big.Int).SetInt64(int64(n))
+		if i, err := rand.Int(rand.Reader, b); err != nil {
+			t.Fatalf("Can't generate random value: %v, %v", i, err)
+		}
+	}
+}
+
+func testIntPanics(t *testing.T, b *big.Int) {
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Int should panic when called with max <= 0: %v", b)
+		}
+	}()
+	rand.Int(rand.Reader, b)
+}
+
+// Test that passing a new big.Int as max causes Int to panic
+func TestIntEmptyMaxPanics(t *testing.T) {
+	b := new(big.Int)
+	testIntPanics(t, b)
+}
+
+// Test that passing a negative value as max causes Int to panic
+func TestIntNegativeMaxPanics(t *testing.T) {
+	b := new(big.Int).SetInt64(int64(-1))
+	testIntPanics(t, b)
+}