Imported Upstream version 60upstream/60

6 files changed, 330 insertions, 0 deletions

diff --git a/src/pkg/crypto/rand/Makefile b/src/pkg/crypto/rand/Makefile
new file mode 100644
index 000000000..d1a3d45e8
--- /dev/null
+++ b/src/pkg/crypto/rand/Makefile
@@ -0,0 +1,30 @@
+# 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.
+
+include ../../../Make.inc
+
+TARG=crypto/rand
+
+GOFILES=\
+	rand.go\
+	util.go\
+
+GOFILES_freebsd=\
+	rand_unix.go\
+
+GOFILES_darwin=\
+	rand_unix.go\
+
+GOFILES_linux=\
+	rand_unix.go\
+
+GOFILES_openbsd=\
+	rand_unix.go\
+
+GOFILES_windows=\
+	rand_windows.go\
+
+GOFILES+=$(GOFILES_$(GOOS))
+
+include ../../../Make.pkg
diff --git a/src/pkg/crypto/rand/rand.go b/src/pkg/crypto/rand/rand.go
new file mode 100644
index 000000000..42d9da0ef
--- /dev/null
+++ b/src/pkg/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"
+	"os"
+)
+
+// 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.
+func Read(b []byte) (n int, err os.Error) { return Reader.Read(b) }
diff --git a/src/pkg/crypto/rand/rand_test.go b/src/pkg/crypto/rand/rand_test.go
new file mode 100644
index 000000000..bfae7ce4f
--- /dev/null
+++ b/src/pkg/crypto/rand/rand_test.go
@@ -0,0 +1,31 @@
+// 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"
+	"testing"
+)
+
+func TestRead(t *testing.T) {
+	var n int = 4e6
+	if testing.Short() {
+		n = 1e5
+	}
+	b := make([]byte, n)
+	n, err := Read(b)
+	if n != len(b) || err != nil {
+		t.Fatalf("Read(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())
+	}
+}
diff --git a/src/pkg/crypto/rand/rand_unix.go b/src/pkg/crypto/rand/rand_unix.go
new file mode 100644
index 000000000..3a06aa8b1
--- /dev/null
+++ b/src/pkg/crypto/rand/rand_unix.go
@@ -0,0 +1,125 @@
+// 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.
+
+// Unix cryptographically secure pseudorandom number
+// generator.
+
+package rand
+
+import (
+	"bufio"
+	"crypto/aes"
+	"io"
+	"os"
+	"sync"
+	"time"
+)
+
+// Easy implementation: read from /dev/urandom.
+// This is sufficient on Linux, OS X, and FreeBSD.
+
+func init() { Reader = &devReader{name: "/dev/urandom"} }
+
+// A devReader satisfies reads by reading the file named name.
+type devReader struct {
+	name string
+	f    io.Reader
+	mu   sync.Mutex
+}
+
+func (r *devReader) Read(b []byte) (n int, err os.Error) {
+	r.mu.Lock()
+	defer r.mu.Unlock()
+	if r.f == nil {
+		f, err := os.Open(r.name)
+		if f == nil {
+			return 0, err
+		}
+		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.
+
+// 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               *aes.Cipher
+	entropy              io.Reader
+	time, seed, dst, key [aes.BlockSize]byte
+}
+
+func (r *reader) Read(b []byte) (n int, err os.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.Nanoseconds()
+		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/pkg/crypto/rand/rand_windows.go b/src/pkg/crypto/rand/rand_windows.go
new file mode 100755
index 000000000..0eab6b213
--- /dev/null
+++ b/src/pkg/crypto/rand/rand_windows.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.
+
+// 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 os.Error) {
+	r.mu.Lock()
+	if r.prov == 0 {
+		const provType = syscall.PROV_RSA_FULL
+		const flags = syscall.CRYPT_VERIFYCONTEXT | syscall.CRYPT_SILENT
+		errno := syscall.CryptAcquireContext(&r.prov, nil, nil, provType, flags)
+		if errno != 0 {
+			r.mu.Unlock()
+			return 0, os.NewSyscallError("CryptAcquireContext", errno)
+		}
+	}
+	r.mu.Unlock()
+	errno := syscall.CryptGenRandom(r.prov, uint32(len(b)), &b[0])
+	if errno != 0 {
+		return 0, os.NewSyscallError("CryptGenRandom", errno)
+	}
+	return len(b), nil
+}
diff --git a/src/pkg/crypto/rand/util.go b/src/pkg/crypto/rand/util.go
new file mode 100644
index 000000000..77028476e
--- /dev/null
+++ b/src/pkg/crypto/rand/util.go
@@ -0,0 +1,80 @@
+// 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 (
+	"big"
+	"io"
+	"os"
+)
+
+// 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 os.Error) {
+	if bits < 1 {
+		err = os.EINVAL
+	}
+
+	b := uint(bits % 8)
+	if b == 0 {
+		b = 8
+	}
+
+	bytes := make([]byte, (bits+7)/8)
+	p = 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 bit.
+		bytes[0] |= 1 << (b - 1)
+		// Make the value odd since an even number this large certainly isn't prime.
+		bytes[len(bytes)-1] |= 1
+
+		p.SetBytes(bytes)
+		if big.ProbablyPrime(p, 20) {
+			return
+		}
+	}
+
+	return
+}
+
+// Int returns a uniform random value in [0, max).
+func Int(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) {
+	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
+		}
+	}
+
+	return
+}