build: move package sources from src/pkg to src

Preparation was in CL 134570043.
This CL contains only the effect of 'hg mv src/pkg/* src'.
For more about the move, see golang.org/s/go14nopkg.

7 files changed, 2058 insertions, 0 deletions

diff --git a/src/crypto/rsa/pkcs1v15.go b/src/crypto/rsa/pkcs1v15.go
new file mode 100644
index 000000000..59e8bb5b7
--- /dev/null
+++ b/src/crypto/rsa/pkcs1v15.go
@@ -0,0 +1,292 @@
+// Copyright 2009 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 rsa
+
+import (
+	"crypto"
+	"crypto/subtle"
+	"errors"
+	"io"
+	"math/big"
+)
+
+// This file implements encryption and decryption using PKCS#1 v1.5 padding.
+
+// EncryptPKCS1v15 encrypts the given message with RSA and the padding scheme from PKCS#1 v1.5.
+// The message must be no longer than the length of the public modulus minus 11 bytes.
+// WARNING: use of this function to encrypt plaintexts other than session keys
+// is dangerous. Use RSA OAEP in new protocols.
+func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) (out []byte, err error) {
+	if err := checkPub(pub); err != nil {
+		return nil, err
+	}
+	k := (pub.N.BitLen() + 7) / 8
+	if len(msg) > k-11 {
+		err = ErrMessageTooLong
+		return
+	}
+
+	// EM = 0x00 || 0x02 || PS || 0x00 || M
+	em := make([]byte, k)
+	em[1] = 2
+	ps, mm := em[2:len(em)-len(msg)-1], em[len(em)-len(msg):]
+	err = nonZeroRandomBytes(ps, rand)
+	if err != nil {
+		return
+	}
+	em[len(em)-len(msg)-1] = 0
+	copy(mm, msg)
+
+	m := new(big.Int).SetBytes(em)
+	c := encrypt(new(big.Int), pub, m)
+
+	copyWithLeftPad(em, c.Bytes())
+	out = em
+	return
+}
+
+// DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS#1 v1.5.
+// If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
+func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (out []byte, err error) {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return nil, err
+	}
+	valid, out, index, err := decryptPKCS1v15(rand, priv, ciphertext)
+	if err != nil {
+		return
+	}
+	if valid == 0 {
+		return nil, ErrDecryption
+	}
+	out = out[index:]
+	return
+}
+
+// DecryptPKCS1v15SessionKey decrypts a session key using RSA and the padding scheme from PKCS#1 v1.5.
+// If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
+// It returns an error if the ciphertext is the wrong length or if the
+// ciphertext is greater than the public modulus. Otherwise, no error is
+// returned. If the padding is valid, the resulting plaintext message is copied
+// into key. Otherwise, key is unchanged. These alternatives occur in constant
+// time. It is intended that the user of this function generate a random
+// session key beforehand and continue the protocol with the resulting value.
+// This will remove any possibility that an attacker can learn any information
+// about the plaintext.
+// See ``Chosen Ciphertext Attacks Against Protocols Based on the RSA
+// Encryption Standard PKCS #1'', Daniel Bleichenbacher, Advances in Cryptology
+// (Crypto '98).
+func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []byte, key []byte) (err error) {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return err
+	}
+	k := (priv.N.BitLen() + 7) / 8
+	if k-(len(key)+3+8) < 0 {
+		return ErrDecryption
+	}
+
+	valid, em, index, err := decryptPKCS1v15(rand, priv, ciphertext)
+	if err != nil {
+		return
+	}
+
+	if len(em) != k {
+		// This should be impossible because decryptPKCS1v15 always
+		// returns the full slice.
+		return ErrDecryption
+	}
+
+	valid &= subtle.ConstantTimeEq(int32(len(em)-index), int32(len(key)))
+	subtle.ConstantTimeCopy(valid, key, em[len(em)-len(key):])
+	return
+}
+
+// decryptPKCS1v15 decrypts ciphertext using priv and blinds the operation if
+// rand is not nil. It returns one or zero in valid that indicates whether the
+// plaintext was correctly structured. In either case, the plaintext is
+// returned in em so that it may be read independently of whether it was valid
+// in order to maintain constant memory access patterns. If the plaintext was
+// valid then index contains the index of the original message in em.
+func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
+	k := (priv.N.BitLen() + 7) / 8
+	if k < 11 {
+		err = ErrDecryption
+		return
+	}
+
+	c := new(big.Int).SetBytes(ciphertext)
+	m, err := decrypt(rand, priv, c)
+	if err != nil {
+		return
+	}
+
+	em = leftPad(m.Bytes(), k)
+	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
+	secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)
+
+	// The remainder of the plaintext must be a string of non-zero random
+	// octets, followed by a 0, followed by the message.
+	//   lookingForIndex: 1 iff we are still looking for the zero.
+	//   index: the offset of the first zero byte.
+	lookingForIndex := 1
+
+	for i := 2; i < len(em); i++ {
+		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
+		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
+		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
+	}
+
+	// The PS padding must be at least 8 bytes long, and it starts two
+	// bytes into em.
+	validPS := subtle.ConstantTimeLessOrEq(2+8, index)
+
+	valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1) & validPS
+	index = subtle.ConstantTimeSelect(valid, index+1, 0)
+	return valid, em, index, nil
+}
+
+// nonZeroRandomBytes fills the given slice with non-zero random octets.
+func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) {
+	_, err = io.ReadFull(rand, s)
+	if err != nil {
+		return
+	}
+
+	for i := 0; i < len(s); i++ {
+		for s[i] == 0 {
+			_, err = io.ReadFull(rand, s[i:i+1])
+			if err != nil {
+				return
+			}
+			// In tests, the PRNG may return all zeros so we do
+			// this to break the loop.
+			s[i] ^= 0x42
+		}
+	}
+
+	return
+}
+
+// These are ASN1 DER structures:
+//   DigestInfo ::= SEQUENCE {
+//     digestAlgorithm AlgorithmIdentifier,
+//     digest OCTET STRING
+//   }
+// For performance, we don't use the generic ASN1 encoder. Rather, we
+// precompute a prefix of the digest value that makes a valid ASN1 DER string
+// with the correct contents.
+var hashPrefixes = map[crypto.Hash][]byte{
+	crypto.MD5:       {0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10},
+	crypto.SHA1:      {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14},
+	crypto.SHA224:    {0x30, 0x2d, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x05, 0x00, 0x04, 0x1c},
+	crypto.SHA256:    {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20},
+	crypto.SHA384:    {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30},
+	crypto.SHA512:    {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40},
+	crypto.MD5SHA1:   {}, // A special TLS case which doesn't use an ASN1 prefix.
+	crypto.RIPEMD160: {0x30, 0x20, 0x30, 0x08, 0x06, 0x06, 0x28, 0xcf, 0x06, 0x03, 0x00, 0x31, 0x04, 0x14},
+}
+
+// SignPKCS1v15 calculates the signature of hashed using RSASSA-PKCS1-V1_5-SIGN from RSA PKCS#1 v1.5.
+// Note that hashed must be the result of hashing the input message using the
+// given hash function. If hash is zero, hashed is signed directly. This isn't
+// advisable except for interoperability.
+func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte) (s []byte, err error) {
+	hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
+	if err != nil {
+		return
+	}
+
+	tLen := len(prefix) + hashLen
+	k := (priv.N.BitLen() + 7) / 8
+	if k < tLen+11 {
+		return nil, ErrMessageTooLong
+	}
+
+	// EM = 0x00 || 0x01 || PS || 0x00 || T
+	em := make([]byte, k)
+	em[1] = 1
+	for i := 2; i < k-tLen-1; i++ {
+		em[i] = 0xff
+	}
+	copy(em[k-tLen:k-hashLen], prefix)
+	copy(em[k-hashLen:k], hashed)
+
+	m := new(big.Int).SetBytes(em)
+	c, err := decrypt(rand, priv, m)
+	if err != nil {
+		return
+	}
+
+	copyWithLeftPad(em, c.Bytes())
+	s = em
+	return
+}
+
+// VerifyPKCS1v15 verifies an RSA PKCS#1 v1.5 signature.
+// hashed is the result of hashing the input message using the given hash
+// function and sig is the signature. A valid signature is indicated by
+// returning a nil error. If hash is zero then hashed is used directly. This
+// isn't advisable except for interoperability.
+func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte) (err error) {
+	hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
+	if err != nil {
+		return
+	}
+
+	tLen := len(prefix) + hashLen
+	k := (pub.N.BitLen() + 7) / 8
+	if k < tLen+11 {
+		err = ErrVerification
+		return
+	}
+
+	c := new(big.Int).SetBytes(sig)
+	m := encrypt(new(big.Int), pub, c)
+	em := leftPad(m.Bytes(), k)
+	// EM = 0x00 || 0x01 || PS || 0x00 || T
+
+	ok := subtle.ConstantTimeByteEq(em[0], 0)
+	ok &= subtle.ConstantTimeByteEq(em[1], 1)
+	ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed)
+	ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix)
+	ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0)
+
+	for i := 2; i < k-tLen-1; i++ {
+		ok &= subtle.ConstantTimeByteEq(em[i], 0xff)
+	}
+
+	if ok != 1 {
+		return ErrVerification
+	}
+
+	return nil
+}
+
+func pkcs1v15HashInfo(hash crypto.Hash, inLen int) (hashLen int, prefix []byte, err error) {
+	// Special case: crypto.Hash(0) is used to indicate that the data is
+	// signed directly.
+	if hash == 0 {
+		return inLen, nil, nil
+	}
+
+	hashLen = hash.Size()
+	if inLen != hashLen {
+		return 0, nil, errors.New("crypto/rsa: input must be hashed message")
+	}
+	prefix, ok := hashPrefixes[hash]
+	if !ok {
+		return 0, nil, errors.New("crypto/rsa: unsupported hash function")
+	}
+	return
+}
+
+// copyWithLeftPad copies src to the end of dest, padding with zero bytes as
+// needed.
+func copyWithLeftPad(dest, src []byte) {
+	numPaddingBytes := len(dest) - len(src)
+	for i := 0; i < numPaddingBytes; i++ {
+		dest[i] = 0
+	}
+	copy(dest[numPaddingBytes:], src)
+}
diff --git a/src/crypto/rsa/pkcs1v15_test.go b/src/crypto/rsa/pkcs1v15_test.go
new file mode 100644
index 000000000..2dc5dbc2c
--- /dev/null
+++ b/src/crypto/rsa/pkcs1v15_test.go
@@ -0,0 +1,271 @@
+// Copyright 2009 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 rsa
+
+import (
+	"bytes"
+	"crypto"
+	"crypto/rand"
+	"crypto/sha1"
+	"encoding/base64"
+	"encoding/hex"
+	"io"
+	"math/big"
+	"testing"
+	"testing/quick"
+)
+
+func decodeBase64(in string) []byte {
+	out := make([]byte, base64.StdEncoding.DecodedLen(len(in)))
+	n, err := base64.StdEncoding.Decode(out, []byte(in))
+	if err != nil {
+		return nil
+	}
+	return out[0:n]
+}
+
+type DecryptPKCS1v15Test struct {
+	in, out string
+}
+
+// These test vectors were generated with `openssl rsautl -pkcs -encrypt`
+var decryptPKCS1v15Tests = []DecryptPKCS1v15Test{
+	{
+		"gIcUIoVkD6ATMBk/u/nlCZCCWRKdkfjCgFdo35VpRXLduiKXhNz1XupLLzTXAybEq15juc+EgY5o0DHv/nt3yg==",
+		"x",
+	},
+	{
+		"Y7TOCSqofGhkRb+jaVRLzK8xw2cSo1IVES19utzv6hwvx+M8kFsoWQm5DzBeJCZTCVDPkTpavUuEbgp8hnUGDw==",
+		"testing.",
+	},
+	{
+		"arReP9DJtEVyV2Dg3dDp4c/PSk1O6lxkoJ8HcFupoRorBZG+7+1fDAwT1olNddFnQMjmkb8vxwmNMoTAT/BFjQ==",
+		"testing.\n",
+	},
+	{
+		"WtaBXIoGC54+vH0NH0CHHE+dRDOsMc/6BrfFu2lEqcKL9+uDuWaf+Xj9mrbQCjjZcpQuX733zyok/jsnqe/Ftw==",
+		"01234567890123456789012345678901234567890123456789012",
+	},
+}
+
+func TestDecryptPKCS1v15(t *testing.T) {
+	for i, test := range decryptPKCS1v15Tests {
+		out, err := DecryptPKCS1v15(nil, rsaPrivateKey, decodeBase64(test.in))
+		if err != nil {
+			t.Errorf("#%d error decrypting", i)
+		}
+		want := []byte(test.out)
+		if !bytes.Equal(out, want) {
+			t.Errorf("#%d got:%#v want:%#v", i, out, want)
+		}
+	}
+}
+
+func TestEncryptPKCS1v15(t *testing.T) {
+	random := rand.Reader
+	k := (rsaPrivateKey.N.BitLen() + 7) / 8
+
+	tryEncryptDecrypt := func(in []byte, blind bool) bool {
+		if len(in) > k-11 {
+			in = in[0 : k-11]
+		}
+
+		ciphertext, err := EncryptPKCS1v15(random, &rsaPrivateKey.PublicKey, in)
+		if err != nil {
+			t.Errorf("error encrypting: %s", err)
+			return false
+		}
+
+		var rand io.Reader
+		if !blind {
+			rand = nil
+		} else {
+			rand = random
+		}
+		plaintext, err := DecryptPKCS1v15(rand, rsaPrivateKey, ciphertext)
+		if err != nil {
+			t.Errorf("error decrypting: %s", err)
+			return false
+		}
+
+		if !bytes.Equal(plaintext, in) {
+			t.Errorf("output mismatch: %#v %#v", plaintext, in)
+			return false
+		}
+		return true
+	}
+
+	config := new(quick.Config)
+	if testing.Short() {
+		config.MaxCount = 10
+	}
+	quick.Check(tryEncryptDecrypt, config)
+}
+
+// These test vectors were generated with `openssl rsautl -pkcs -encrypt`
+var decryptPKCS1v15SessionKeyTests = []DecryptPKCS1v15Test{
+	{
+		"e6ukkae6Gykq0fKzYwULpZehX+UPXYzMoB5mHQUDEiclRbOTqas4Y0E6nwns1BBpdvEJcilhl5zsox/6DtGsYg==",
+		"1234",
+	},
+	{
+		"Dtis4uk/q/LQGGqGk97P59K03hkCIVFMEFZRgVWOAAhxgYpCRG0MX2adptt92l67IqMki6iVQyyt0TtX3IdtEw==",
+		"FAIL",
+	},
+	{
+		"LIyFyCYCptPxrvTxpol8F3M7ZivlMsf53zs0vHRAv+rDIh2YsHS69ePMoPMe3TkOMZ3NupiL3takPxIs1sK+dw==",
+		"abcd",
+	},
+	{
+		"bafnobel46bKy76JzqU/RIVOH0uAYvzUtauKmIidKgM0sMlvobYVAVQPeUQ/oTGjbIZ1v/6Gyi5AO4DtHruGdw==",
+		"FAIL",
+	},
+}
+
+func TestEncryptPKCS1v15SessionKey(t *testing.T) {
+	for i, test := range decryptPKCS1v15SessionKeyTests {
+		key := []byte("FAIL")
+		err := DecryptPKCS1v15SessionKey(nil, rsaPrivateKey, decodeBase64(test.in), key)
+		if err != nil {
+			t.Errorf("#%d error decrypting", i)
+		}
+		want := []byte(test.out)
+		if !bytes.Equal(key, want) {
+			t.Errorf("#%d got:%#v want:%#v", i, key, want)
+		}
+	}
+}
+
+func TestNonZeroRandomBytes(t *testing.T) {
+	random := rand.Reader
+
+	b := make([]byte, 512)
+	err := nonZeroRandomBytes(b, random)
+	if err != nil {
+		t.Errorf("returned error: %s", err)
+	}
+	for _, b := range b {
+		if b == 0 {
+			t.Errorf("Zero octet found")
+			return
+		}
+	}
+}
+
+type signPKCS1v15Test struct {
+	in, out string
+}
+
+// These vectors have been tested with
+//   `openssl rsautl -verify -inkey pk -in signature | hexdump -C`
+var signPKCS1v15Tests = []signPKCS1v15Test{
+	{"Test.\n", "a4f3fa6ea93bcdd0c57be020c1193ecbfd6f200a3d95c409769b029578fa0e336ad9a347600e40d3ae823b8c7e6bad88cc07c1d54c3a1523cbbb6d58efc362ae"},
+}
+
+func TestSignPKCS1v15(t *testing.T) {
+	for i, test := range signPKCS1v15Tests {
+		h := sha1.New()
+		h.Write([]byte(test.in))
+		digest := h.Sum(nil)
+
+		s, err := SignPKCS1v15(nil, rsaPrivateKey, crypto.SHA1, digest)
+		if err != nil {
+			t.Errorf("#%d %s", i, err)
+		}
+
+		expected, _ := hex.DecodeString(test.out)
+		if !bytes.Equal(s, expected) {
+			t.Errorf("#%d got: %x want: %x", i, s, expected)
+		}
+	}
+}
+
+func TestVerifyPKCS1v15(t *testing.T) {
+	for i, test := range signPKCS1v15Tests {
+		h := sha1.New()
+		h.Write([]byte(test.in))
+		digest := h.Sum(nil)
+
+		sig, _ := hex.DecodeString(test.out)
+
+		err := VerifyPKCS1v15(&rsaPrivateKey.PublicKey, crypto.SHA1, digest, sig)
+		if err != nil {
+			t.Errorf("#%d %s", i, err)
+		}
+	}
+}
+
+func TestOverlongMessagePKCS1v15(t *testing.T) {
+	ciphertext := decodeBase64("fjOVdirUzFoLlukv80dBllMLjXythIf22feqPrNo0YoIjzyzyoMFiLjAc/Y4krkeZ11XFThIrEvw\nkRiZcCq5ng==")
+	_, err := DecryptPKCS1v15(nil, rsaPrivateKey, ciphertext)
+	if err == nil {
+		t.Error("RSA decrypted a message that was too long.")
+	}
+}
+
+func TestUnpaddedSignature(t *testing.T) {
+	msg := []byte("Thu Dec 19 18:06:16 EST 2013\n")
+	// This base64 value was generated with:
+	// % echo Thu Dec 19 18:06:16 EST 2013 > /tmp/msg
+	// % openssl rsautl -sign -inkey key -out /tmp/sig -in /tmp/msg
+	//
+	// Where "key" contains the RSA private key given at the bottom of this
+	// file.
+	expectedSig := decodeBase64("pX4DR8azytjdQ1rtUiC040FjkepuQut5q2ZFX1pTjBrOVKNjgsCDyiJDGZTCNoh9qpXYbhl7iEym30BWWwuiZg==")
+
+	sig, err := SignPKCS1v15(nil, rsaPrivateKey, crypto.Hash(0), msg)
+	if err != nil {
+		t.Fatalf("SignPKCS1v15 failed: %s", err)
+	}
+	if !bytes.Equal(sig, expectedSig) {
+		t.Fatalf("signature is not expected value: got %x, want %x", sig, expectedSig)
+	}
+	if err := VerifyPKCS1v15(&rsaPrivateKey.PublicKey, crypto.Hash(0), msg, sig); err != nil {
+		t.Fatalf("signature failed to verify: %s", err)
+	}
+}
+
+func TestShortSessionKey(t *testing.T) {
+	// This tests that attempting to decrypt a session key where the
+	// ciphertext is too small doesn't run outside the array bounds.
+	ciphertext, err := EncryptPKCS1v15(rand.Reader, &rsaPrivateKey.PublicKey, []byte{1})
+	if err != nil {
+		t.Fatalf("Failed to encrypt short message: %s", err)
+	}
+
+	var key [32]byte
+	if err := DecryptPKCS1v15SessionKey(nil, rsaPrivateKey, ciphertext, key[:]); err != nil {
+		t.Fatalf("Failed to decrypt short message: %s", err)
+	}
+
+	for _, v := range key {
+		if v != 0 {
+			t.Fatal("key was modified when ciphertext was invalid")
+		}
+	}
+}
+
+// In order to generate new test vectors you'll need the PEM form of this key:
+// -----BEGIN RSA PRIVATE KEY-----
+// MIIBOgIBAAJBALKZD0nEffqM1ACuak0bijtqE2QrI/KLADv7l3kK3ppMyCuLKoF0
+// fd7Ai2KW5ToIwzFofvJcS/STa6HA5gQenRUCAwEAAQJBAIq9amn00aS0h/CrjXqu
+// /ThglAXJmZhOMPVn4eiu7/ROixi9sex436MaVeMqSNf7Ex9a8fRNfWss7Sqd9eWu
+// RTUCIQDasvGASLqmjeffBNLTXV2A5g4t+kLVCpsEIZAycV5GswIhANEPLmax0ME/
+// EO+ZJ79TJKN5yiGBRsv5yvx5UiHxajEXAiAhAol5N4EUyq6I9w1rYdhPMGpLfk7A
+// IU2snfRJ6Nq2CQIgFrPsWRCkV+gOYcajD17rEqmuLrdIRexpg8N1DOSXoJ8CIGlS
+// tAboUGBxTDq3ZroNism3DaMIbKPyYrAqhKov1h5V
+// -----END RSA PRIVATE KEY-----
+
+var rsaPrivateKey = &PrivateKey{
+	PublicKey: PublicKey{
+		N: fromBase10("9353930466774385905609975137998169297361893554149986716853295022578535724979677252958524466350471210367835187480748268864277464700638583474144061408845077"),
+		E: 65537,
+	},
+	D: fromBase10("7266398431328116344057699379749222532279343923819063639497049039389899328538543087657733766554155839834519529439851673014800261285757759040931985506583861"),
+	Primes: []*big.Int{
+		fromBase10("98920366548084643601728869055592650835572950932266967461790948584315647051443"),
+		fromBase10("94560208308847015747498523884063394671606671904944666360068158221458669711639"),
+	},
+}
diff --git a/src/crypto/rsa/pss.go b/src/crypto/rsa/pss.go
new file mode 100644
index 000000000..e9f290825
--- /dev/null
+++ b/src/crypto/rsa/pss.go
@@ -0,0 +1,297 @@
+// 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 rsa
+
+// This file implements the PSS signature scheme [1].
+//
+// [1] http://www.rsa.com/rsalabs/pkcs/files/h11300-wp-pkcs-1v2-2-rsa-cryptography-standard.pdf
+
+import (
+	"bytes"
+	"crypto"
+	"errors"
+	"hash"
+	"io"
+	"math/big"
+)
+
+func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byte, error) {
+	// See [1], section 9.1.1
+	hLen := hash.Size()
+	sLen := len(salt)
+	emLen := (emBits + 7) / 8
+
+	// 1.  If the length of M is greater than the input limitation for the
+	//     hash function (2^61 - 1 octets for SHA-1), output "message too
+	//     long" and stop.
+	//
+	// 2.  Let mHash = Hash(M), an octet string of length hLen.
+
+	if len(mHash) != hLen {
+		return nil, errors.New("crypto/rsa: input must be hashed message")
+	}
+
+	// 3.  If emLen < hLen + sLen + 2, output "encoding error" and stop.
+
+	if emLen < hLen+sLen+2 {
+		return nil, errors.New("crypto/rsa: encoding error")
+	}
+
+	em := make([]byte, emLen)
+	db := em[:emLen-sLen-hLen-2+1+sLen]
+	h := em[emLen-sLen-hLen-2+1+sLen : emLen-1]
+
+	// 4.  Generate a random octet string salt of length sLen; if sLen = 0,
+	//     then salt is the empty string.
+	//
+	// 5.  Let
+	//       M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt;
+	//
+	//     M' is an octet string of length 8 + hLen + sLen with eight
+	//     initial zero octets.
+	//
+	// 6.  Let H = Hash(M'), an octet string of length hLen.
+
+	var prefix [8]byte
+
+	hash.Write(prefix[:])
+	hash.Write(mHash)
+	hash.Write(salt)
+
+	h = hash.Sum(h[:0])
+	hash.Reset()
+
+	// 7.  Generate an octet string PS consisting of emLen - sLen - hLen - 2
+	//     zero octets.  The length of PS may be 0.
+	//
+	// 8.  Let DB = PS || 0x01 || salt; DB is an octet string of length
+	//     emLen - hLen - 1.
+
+	db[emLen-sLen-hLen-2] = 0x01
+	copy(db[emLen-sLen-hLen-1:], salt)
+
+	// 9.  Let dbMask = MGF(H, emLen - hLen - 1).
+	//
+	// 10. Let maskedDB = DB \xor dbMask.
+
+	mgf1XOR(db, hash, h)
+
+	// 11. Set the leftmost 8 * emLen - emBits bits of the leftmost octet in
+	//     maskedDB to zero.
+
+	db[0] &= (0xFF >> uint(8*emLen-emBits))
+
+	// 12. Let EM = maskedDB || H || 0xbc.
+	em[emLen-1] = 0xBC
+
+	// 13. Output EM.
+	return em, nil
+}
+
+func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
+	// 1.  If the length of M is greater than the input limitation for the
+	//     hash function (2^61 - 1 octets for SHA-1), output "inconsistent"
+	//     and stop.
+	//
+	// 2.  Let mHash = Hash(M), an octet string of length hLen.
+	hLen := hash.Size()
+	if hLen != len(mHash) {
+		return ErrVerification
+	}
+
+	// 3.  If emLen < hLen + sLen + 2, output "inconsistent" and stop.
+	emLen := (emBits + 7) / 8
+	if emLen < hLen+sLen+2 {
+		return ErrVerification
+	}
+
+	// 4.  If the rightmost octet of EM does not have hexadecimal value
+	//     0xbc, output "inconsistent" and stop.
+	if em[len(em)-1] != 0xBC {
+		return ErrVerification
+	}
+
+	// 5.  Let maskedDB be the leftmost emLen - hLen - 1 octets of EM, and
+	//     let H be the next hLen octets.
+	db := em[:emLen-hLen-1]
+	h := em[emLen-hLen-1 : len(em)-1]
+
+	// 6.  If the leftmost 8 * emLen - emBits bits of the leftmost octet in
+	//     maskedDB are not all equal to zero, output "inconsistent" and
+	//     stop.
+	if em[0]&(0xFF<<uint(8-(8*emLen-emBits))) != 0 {
+		return ErrVerification
+	}
+
+	// 7.  Let dbMask = MGF(H, emLen - hLen - 1).
+	//
+	// 8.  Let DB = maskedDB \xor dbMask.
+	mgf1XOR(db, hash, h)
+
+	// 9.  Set the leftmost 8 * emLen - emBits bits of the leftmost octet in DB
+	//     to zero.
+	db[0] &= (0xFF >> uint(8*emLen-emBits))
+
+	if sLen == PSSSaltLengthAuto {
+	FindSaltLength:
+		for sLen = emLen - (hLen + 2); sLen >= 0; sLen-- {
+			switch db[emLen-hLen-sLen-2] {
+			case 1:
+				break FindSaltLength
+			case 0:
+				continue
+			default:
+				return ErrVerification
+			}
+		}
+		if sLen < 0 {
+			return ErrVerification
+		}
+	} else {
+		// 10. If the emLen - hLen - sLen - 2 leftmost octets of DB are not zero
+		//     or if the octet at position emLen - hLen - sLen - 1 (the leftmost
+		//     position is "position 1") does not have hexadecimal value 0x01,
+		//     output "inconsistent" and stop.
+		for _, e := range db[:emLen-hLen-sLen-2] {
+			if e != 0x00 {
+				return ErrVerification
+			}
+		}
+		if db[emLen-hLen-sLen-2] != 0x01 {
+			return ErrVerification
+		}
+	}
+
+	// 11.  Let salt be the last sLen octets of DB.
+	salt := db[len(db)-sLen:]
+
+	// 12.  Let
+	//          M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt ;
+	//     M' is an octet string of length 8 + hLen + sLen with eight
+	//     initial zero octets.
+	//
+	// 13. Let H' = Hash(M'), an octet string of length hLen.
+	var prefix [8]byte
+	hash.Write(prefix[:])
+	hash.Write(mHash)
+	hash.Write(salt)
+
+	h0 := hash.Sum(nil)
+
+	// 14. If H = H', output "consistent." Otherwise, output "inconsistent."
+	if !bytes.Equal(h0, h) {
+		return ErrVerification
+	}
+	return nil
+}
+
+// signPSSWithSalt calculates the signature of hashed using PSS [1] with specified salt.
+// Note that hashed must be the result of hashing the input message using the
+// given hash function. salt is a random sequence of bytes whose length will be
+// later used to verify the signature.
+func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) (s []byte, err error) {
+	nBits := priv.N.BitLen()
+	em, err := emsaPSSEncode(hashed, nBits-1, salt, hash.New())
+	if err != nil {
+		return
+	}
+	m := new(big.Int).SetBytes(em)
+	c, err := decrypt(rand, priv, m)
+	if err != nil {
+		return
+	}
+	s = make([]byte, (nBits+7)/8)
+	copyWithLeftPad(s, c.Bytes())
+	return
+}
+
+const (
+	// PSSSaltLengthAuto causes the salt in a PSS signature to be as large
+	// as possible when signing, and to be auto-detected when verifying.
+	PSSSaltLengthAuto = 0
+	// PSSSaltLengthEqualsHash causes the salt length to equal the length
+	// of the hash used in the signature.
+	PSSSaltLengthEqualsHash = -1
+)
+
+// PSSOptions contains options for creating and verifying PSS signatures.
+type PSSOptions struct {
+	// SaltLength controls the length of the salt used in the PSS
+	// signature. It can either be a number of bytes, or one of the special
+	// PSSSaltLength constants.
+	SaltLength int
+
+	// Hash, if not zero, overrides the hash function passed to SignPSS.
+	// This is the only way to specify the hash function when using the
+	// crypto.Signer interface.
+	Hash crypto.Hash
+}
+
+// HashFunc returns pssOpts.Hash so that PSSOptions implements
+// crypto.SignerOpts.
+func (pssOpts *PSSOptions) HashFunc() crypto.Hash {
+	return pssOpts.Hash
+}
+
+func (opts *PSSOptions) saltLength() int {
+	if opts == nil {
+		return PSSSaltLengthAuto
+	}
+	return opts.SaltLength
+}
+
+// SignPSS calculates the signature of hashed using RSASSA-PSS [1].
+// Note that hashed must be the result of hashing the input message using the
+// given hash function. The opts argument may be nil, in which case sensible
+// defaults are used.
+func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte, opts *PSSOptions) (s []byte, err error) {
+	saltLength := opts.saltLength()
+	switch saltLength {
+	case PSSSaltLengthAuto:
+		saltLength = (priv.N.BitLen()+7)/8 - 2 - hash.Size()
+	case PSSSaltLengthEqualsHash:
+		saltLength = hash.Size()
+	}
+
+	if opts.Hash != 0 {
+		hash = opts.Hash
+	}
+
+	salt := make([]byte, saltLength)
+	if _, err = io.ReadFull(rand, salt); err != nil {
+		return
+	}
+	return signPSSWithSalt(rand, priv, hash, hashed, salt)
+}
+
+// VerifyPSS verifies a PSS signature.
+// hashed is the result of hashing the input message using the given hash
+// function and sig is the signature. A valid signature is indicated by
+// returning a nil error. The opts argument may be nil, in which case sensible
+// defaults are used.
+func VerifyPSS(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte, opts *PSSOptions) error {
+	return verifyPSS(pub, hash, hashed, sig, opts.saltLength())
+}
+
+// verifyPSS verifies a PSS signature with the given salt length.
+func verifyPSS(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte, saltLen int) error {
+	nBits := pub.N.BitLen()
+	if len(sig) != (nBits+7)/8 {
+		return ErrVerification
+	}
+	s := new(big.Int).SetBytes(sig)
+	m := encrypt(new(big.Int), pub, s)
+	emBits := nBits - 1
+	emLen := (emBits + 7) / 8
+	if emLen < len(m.Bytes()) {
+		return ErrVerification
+	}
+	em := make([]byte, emLen)
+	copyWithLeftPad(em, m.Bytes())
+	if saltLen == PSSSaltLengthEqualsHash {
+		saltLen = hash.Size()
+	}
+	return emsaPSSVerify(hashed, em, emBits, saltLen, hash.New())
+}
diff --git a/src/crypto/rsa/pss_test.go b/src/crypto/rsa/pss_test.go
new file mode 100644
index 000000000..32e6fc39d
--- /dev/null
+++ b/src/crypto/rsa/pss_test.go
@@ -0,0 +1,249 @@
+// 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 rsa
+
+import (
+	"bufio"
+	"bytes"
+	"compress/bzip2"
+	"crypto"
+	_ "crypto/md5"
+	"crypto/rand"
+	"crypto/sha1"
+	_ "crypto/sha256"
+	"encoding/hex"
+	"math/big"
+	"os"
+	"strconv"
+	"strings"
+	"testing"
+)
+
+func TestEMSAPSS(t *testing.T) {
+	// Test vector in file pss-int.txt from: ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1-vec.zip
+	msg := []byte{
+		0x85, 0x9e, 0xef, 0x2f, 0xd7, 0x8a, 0xca, 0x00, 0x30, 0x8b,
+		0xdc, 0x47, 0x11, 0x93, 0xbf, 0x55, 0xbf, 0x9d, 0x78, 0xdb,
+		0x8f, 0x8a, 0x67, 0x2b, 0x48, 0x46, 0x34, 0xf3, 0xc9, 0xc2,
+		0x6e, 0x64, 0x78, 0xae, 0x10, 0x26, 0x0f, 0xe0, 0xdd, 0x8c,
+		0x08, 0x2e, 0x53, 0xa5, 0x29, 0x3a, 0xf2, 0x17, 0x3c, 0xd5,
+		0x0c, 0x6d, 0x5d, 0x35, 0x4f, 0xeb, 0xf7, 0x8b, 0x26, 0x02,
+		0x1c, 0x25, 0xc0, 0x27, 0x12, 0xe7, 0x8c, 0xd4, 0x69, 0x4c,
+		0x9f, 0x46, 0x97, 0x77, 0xe4, 0x51, 0xe7, 0xf8, 0xe9, 0xe0,
+		0x4c, 0xd3, 0x73, 0x9c, 0x6b, 0xbf, 0xed, 0xae, 0x48, 0x7f,
+		0xb5, 0x56, 0x44, 0xe9, 0xca, 0x74, 0xff, 0x77, 0xa5, 0x3c,
+		0xb7, 0x29, 0x80, 0x2f, 0x6e, 0xd4, 0xa5, 0xff, 0xa8, 0xba,
+		0x15, 0x98, 0x90, 0xfc,
+	}
+	salt := []byte{
+		0xe3, 0xb5, 0xd5, 0xd0, 0x02, 0xc1, 0xbc, 0xe5, 0x0c, 0x2b,
+		0x65, 0xef, 0x88, 0xa1, 0x88, 0xd8, 0x3b, 0xce, 0x7e, 0x61,
+	}
+	expected := []byte{
+		0x66, 0xe4, 0x67, 0x2e, 0x83, 0x6a, 0xd1, 0x21, 0xba, 0x24,
+		0x4b, 0xed, 0x65, 0x76, 0xb8, 0x67, 0xd9, 0xa4, 0x47, 0xc2,
+		0x8a, 0x6e, 0x66, 0xa5, 0xb8, 0x7d, 0xee, 0x7f, 0xbc, 0x7e,
+		0x65, 0xaf, 0x50, 0x57, 0xf8, 0x6f, 0xae, 0x89, 0x84, 0xd9,
+		0xba, 0x7f, 0x96, 0x9a, 0xd6, 0xfe, 0x02, 0xa4, 0xd7, 0x5f,
+		0x74, 0x45, 0xfe, 0xfd, 0xd8, 0x5b, 0x6d, 0x3a, 0x47, 0x7c,
+		0x28, 0xd2, 0x4b, 0xa1, 0xe3, 0x75, 0x6f, 0x79, 0x2d, 0xd1,
+		0xdc, 0xe8, 0xca, 0x94, 0x44, 0x0e, 0xcb, 0x52, 0x79, 0xec,
+		0xd3, 0x18, 0x3a, 0x31, 0x1f, 0xc8, 0x96, 0xda, 0x1c, 0xb3,
+		0x93, 0x11, 0xaf, 0x37, 0xea, 0x4a, 0x75, 0xe2, 0x4b, 0xdb,
+		0xfd, 0x5c, 0x1d, 0xa0, 0xde, 0x7c, 0xec, 0xdf, 0x1a, 0x89,
+		0x6f, 0x9d, 0x8b, 0xc8, 0x16, 0xd9, 0x7c, 0xd7, 0xa2, 0xc4,
+		0x3b, 0xad, 0x54, 0x6f, 0xbe, 0x8c, 0xfe, 0xbc,
+	}
+
+	hash := sha1.New()
+	hash.Write(msg)
+	hashed := hash.Sum(nil)
+
+	encoded, err := emsaPSSEncode(hashed, 1023, salt, sha1.New())
+	if err != nil {
+		t.Errorf("Error from emsaPSSEncode: %s\n", err)
+	}
+	if !bytes.Equal(encoded, expected) {
+		t.Errorf("Bad encoding. got %x, want %x", encoded, expected)
+	}
+
+	if err = emsaPSSVerify(hashed, encoded, 1023, len(salt), sha1.New()); err != nil {
+		t.Errorf("Bad verification: %s", err)
+	}
+}
+
+// TestPSSGolden tests all the test vectors in pss-vect.txt from
+// ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1-vec.zip
+func TestPSSGolden(t *testing.T) {
+	inFile, err := os.Open("testdata/pss-vect.txt.bz2")
+	if err != nil {
+		t.Fatalf("Failed to open input file: %s", err)
+	}
+	defer inFile.Close()
+
+	// The pss-vect.txt file contains RSA keys and then a series of
+	// signatures. A goroutine is used to preprocess the input by merging
+	// lines, removing spaces in hex values and identifying the start of
+	// new keys and signature blocks.
+	const newKeyMarker = "START NEW KEY"
+	const newSignatureMarker = "START NEW SIGNATURE"
+
+	values := make(chan string)
+
+	go func() {
+		defer close(values)
+		scanner := bufio.NewScanner(bzip2.NewReader(inFile))
+		var partialValue string
+		lastWasValue := true
+
+		for scanner.Scan() {
+			line := scanner.Text()
+			switch {
+			case len(line) == 0:
+				if len(partialValue) > 0 {
+					values <- strings.Replace(partialValue, " ", "", -1)
+					partialValue = ""
+					lastWasValue = true
+				}
+				continue
+			case strings.HasPrefix(line, "# ======") && lastWasValue:
+				values <- newKeyMarker
+				lastWasValue = false
+			case strings.HasPrefix(line, "# ------") && lastWasValue:
+				values <- newSignatureMarker
+				lastWasValue = false
+			case strings.HasPrefix(line, "#"):
+				continue
+			default:
+				partialValue += line
+			}
+		}
+		if err := scanner.Err(); err != nil {
+			panic(err)
+		}
+	}()
+
+	var key *PublicKey
+	var hashed []byte
+	hash := crypto.SHA1
+	h := hash.New()
+	opts := &PSSOptions{
+		SaltLength: PSSSaltLengthEqualsHash,
+	}
+
+	for marker := range values {
+		switch marker {
+		case newKeyMarker:
+			key = new(PublicKey)
+			nHex, ok := <-values
+			if !ok {
+				continue
+			}
+			key.N = bigFromHex(nHex)
+			key.E = intFromHex(<-values)
+			// We don't care for d, p, q, dP, dQ or qInv.
+			for i := 0; i < 6; i++ {
+				<-values
+			}
+		case newSignatureMarker:
+			msg := fromHex(<-values)
+			<-values // skip salt
+			sig := fromHex(<-values)
+
+			h.Reset()
+			h.Write(msg)
+			hashed = h.Sum(hashed[:0])
+
+			if err := VerifyPSS(key, hash, hashed, sig, opts); err != nil {
+				t.Error(err)
+			}
+		default:
+			t.Fatalf("unknown marker: " + marker)
+		}
+	}
+}
+
+// TestPSSOpenSSL ensures that we can verify a PSS signature from OpenSSL with
+// the default options. OpenSSL sets the salt length to be maximal.
+func TestPSSOpenSSL(t *testing.T) {
+	hash := crypto.SHA256
+	h := hash.New()
+	h.Write([]byte("testing"))
+	hashed := h.Sum(nil)
+
+	// Generated with `echo -n testing | openssl dgst -sign key.pem -sigopt rsa_padding_mode:pss -sha256 > sig`
+	sig := []byte{
+		0x95, 0x59, 0x6f, 0xd3, 0x10, 0xa2, 0xe7, 0xa2, 0x92, 0x9d,
+		0x4a, 0x07, 0x2e, 0x2b, 0x27, 0xcc, 0x06, 0xc2, 0x87, 0x2c,
+		0x52, 0xf0, 0x4a, 0xcc, 0x05, 0x94, 0xf2, 0xc3, 0x2e, 0x20,
+		0xd7, 0x3e, 0x66, 0x62, 0xb5, 0x95, 0x2b, 0xa3, 0x93, 0x9a,
+		0x66, 0x64, 0x25, 0xe0, 0x74, 0x66, 0x8c, 0x3e, 0x92, 0xeb,
+		0xc6, 0xe6, 0xc0, 0x44, 0xf3, 0xb4, 0xb4, 0x2e, 0x8c, 0x66,
+		0x0a, 0x37, 0x9c, 0x69,
+	}
+
+	if err := VerifyPSS(&rsaPrivateKey.PublicKey, hash, hashed, sig, nil); err != nil {
+		t.Error(err)
+	}
+}
+
+func TestPSSSigning(t *testing.T) {
+	var saltLengthCombinations = []struct {
+		signSaltLength, verifySaltLength int
+		good                             bool
+	}{
+		{PSSSaltLengthAuto, PSSSaltLengthAuto, true},
+		{PSSSaltLengthEqualsHash, PSSSaltLengthAuto, true},
+		{PSSSaltLengthEqualsHash, PSSSaltLengthEqualsHash, true},
+		{PSSSaltLengthEqualsHash, 8, false},
+		{PSSSaltLengthAuto, PSSSaltLengthEqualsHash, false},
+		{8, 8, true},
+	}
+
+	hash := crypto.MD5
+	h := hash.New()
+	h.Write([]byte("testing"))
+	hashed := h.Sum(nil)
+	var opts PSSOptions
+
+	for i, test := range saltLengthCombinations {
+		opts.SaltLength = test.signSaltLength
+		sig, err := SignPSS(rand.Reader, rsaPrivateKey, hash, hashed, &opts)
+		if err != nil {
+			t.Errorf("#%d: error while signing: %s", i, err)
+			continue
+		}
+
+		opts.SaltLength = test.verifySaltLength
+		err = VerifyPSS(&rsaPrivateKey.PublicKey, hash, hashed, sig, &opts)
+		if (err == nil) != test.good {
+			t.Errorf("#%d: bad result, wanted: %t, got: %s", i, test.good, err)
+		}
+	}
+}
+
+func bigFromHex(hex string) *big.Int {
+	n, ok := new(big.Int).SetString(hex, 16)
+	if !ok {
+		panic("bad hex: " + hex)
+	}
+	return n
+}
+
+func intFromHex(hex string) int {
+	i, err := strconv.ParseInt(hex, 16, 32)
+	if err != nil {
+		panic(err)
+	}
+	return int(i)
+}
+
+func fromHex(hexStr string) []byte {
+	s, err := hex.DecodeString(hexStr)
+	if err != nil {
+		panic(err)
+	}
+	return s
+}
diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
new file mode 100644
index 000000000..270231128
--- /dev/null
+++ b/src/crypto/rsa/rsa.go
@@ -0,0 +1,557 @@
+// Copyright 2009 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 rsa implements RSA encryption as specified in PKCS#1.
+package rsa
+
+import (
+	"crypto"
+	"crypto/rand"
+	"crypto/subtle"
+	"errors"
+	"hash"
+	"io"
+	"math/big"
+)
+
+var bigZero = big.NewInt(0)
+var bigOne = big.NewInt(1)
+
+// A PublicKey represents the public part of an RSA key.
+type PublicKey struct {
+	N *big.Int // modulus
+	E int      // public exponent
+}
+
+var (
+	errPublicModulus       = errors.New("crypto/rsa: missing public modulus")
+	errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
+	errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
+)
+
+// checkPub sanity checks the public key before we use it.
+// We require pub.E to fit into a 32-bit integer so that we
+// do not have different behavior depending on whether
+// int is 32 or 64 bits. See also
+// http://www.imperialviolet.org/2012/03/16/rsae.html.
+func checkPub(pub *PublicKey) error {
+	if pub.N == nil {
+		return errPublicModulus
+	}
+	if pub.E < 2 {
+		return errPublicExponentSmall
+	}
+	if pub.E > 1<<31-1 {
+		return errPublicExponentLarge
+	}
+	return nil
+}
+
+// A PrivateKey represents an RSA key
+type PrivateKey struct {
+	PublicKey            // public part.
+	D         *big.Int   // private exponent
+	Primes    []*big.Int // prime factors of N, has >= 2 elements.
+
+	// Precomputed contains precomputed values that speed up private
+	// operations, if available.
+	Precomputed PrecomputedValues
+}
+
+// Public returns the public key corresponding to priv.
+func (priv *PrivateKey) Public() crypto.PublicKey {
+	return &priv.PublicKey
+}
+
+// Sign signs msg with priv, reading randomness from rand. If opts is a
+// *PSSOptions then the PSS algorithm will be used, otherwise PKCS#1 v1.5 will
+// be used. This method is intended to support keys where the private part is
+// kept in, for example, a hardware module. Common uses should use the Sign*
+// functions in this package.
+func (priv *PrivateKey) Sign(rand io.Reader, msg []byte, opts crypto.SignerOpts) ([]byte, error) {
+	if pssOpts, ok := opts.(*PSSOptions); ok {
+		return SignPSS(rand, priv, pssOpts.Hash, msg, pssOpts)
+	}
+
+	return SignPKCS1v15(rand, priv, opts.HashFunc(), msg)
+}
+
+type PrecomputedValues struct {
+	Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
+	Qinv   *big.Int // Q^-1 mod P
+
+	// CRTValues is used for the 3rd and subsequent primes. Due to a
+	// historical accident, the CRT for the first two primes is handled
+	// differently in PKCS#1 and interoperability is sufficiently
+	// important that we mirror this.
+	CRTValues []CRTValue
+}
+
+// CRTValue contains the precomputed chinese remainder theorem values.
+type CRTValue struct {
+	Exp   *big.Int // D mod (prime-1).
+	Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
+	R     *big.Int // product of primes prior to this (inc p and q).
+}
+
+// Validate performs basic sanity checks on the key.
+// It returns nil if the key is valid, or else an error describing a problem.
+func (priv *PrivateKey) Validate() error {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return err
+	}
+
+	// Check that the prime factors are actually prime. Note that this is
+	// just a sanity check. Since the random witnesses chosen by
+	// ProbablyPrime are deterministic, given the candidate number, it's
+	// easy for an attack to generate composites that pass this test.
+	for _, prime := range priv.Primes {
+		if !prime.ProbablyPrime(20) {
+			return errors.New("crypto/rsa: prime factor is composite")
+		}
+	}
+
+	// Check that Πprimes == n.
+	modulus := new(big.Int).Set(bigOne)
+	for _, prime := range priv.Primes {
+		modulus.Mul(modulus, prime)
+	}
+	if modulus.Cmp(priv.N) != 0 {
+		return errors.New("crypto/rsa: invalid modulus")
+	}
+
+	// Check that de ≡ 1 mod p-1, for each prime.
+	// This implies that e is coprime to each p-1 as e has a multiplicative
+	// inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
+	// exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
+	// mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.
+	congruence := new(big.Int)
+	de := new(big.Int).SetInt64(int64(priv.E))
+	de.Mul(de, priv.D)
+	for _, prime := range priv.Primes {
+		pminus1 := new(big.Int).Sub(prime, bigOne)
+		congruence.Mod(de, pminus1)
+		if congruence.Cmp(bigOne) != 0 {
+			return errors.New("crypto/rsa: invalid exponents")
+		}
+	}
+	return nil
+}
+
+// GenerateKey generates an RSA keypair of the given bit size using the
+// random source random (for example, crypto/rand.Reader).
+func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err error) {
+	return GenerateMultiPrimeKey(random, 2, bits)
+}
+
+// GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
+// size and the given random source, as suggested in [1]. Although the public
+// keys are compatible (actually, indistinguishable) from the 2-prime case,
+// the private keys are not. Thus it may not be possible to export multi-prime
+// private keys in certain formats or to subsequently import them into other
+// code.
+//
+// Table 1 in [2] suggests maximum numbers of primes for a given size.
+//
+// [1] US patent 4405829 (1972, expired)
+// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
+func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err error) {
+	priv = new(PrivateKey)
+	priv.E = 65537
+
+	if nprimes < 2 {
+		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
+	}
+
+	primes := make([]*big.Int, nprimes)
+
+NextSetOfPrimes:
+	for {
+		todo := bits
+		// crypto/rand should set the top two bits in each prime.
+		// Thus each prime has the form
+		//   p_i = 2^bitlen(p_i) × 0.11... (in base 2).
+		// And the product is:
+		//   P = 2^todo × α
+		// where α is the product of nprimes numbers of the form 0.11...
+		//
+		// If α < 1/2 (which can happen for nprimes > 2), we need to
+		// shift todo to compensate for lost bits: the mean value of 0.11...
+		// is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
+		// will give good results.
+		if nprimes >= 7 {
+			todo += (nprimes - 2) / 5
+		}
+		for i := 0; i < nprimes; i++ {
+			primes[i], err = rand.Prime(random, todo/(nprimes-i))
+			if err != nil {
+				return nil, err
+			}
+			todo -= primes[i].BitLen()
+		}
+
+		// Make sure that primes is pairwise unequal.
+		for i, prime := range primes {
+			for j := 0; j < i; j++ {
+				if prime.Cmp(primes[j]) == 0 {
+					continue NextSetOfPrimes
+				}
+			}
+		}
+
+		n := new(big.Int).Set(bigOne)
+		totient := new(big.Int).Set(bigOne)
+		pminus1 := new(big.Int)
+		for _, prime := range primes {
+			n.Mul(n, prime)
+			pminus1.Sub(prime, bigOne)
+			totient.Mul(totient, pminus1)
+		}
+		if n.BitLen() != bits {
+			// This should never happen for nprimes == 2 because
+			// crypto/rand should set the top two bits in each prime.
+			// For nprimes > 2 we hope it does not happen often.
+			continue NextSetOfPrimes
+		}
+
+		g := new(big.Int)
+		priv.D = new(big.Int)
+		y := new(big.Int)
+		e := big.NewInt(int64(priv.E))
+		g.GCD(priv.D, y, e, totient)
+
+		if g.Cmp(bigOne) == 0 {
+			if priv.D.Sign() < 0 {
+				priv.D.Add(priv.D, totient)
+			}
+			priv.Primes = primes
+			priv.N = n
+
+			break
+		}
+	}
+
+	priv.Precompute()
+	return
+}
+
+// incCounter increments a four byte, big-endian counter.
+func incCounter(c *[4]byte) {
+	if c[3]++; c[3] != 0 {
+		return
+	}
+	if c[2]++; c[2] != 0 {
+		return
+	}
+	if c[1]++; c[1] != 0 {
+		return
+	}
+	c[0]++
+}
+
+// mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
+// specified in PKCS#1 v2.1.
+func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
+	var counter [4]byte
+	var digest []byte
+
+	done := 0
+	for done < len(out) {
+		hash.Write(seed)
+		hash.Write(counter[0:4])
+		digest = hash.Sum(digest[:0])
+		hash.Reset()
+
+		for i := 0; i < len(digest) && done < len(out); i++ {
+			out[done] ^= digest[i]
+			done++
+		}
+		incCounter(&counter)
+	}
+}
+
+// ErrMessageTooLong is returned when attempting to encrypt a message which is
+// too large for the size of the public key.
+var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")
+
+func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
+	e := big.NewInt(int64(pub.E))
+	c.Exp(m, e, pub.N)
+	return c
+}
+
+// EncryptOAEP encrypts the given message with RSA-OAEP.
+// The message must be no longer than the length of the public modulus less
+// twice the hash length plus 2.
+func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err error) {
+	if err := checkPub(pub); err != nil {
+		return nil, err
+	}
+	hash.Reset()
+	k := (pub.N.BitLen() + 7) / 8
+	if len(msg) > k-2*hash.Size()-2 {
+		err = ErrMessageTooLong
+		return
+	}
+
+	hash.Write(label)
+	lHash := hash.Sum(nil)
+	hash.Reset()
+
+	em := make([]byte, k)
+	seed := em[1 : 1+hash.Size()]
+	db := em[1+hash.Size():]
+
+	copy(db[0:hash.Size()], lHash)
+	db[len(db)-len(msg)-1] = 1
+	copy(db[len(db)-len(msg):], msg)
+
+	_, err = io.ReadFull(random, seed)
+	if err != nil {
+		return
+	}
+
+	mgf1XOR(db, hash, seed)
+	mgf1XOR(seed, hash, db)
+
+	m := new(big.Int)
+	m.SetBytes(em)
+	c := encrypt(new(big.Int), pub, m)
+	out = c.Bytes()
+
+	if len(out) < k {
+		// If the output is too small, we need to left-pad with zeros.
+		t := make([]byte, k)
+		copy(t[k-len(out):], out)
+		out = t
+	}
+
+	return
+}
+
+// ErrDecryption represents a failure to decrypt a message.
+// It is deliberately vague to avoid adaptive attacks.
+var ErrDecryption = errors.New("crypto/rsa: decryption error")
+
+// ErrVerification represents a failure to verify a signature.
+// It is deliberately vague to avoid adaptive attacks.
+var ErrVerification = errors.New("crypto/rsa: verification error")
+
+// modInverse returns ia, the inverse of a in the multiplicative group of prime
+// order n. It requires that a be a member of the group (i.e. less than n).
+func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
+	g := new(big.Int)
+	x := new(big.Int)
+	y := new(big.Int)
+	g.GCD(x, y, a, n)
+	if g.Cmp(bigOne) != 0 {
+		// In this case, a and n aren't coprime and we cannot calculate
+		// the inverse. This happens because the values of n are nearly
+		// prime (being the product of two primes) rather than truly
+		// prime.
+		return
+	}
+
+	if x.Cmp(bigOne) < 0 {
+		// 0 is not the multiplicative inverse of any element so, if x
+		// < 1, then x is negative.
+		x.Add(x, n)
+	}
+
+	return x, true
+}
+
+// Precompute performs some calculations that speed up private key operations
+// in the future.
+func (priv *PrivateKey) Precompute() {
+	if priv.Precomputed.Dp != nil {
+		return
+	}
+
+	priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
+	priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
+
+	priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
+	priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
+
+	priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
+
+	r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
+	priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
+	for i := 2; i < len(priv.Primes); i++ {
+		prime := priv.Primes[i]
+		values := &priv.Precomputed.CRTValues[i-2]
+
+		values.Exp = new(big.Int).Sub(prime, bigOne)
+		values.Exp.Mod(priv.D, values.Exp)
+
+		values.R = new(big.Int).Set(r)
+		values.Coeff = new(big.Int).ModInverse(r, prime)
+
+		r.Mul(r, prime)
+	}
+}
+
+// decrypt performs an RSA decryption, resulting in a plaintext integer. If a
+// random source is given, RSA blinding is used.
+func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
+	// TODO(agl): can we get away with reusing blinds?
+	if c.Cmp(priv.N) > 0 {
+		err = ErrDecryption
+		return
+	}
+
+	var ir *big.Int
+	if random != nil {
+		// Blinding enabled. Blinding involves multiplying c by r^e.
+		// Then the decryption operation performs (m^e * r^e)^d mod n
+		// which equals mr mod n. The factor of r can then be removed
+		// by multiplying by the multiplicative inverse of r.
+
+		var r *big.Int
+
+		for {
+			r, err = rand.Int(random, priv.N)
+			if err != nil {
+				return
+			}
+			if r.Cmp(bigZero) == 0 {
+				r = bigOne
+			}
+			var ok bool
+			ir, ok = modInverse(r, priv.N)
+			if ok {
+				break
+			}
+		}
+		bigE := big.NewInt(int64(priv.E))
+		rpowe := new(big.Int).Exp(r, bigE, priv.N)
+		cCopy := new(big.Int).Set(c)
+		cCopy.Mul(cCopy, rpowe)
+		cCopy.Mod(cCopy, priv.N)
+		c = cCopy
+	}
+
+	if priv.Precomputed.Dp == nil {
+		m = new(big.Int).Exp(c, priv.D, priv.N)
+	} else {
+		// We have the precalculated values needed for the CRT.
+		m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
+		m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
+		m.Sub(m, m2)
+		if m.Sign() < 0 {
+			m.Add(m, priv.Primes[0])
+		}
+		m.Mul(m, priv.Precomputed.Qinv)
+		m.Mod(m, priv.Primes[0])
+		m.Mul(m, priv.Primes[1])
+		m.Add(m, m2)
+
+		for i, values := range priv.Precomputed.CRTValues {
+			prime := priv.Primes[2+i]
+			m2.Exp(c, values.Exp, prime)
+			m2.Sub(m2, m)
+			m2.Mul(m2, values.Coeff)
+			m2.Mod(m2, prime)
+			if m2.Sign() < 0 {
+				m2.Add(m2, prime)
+			}
+			m2.Mul(m2, values.R)
+			m.Add(m, m2)
+		}
+	}
+
+	if ir != nil {
+		// Unblind.
+		m.Mul(m, ir)
+		m.Mod(m, priv.N)
+	}
+
+	return
+}
+
+// DecryptOAEP decrypts ciphertext using RSA-OAEP.
+// If random != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks.
+func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err error) {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return nil, err
+	}
+	k := (priv.N.BitLen() + 7) / 8
+	if len(ciphertext) > k ||
+		k < hash.Size()*2+2 {
+		err = ErrDecryption
+		return
+	}
+
+	c := new(big.Int).SetBytes(ciphertext)
+
+	m, err := decrypt(random, priv, c)
+	if err != nil {
+		return
+	}
+
+	hash.Write(label)
+	lHash := hash.Sum(nil)
+	hash.Reset()
+
+	// Converting the plaintext number to bytes will strip any
+	// leading zeros so we may have to left pad. We do this unconditionally
+	// to avoid leaking timing information. (Although we still probably
+	// leak the number of leading zeros. It's not clear that we can do
+	// anything about this.)
+	em := leftPad(m.Bytes(), k)
+
+	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
+
+	seed := em[1 : hash.Size()+1]
+	db := em[hash.Size()+1:]
+
+	mgf1XOR(seed, hash, db)
+	mgf1XOR(db, hash, seed)
+
+	lHash2 := db[0:hash.Size()]
+
+	// We have to validate the plaintext in constant time in order to avoid
+	// attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
+	// Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
+	// v2.0. In J. Kilian, editor, Advances in Cryptology.
+	lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
+
+	// The remainder of the plaintext must be zero or more 0x00, followed
+	// by 0x01, followed by the message.
+	//   lookingForIndex: 1 iff we are still looking for the 0x01
+	//   index: the offset of the first 0x01 byte
+	//   invalid: 1 iff we saw a non-zero byte before the 0x01.
+	var lookingForIndex, index, invalid int
+	lookingForIndex = 1
+	rest := db[hash.Size():]
+
+	for i := 0; i < len(rest); i++ {
+		equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
+		equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
+		index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
+		lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
+		invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
+	}
+
+	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
+		err = ErrDecryption
+		return
+	}
+
+	msg = rest[index+1:]
+	return
+}
+
+// leftPad returns a new slice of length size. The contents of input are right
+// aligned in the new slice.
+func leftPad(input []byte, size int) (out []byte) {
+	n := len(input)
+	if n > size {
+		n = size
+	}
+	out = make([]byte, size)
+	copy(out[len(out)-n:], input)
+	return
+}
diff --git a/src/crypto/rsa/rsa_test.go b/src/crypto/rsa/rsa_test.go
new file mode 100644
index 000000000..4ee1c3a8b
--- /dev/null
+++ b/src/crypto/rsa/rsa_test.go
@@ -0,0 +1,392 @@
+// Copyright 2009 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 rsa
+
+import (
+	"bytes"
+	"crypto/rand"
+	"crypto/sha1"
+	"math/big"
+	"testing"
+)
+
+func TestKeyGeneration(t *testing.T) {
+	size := 1024
+	if testing.Short() {
+		size = 128
+	}
+	priv, err := GenerateKey(rand.Reader, size)
+	if err != nil {
+		t.Errorf("failed to generate key")
+	}
+	if bits := priv.N.BitLen(); bits != size {
+		t.Errorf("key too short (%d vs %d)", bits, size)
+	}
+	testKeyBasics(t, priv)
+}
+
+func Test3PrimeKeyGeneration(t *testing.T) {
+	size := 768
+	if testing.Short() {
+		size = 256
+	}
+
+	priv, err := GenerateMultiPrimeKey(rand.Reader, 3, size)
+	if err != nil {
+		t.Errorf("failed to generate key")
+	}
+	testKeyBasics(t, priv)
+}
+
+func Test4PrimeKeyGeneration(t *testing.T) {
+	size := 768
+	if testing.Short() {
+		size = 256
+	}
+
+	priv, err := GenerateMultiPrimeKey(rand.Reader, 4, size)
+	if err != nil {
+		t.Errorf("failed to generate key")
+	}
+	testKeyBasics(t, priv)
+}
+
+func TestNPrimeKeyGeneration(t *testing.T) {
+	primeSize := 64
+	maxN := 24
+	if testing.Short() {
+		primeSize = 16
+		maxN = 16
+	}
+	// Test that generation of N-prime keys works for N > 4.
+	for n := 5; n < maxN; n++ {
+		priv, err := GenerateMultiPrimeKey(rand.Reader, n, 64+n*primeSize)
+		if err == nil {
+			testKeyBasics(t, priv)
+		} else {
+			t.Errorf("failed to generate %d-prime key", n)
+		}
+	}
+}
+
+func TestGnuTLSKey(t *testing.T) {
+	// This is a key generated by `certtool --generate-privkey --bits 128`.
+	// It's such that de ≢ 1 mod φ(n), but is congruent mod the order of
+	// the group.
+	priv := &PrivateKey{
+		PublicKey: PublicKey{
+			N: fromBase10("290684273230919398108010081414538931343"),
+			E: 65537,
+		},
+		D: fromBase10("31877380284581499213530787347443987241"),
+		Primes: []*big.Int{
+			fromBase10("16775196964030542637"),
+			fromBase10("17328218193455850539"),
+		},
+	}
+	testKeyBasics(t, priv)
+}
+
+func testKeyBasics(t *testing.T, priv *PrivateKey) {
+	if err := priv.Validate(); err != nil {
+		t.Errorf("Validate() failed: %s", err)
+	}
+	if priv.D.Cmp(priv.N) > 0 {
+		t.Errorf("private exponent too large")
+	}
+
+	pub := &priv.PublicKey
+	m := big.NewInt(42)
+	c := encrypt(new(big.Int), pub, m)
+
+	m2, err := decrypt(nil, priv, c)
+	if err != nil {
+		t.Errorf("error while decrypting: %s", err)
+		return
+	}
+	if m.Cmp(m2) != 0 {
+		t.Errorf("got:%v, want:%v (%+v)", m2, m, priv)
+	}
+
+	m3, err := decrypt(rand.Reader, priv, c)
+	if err != nil {
+		t.Errorf("error while decrypting (blind): %s", err)
+	}
+	if m.Cmp(m3) != 0 {
+		t.Errorf("(blind) got:%v, want:%v (%#v)", m3, m, priv)
+	}
+}
+
+func fromBase10(base10 string) *big.Int {
+	i, ok := new(big.Int).SetString(base10, 10)
+	if !ok {
+		panic("bad number: " + base10)
+	}
+	return i
+}
+
+func BenchmarkRSA2048Decrypt(b *testing.B) {
+	b.StopTimer()
+	priv := &PrivateKey{
+		PublicKey: PublicKey{
+			N: fromBase10("14314132931241006650998084889274020608918049032671858325988396851334124245188214251956198731333464217832226406088020736932173064754214329009979944037640912127943488972644697423190955557435910767690712778463524983667852819010259499695177313115447116110358524558307947613422897787329221478860907963827160223559690523660574329011927531289655711860504630573766609239332569210831325633840174683944553667352219670930408593321661375473885147973879086994006440025257225431977751512374815915392249179976902953721486040787792801849818254465486633791826766873076617116727073077821584676715609985777563958286637185868165868520557"),
+			E: 3,
+		},
+		D: fromBase10("9542755287494004433998723259516013739278699355114572217325597900889416163458809501304132487555642811888150937392013824621448709836142886006653296025093941418628992648429798282127303704957273845127141852309016655778568546006839666463451542076964744073572349705538631742281931858219480985907271975884773482372966847639853897890615456605598071088189838676728836833012254065983259638538107719766738032720239892094196108713378822882383694456030043492571063441943847195939549773271694647657549658603365629458610273821292232646334717612674519997533901052790334279661754176490593041941863932308687197618671528035670452762731"),
+		Primes: []*big.Int{
+			fromBase10("130903255182996722426771613606077755295583329135067340152947172868415809027537376306193179624298874215608270802054347609836776473930072411958753044562214537013874103802006369634761074377213995983876788718033850153719421695468704276694983032644416930879093914927146648402139231293035971427838068945045019075433"),
+			fromBase10("109348945610485453577574767652527472924289229538286649661240938988020367005475727988253438647560958573506159449538793540472829815903949343191091817779240101054552748665267574271163617694640513549693841337820602726596756351006149518830932261246698766355347898158548465400674856021497190430791824869615170301029"),
+		},
+	}
+	priv.Precompute()
+
+	c := fromBase10("8472002792838218989464636159316973636630013835787202418124758118372358261975764365740026024610403138425986214991379012696600761514742817632790916315594342398720903716529235119816755589383377471752116975374952783629225022962092351886861518911824745188989071172097120352727368980275252089141512321893536744324822590480751098257559766328893767334861211872318961900897793874075248286439689249972315699410830094164386544311554704755110361048571142336148077772023880664786019636334369759624917224888206329520528064315309519262325023881707530002540634660750469137117568199824615333883758410040459705787022909848740188613313")
+
+	b.StartTimer()
+
+	for i := 0; i < b.N; i++ {
+		decrypt(nil, priv, c)
+	}
+}
+
+func Benchmark3PrimeRSA2048Decrypt(b *testing.B) {
+	b.StopTimer()
+	priv := &PrivateKey{
+		PublicKey: PublicKey{
+			N: fromBase10("16346378922382193400538269749936049106320265317511766357599732575277382844051791096569333808598921852351577762718529818072849191122419410612033592401403764925096136759934497687765453905884149505175426053037420486697072448609022753683683718057795566811401938833367954642951433473337066311978821180526439641496973296037000052546108507805269279414789035461158073156772151892452251106173507240488993608650881929629163465099476849643165682709047462010581308719577053905787496296934240246311806555924593059995202856826239801816771116902778517096212527979497399966526283516447337775509777558018145573127308919204297111496233"),
+			E: 3,
+		},
+		D: fromBase10("10897585948254795600358846499957366070880176878341177571733155050184921896034527397712889205732614568234385175145686545381899460748279607074689061600935843283397424506622998458510302603922766336783617368686090042765718290914099334449154829375179958369993407724946186243249568928237086215759259909861748642124071874879861299389874230489928271621259294894142840428407196932444474088857746123104978617098858619445675532587787023228852383149557470077802718705420275739737958953794088728369933811184572620857678792001136676902250566845618813972833750098806496641114644760255910789397593428910198080271317419213080834885003"),
+		Primes: []*big.Int{
+			fromBase10("1025363189502892836833747188838978207017355117492483312747347695538428729137306368764177201532277413433182799108299960196606011786562992097313508180436744488171474690412562218914213688661311117337381958560443"),
+			fromBase10("3467903426626310123395340254094941045497208049900750380025518552334536945536837294961497712862519984786362199788654739924501424784631315081391467293694361474867825728031147665777546570788493758372218019373"),
+			fromBase10("4597024781409332673052708605078359346966325141767460991205742124888960305710298765592730135879076084498363772408626791576005136245060321874472727132746643162385746062759369754202494417496879741537284589047"),
+		},
+	}
+	priv.Precompute()
+
+	c := fromBase10("8472002792838218989464636159316973636630013835787202418124758118372358261975764365740026024610403138425986214991379012696600761514742817632790916315594342398720903716529235119816755589383377471752116975374952783629225022962092351886861518911824745188989071172097120352727368980275252089141512321893536744324822590480751098257559766328893767334861211872318961900897793874075248286439689249972315699410830094164386544311554704755110361048571142336148077772023880664786019636334369759624917224888206329520528064315309519262325023881707530002540634660750469137117568199824615333883758410040459705787022909848740188613313")
+
+	b.StartTimer()
+
+	for i := 0; i < b.N; i++ {
+		decrypt(nil, priv, c)
+	}
+}
+
+type testEncryptOAEPMessage struct {
+	in   []byte
+	seed []byte
+	out  []byte
+}
+
+type testEncryptOAEPStruct struct {
+	modulus string
+	e       int
+	d       string
+	msgs    []testEncryptOAEPMessage
+}
+
+func TestEncryptOAEP(t *testing.T) {
+	sha1 := sha1.New()
+	n := new(big.Int)
+	for i, test := range testEncryptOAEPData {
+		n.SetString(test.modulus, 16)
+		public := PublicKey{n, test.e}
+
+		for j, message := range test.msgs {
+			randomSource := bytes.NewReader(message.seed)
+			out, err := EncryptOAEP(sha1, randomSource, &public, message.in, nil)
+			if err != nil {
+				t.Errorf("#%d,%d error: %s", i, j, err)
+			}
+			if !bytes.Equal(out, message.out) {
+				t.Errorf("#%d,%d bad result: %x (want %x)", i, j, out, message.out)
+			}
+		}
+	}
+}
+
+func TestDecryptOAEP(t *testing.T) {
+	random := rand.Reader
+
+	sha1 := sha1.New()
+	n := new(big.Int)
+	d := new(big.Int)
+	for i, test := range testEncryptOAEPData {
+		n.SetString(test.modulus, 16)
+		d.SetString(test.d, 16)
+		private := new(PrivateKey)
+		private.PublicKey = PublicKey{n, test.e}
+		private.D = d
+
+		for j, message := range test.msgs {
+			out, err := DecryptOAEP(sha1, nil, private, message.out, nil)
+			if err != nil {
+				t.Errorf("#%d,%d error: %s", i, j, err)
+			} else if !bytes.Equal(out, message.in) {
+				t.Errorf("#%d,%d bad result: %#v (want %#v)", i, j, out, message.in)
+			}
+
+			// Decrypt with blinding.
+			out, err = DecryptOAEP(sha1, random, private, message.out, nil)
+			if err != nil {
+				t.Errorf("#%d,%d (blind) error: %s", i, j, err)
+			} else if !bytes.Equal(out, message.in) {
+				t.Errorf("#%d,%d (blind) bad result: %#v (want %#v)", i, j, out, message.in)
+			}
+		}
+		if testing.Short() {
+			break
+		}
+	}
+}
+
+// testEncryptOAEPData contains a subset of the vectors from RSA's "Test vectors for RSA-OAEP".
+var testEncryptOAEPData = []testEncryptOAEPStruct{
+	// Key 1
+	{"a8b3b284af8eb50b387034a860f146c4919f318763cd6c5598c8ae4811a1e0abc4c7e0b082d693a5e7fced675cf4668512772c0cbc64a742c6c630f533c8cc72f62ae833c40bf25842e984bb78bdbf97c0107d55bdb662f5c4e0fab9845cb5148ef7392dd3aaff93ae1e6b667bb3d4247616d4f5ba10d4cfd226de88d39f16fb",
+		65537,
+		"53339cfdb79fc8466a655c7316aca85c55fd8f6dd898fdaf119517ef4f52e8fd8e258df93fee180fa0e4ab29693cd83b152a553d4ac4d1812b8b9fa5af0e7f55fe7304df41570926f3311f15c4d65a732c483116ee3d3d2d0af3549ad9bf7cbfb78ad884f84d5beb04724dc7369b31def37d0cf539e9cfcdd3de653729ead5d1",
+		[]testEncryptOAEPMessage{
+			// Example 1.1
+			{
+				[]byte{0x66, 0x28, 0x19, 0x4e, 0x12, 0x07, 0x3d, 0xb0,
+					0x3b, 0xa9, 0x4c, 0xda, 0x9e, 0xf9, 0x53, 0x23, 0x97,
+					0xd5, 0x0d, 0xba, 0x79, 0xb9, 0x87, 0x00, 0x4a, 0xfe,
+					0xfe, 0x34,
+				},
+				[]byte{0x18, 0xb7, 0x76, 0xea, 0x21, 0x06, 0x9d, 0x69,
+					0x77, 0x6a, 0x33, 0xe9, 0x6b, 0xad, 0x48, 0xe1, 0xdd,
+					0xa0, 0xa5, 0xef,
+				},
+				[]byte{0x35, 0x4f, 0xe6, 0x7b, 0x4a, 0x12, 0x6d, 0x5d,
+					0x35, 0xfe, 0x36, 0xc7, 0x77, 0x79, 0x1a, 0x3f, 0x7b,
+					0xa1, 0x3d, 0xef, 0x48, 0x4e, 0x2d, 0x39, 0x08, 0xaf,
+					0xf7, 0x22, 0xfa, 0xd4, 0x68, 0xfb, 0x21, 0x69, 0x6d,
+					0xe9, 0x5d, 0x0b, 0xe9, 0x11, 0xc2, 0xd3, 0x17, 0x4f,
+					0x8a, 0xfc, 0xc2, 0x01, 0x03, 0x5f, 0x7b, 0x6d, 0x8e,
+					0x69, 0x40, 0x2d, 0xe5, 0x45, 0x16, 0x18, 0xc2, 0x1a,
+					0x53, 0x5f, 0xa9, 0xd7, 0xbf, 0xc5, 0xb8, 0xdd, 0x9f,
+					0xc2, 0x43, 0xf8, 0xcf, 0x92, 0x7d, 0xb3, 0x13, 0x22,
+					0xd6, 0xe8, 0x81, 0xea, 0xa9, 0x1a, 0x99, 0x61, 0x70,
+					0xe6, 0x57, 0xa0, 0x5a, 0x26, 0x64, 0x26, 0xd9, 0x8c,
+					0x88, 0x00, 0x3f, 0x84, 0x77, 0xc1, 0x22, 0x70, 0x94,
+					0xa0, 0xd9, 0xfa, 0x1e, 0x8c, 0x40, 0x24, 0x30, 0x9c,
+					0xe1, 0xec, 0xcc, 0xb5, 0x21, 0x00, 0x35, 0xd4, 0x7a,
+					0xc7, 0x2e, 0x8a,
+				},
+			},
+			// Example 1.2
+			{
+				[]byte{0x75, 0x0c, 0x40, 0x47, 0xf5, 0x47, 0xe8, 0xe4,
+					0x14, 0x11, 0x85, 0x65, 0x23, 0x29, 0x8a, 0xc9, 0xba,
+					0xe2, 0x45, 0xef, 0xaf, 0x13, 0x97, 0xfb, 0xe5, 0x6f,
+					0x9d, 0xd5,
+				},
+				[]byte{0x0c, 0xc7, 0x42, 0xce, 0x4a, 0x9b, 0x7f, 0x32,
+					0xf9, 0x51, 0xbc, 0xb2, 0x51, 0xef, 0xd9, 0x25, 0xfe,
+					0x4f, 0xe3, 0x5f,
+				},
+				[]byte{0x64, 0x0d, 0xb1, 0xac, 0xc5, 0x8e, 0x05, 0x68,
+					0xfe, 0x54, 0x07, 0xe5, 0xf9, 0xb7, 0x01, 0xdf, 0xf8,
+					0xc3, 0xc9, 0x1e, 0x71, 0x6c, 0x53, 0x6f, 0xc7, 0xfc,
+					0xec, 0x6c, 0xb5, 0xb7, 0x1c, 0x11, 0x65, 0x98, 0x8d,
+					0x4a, 0x27, 0x9e, 0x15, 0x77, 0xd7, 0x30, 0xfc, 0x7a,
+					0x29, 0x93, 0x2e, 0x3f, 0x00, 0xc8, 0x15, 0x15, 0x23,
+					0x6d, 0x8d, 0x8e, 0x31, 0x01, 0x7a, 0x7a, 0x09, 0xdf,
+					0x43, 0x52, 0xd9, 0x04, 0xcd, 0xeb, 0x79, 0xaa, 0x58,
+					0x3a, 0xdc, 0xc3, 0x1e, 0xa6, 0x98, 0xa4, 0xc0, 0x52,
+					0x83, 0xda, 0xba, 0x90, 0x89, 0xbe, 0x54, 0x91, 0xf6,
+					0x7c, 0x1a, 0x4e, 0xe4, 0x8d, 0xc7, 0x4b, 0xbb, 0xe6,
+					0x64, 0x3a, 0xef, 0x84, 0x66, 0x79, 0xb4, 0xcb, 0x39,
+					0x5a, 0x35, 0x2d, 0x5e, 0xd1, 0x15, 0x91, 0x2d, 0xf6,
+					0x96, 0xff, 0xe0, 0x70, 0x29, 0x32, 0x94, 0x6d, 0x71,
+					0x49, 0x2b, 0x44,
+				},
+			},
+			// Example 1.3
+			{
+				[]byte{0xd9, 0x4a, 0xe0, 0x83, 0x2e, 0x64, 0x45, 0xce,
+					0x42, 0x33, 0x1c, 0xb0, 0x6d, 0x53, 0x1a, 0x82, 0xb1,
+					0xdb, 0x4b, 0xaa, 0xd3, 0x0f, 0x74, 0x6d, 0xc9, 0x16,
+					0xdf, 0x24, 0xd4, 0xe3, 0xc2, 0x45, 0x1f, 0xff, 0x59,
+					0xa6, 0x42, 0x3e, 0xb0, 0xe1, 0xd0, 0x2d, 0x4f, 0xe6,
+					0x46, 0xcf, 0x69, 0x9d, 0xfd, 0x81, 0x8c, 0x6e, 0x97,
+					0xb0, 0x51,
+				},
+				[]byte{0x25, 0x14, 0xdf, 0x46, 0x95, 0x75, 0x5a, 0x67,
+					0xb2, 0x88, 0xea, 0xf4, 0x90, 0x5c, 0x36, 0xee, 0xc6,
+					0x6f, 0xd2, 0xfd,
+				},
+				[]byte{0x42, 0x37, 0x36, 0xed, 0x03, 0x5f, 0x60, 0x26,
+					0xaf, 0x27, 0x6c, 0x35, 0xc0, 0xb3, 0x74, 0x1b, 0x36,
+					0x5e, 0x5f, 0x76, 0xca, 0x09, 0x1b, 0x4e, 0x8c, 0x29,
+					0xe2, 0xf0, 0xbe, 0xfe, 0xe6, 0x03, 0x59, 0x5a, 0xa8,
+					0x32, 0x2d, 0x60, 0x2d, 0x2e, 0x62, 0x5e, 0x95, 0xeb,
+					0x81, 0xb2, 0xf1, 0xc9, 0x72, 0x4e, 0x82, 0x2e, 0xca,
+					0x76, 0xdb, 0x86, 0x18, 0xcf, 0x09, 0xc5, 0x34, 0x35,
+					0x03, 0xa4, 0x36, 0x08, 0x35, 0xb5, 0x90, 0x3b, 0xc6,
+					0x37, 0xe3, 0x87, 0x9f, 0xb0, 0x5e, 0x0e, 0xf3, 0x26,
+					0x85, 0xd5, 0xae, 0xc5, 0x06, 0x7c, 0xd7, 0xcc, 0x96,
+					0xfe, 0x4b, 0x26, 0x70, 0xb6, 0xea, 0xc3, 0x06, 0x6b,
+					0x1f, 0xcf, 0x56, 0x86, 0xb6, 0x85, 0x89, 0xaa, 0xfb,
+					0x7d, 0x62, 0x9b, 0x02, 0xd8, 0xf8, 0x62, 0x5c, 0xa3,
+					0x83, 0x36, 0x24, 0xd4, 0x80, 0x0f, 0xb0, 0x81, 0xb1,
+					0xcf, 0x94, 0xeb,
+				},
+			},
+		},
+	},
+	// Key 10
+	{"ae45ed5601cec6b8cc05f803935c674ddbe0d75c4c09fd7951fc6b0caec313a8df39970c518bffba5ed68f3f0d7f22a4029d413f1ae07e4ebe9e4177ce23e7f5404b569e4ee1bdcf3c1fb03ef113802d4f855eb9b5134b5a7c8085adcae6fa2fa1417ec3763be171b0c62b760ede23c12ad92b980884c641f5a8fac26bdad4a03381a22fe1b754885094c82506d4019a535a286afeb271bb9ba592de18dcf600c2aeeae56e02f7cf79fc14cf3bdc7cd84febbbf950ca90304b2219a7aa063aefa2c3c1980e560cd64afe779585b6107657b957857efde6010988ab7de417fc88d8f384c4e6e72c3f943e0c31c0c4a5cc36f879d8a3ac9d7d59860eaada6b83bb",
+		65537,
+		"056b04216fe5f354ac77250a4b6b0c8525a85c59b0bd80c56450a22d5f438e596a333aa875e291dd43f48cb88b9d5fc0d499f9fcd1c397f9afc070cd9e398c8d19e61db7c7410a6b2675dfbf5d345b804d201add502d5ce2dfcb091ce9997bbebe57306f383e4d588103f036f7e85d1934d152a323e4a8db451d6f4a5b1b0f102cc150e02feee2b88dea4ad4c1baccb24d84072d14e1d24a6771f7408ee30564fb86d4393a34bcf0b788501d193303f13a2284b001f0f649eaf79328d4ac5c430ab4414920a9460ed1b7bc40ec653e876d09abc509ae45b525190116a0c26101848298509c1c3bf3a483e7274054e15e97075036e989f60932807b5257751e79",
+		[]testEncryptOAEPMessage{
+			// Example 10.1
+			{
+				[]byte{0x8b, 0xba, 0x6b, 0xf8, 0x2a, 0x6c, 0x0f, 0x86,
+					0xd5, 0xf1, 0x75, 0x6e, 0x97, 0x95, 0x68, 0x70, 0xb0,
+					0x89, 0x53, 0xb0, 0x6b, 0x4e, 0xb2, 0x05, 0xbc, 0x16,
+					0x94, 0xee,
+				},
+				[]byte{0x47, 0xe1, 0xab, 0x71, 0x19, 0xfe, 0xe5, 0x6c,
+					0x95, 0xee, 0x5e, 0xaa, 0xd8, 0x6f, 0x40, 0xd0, 0xaa,
+					0x63, 0xbd, 0x33,
+				},
+				[]byte{0x53, 0xea, 0x5d, 0xc0, 0x8c, 0xd2, 0x60, 0xfb,
+					0x3b, 0x85, 0x85, 0x67, 0x28, 0x7f, 0xa9, 0x15, 0x52,
+					0xc3, 0x0b, 0x2f, 0xeb, 0xfb, 0xa2, 0x13, 0xf0, 0xae,
+					0x87, 0x70, 0x2d, 0x06, 0x8d, 0x19, 0xba, 0xb0, 0x7f,
+					0xe5, 0x74, 0x52, 0x3d, 0xfb, 0x42, 0x13, 0x9d, 0x68,
+					0xc3, 0xc5, 0xaf, 0xee, 0xe0, 0xbf, 0xe4, 0xcb, 0x79,
+					0x69, 0xcb, 0xf3, 0x82, 0xb8, 0x04, 0xd6, 0xe6, 0x13,
+					0x96, 0x14, 0x4e, 0x2d, 0x0e, 0x60, 0x74, 0x1f, 0x89,
+					0x93, 0xc3, 0x01, 0x4b, 0x58, 0xb9, 0xb1, 0x95, 0x7a,
+					0x8b, 0xab, 0xcd, 0x23, 0xaf, 0x85, 0x4f, 0x4c, 0x35,
+					0x6f, 0xb1, 0x66, 0x2a, 0xa7, 0x2b, 0xfc, 0xc7, 0xe5,
+					0x86, 0x55, 0x9d, 0xc4, 0x28, 0x0d, 0x16, 0x0c, 0x12,
+					0x67, 0x85, 0xa7, 0x23, 0xeb, 0xee, 0xbe, 0xff, 0x71,
+					0xf1, 0x15, 0x94, 0x44, 0x0a, 0xae, 0xf8, 0x7d, 0x10,
+					0x79, 0x3a, 0x87, 0x74, 0xa2, 0x39, 0xd4, 0xa0, 0x4c,
+					0x87, 0xfe, 0x14, 0x67, 0xb9, 0xda, 0xf8, 0x52, 0x08,
+					0xec, 0x6c, 0x72, 0x55, 0x79, 0x4a, 0x96, 0xcc, 0x29,
+					0x14, 0x2f, 0x9a, 0x8b, 0xd4, 0x18, 0xe3, 0xc1, 0xfd,
+					0x67, 0x34, 0x4b, 0x0c, 0xd0, 0x82, 0x9d, 0xf3, 0xb2,
+					0xbe, 0xc6, 0x02, 0x53, 0x19, 0x62, 0x93, 0xc6, 0xb3,
+					0x4d, 0x3f, 0x75, 0xd3, 0x2f, 0x21, 0x3d, 0xd4, 0x5c,
+					0x62, 0x73, 0xd5, 0x05, 0xad, 0xf4, 0xcc, 0xed, 0x10,
+					0x57, 0xcb, 0x75, 0x8f, 0xc2, 0x6a, 0xee, 0xfa, 0x44,
+					0x12, 0x55, 0xed, 0x4e, 0x64, 0xc1, 0x99, 0xee, 0x07,
+					0x5e, 0x7f, 0x16, 0x64, 0x61, 0x82, 0xfd, 0xb4, 0x64,
+					0x73, 0x9b, 0x68, 0xab, 0x5d, 0xaf, 0xf0, 0xe6, 0x3e,
+					0x95, 0x52, 0x01, 0x68, 0x24, 0xf0, 0x54, 0xbf, 0x4d,
+					0x3c, 0x8c, 0x90, 0xa9, 0x7b, 0xb6, 0xb6, 0x55, 0x32,
+					0x84, 0xeb, 0x42, 0x9f, 0xcc,
+				},
+			},
+		},
+	},
+}
diff --git a/src/crypto/rsa/testdata/pss-vect.txt.bz2 b/src/crypto/rsa/testdata/pss-vect.txt.bz2
new file mode 100644
index 000000000..ad3da1ac4
--- /dev/null
+++ b/src/crypto/rsa/testdata/pss-vect.txt.bz2