src/crypto/rsa/rsa.go - go - Git at Google

 // 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.
 //
 // RSA is a single, fundamental operation that is used in this package to
 // implement either public-key encryption or public-key signatures.
 //
 // The original specification for encryption and signatures with RSA is PKCS#1
 // and the terms "RSA encryption" and "RSA signatures" by default refer to
 // PKCS#1 version 1.5. However, that specification has flaws and new designs
 // should use version two, usually called by just OAEP and PSS, where
 // possible.
 //
 // Two sets of interfaces are included in this package. When a more abstract
 // interface isn't necessary, there are functions for encrypting/decrypting
 // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract
 // over the public-key primitive, the PrivateKey struct implements the
 // Decrypter and Signer interfaces from the crypto package.
 //
 // The RSA operations in this package are not implemented using constant-time algorithms.
 package rsa

 import (
 	"crypto"
 	"crypto/rand"
 	"crypto/subtle"
 	"errors"
 	"hash"
 	"io"
 	"math"
 	"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
 }

 // OAEPOptions is an interface for passing options to OAEP decryption using the
 // crypto.Decrypter interface.
 type OAEPOptions struct {
 	// Hash is the hash function that will be used when generating the mask.
 	Hash crypto.Hash
 	// Label is an arbitrary byte string that must be equal to the value
 	// used when encrypting.
 	Label []byte
 }

 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 digest 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 implements crypto.Signer, which is an interface 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 directly.
 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
 	if pssOpts, ok := opts.(*PSSOptions); ok {
 		return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
 	}

 	return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
 }

 // Decrypt decrypts ciphertext with priv. If opts is nil or of type
 // *PKCS1v15DecryptOptions then PKCS#1 v1.5 decryption is performed. Otherwise
 // opts must have type *OAEPOptions and OAEP decryption is done.
 func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
 	if opts == nil {
 		return DecryptPKCS1v15(rand, priv, ciphertext)
 	}

 	switch opts := opts.(type) {
 	case *OAEPOptions:
 		return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)

 	case *PKCS1v15DecryptOptions:
 		if l := opts.SessionKeyLen; l > 0 {
 			plaintext = make([]byte, l)
 			if _, err := io.ReadFull(rand, plaintext); err != nil {
 				return nil, err
 			}
 			if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
 				return nil, err
 			}
 			return plaintext, nil
 		} else {
 			return DecryptPKCS1v15(rand, priv, ciphertext)
 		}

 	default:
 		return nil, errors.New("crypto/rsa: invalid options for Decrypt")
 	}
 }

 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 Πprimes == n.
 	modulus := new(big.Int).Set(bigOne)
 	for _, prime := range priv.Primes {
 		// Any primes ≤ 1 will cause divide-by-zero panics later.
 		if prime.Cmp(bigOne) <= 0 {
 			return errors.New("crypto/rsa: invalid prime value")
 		}
 		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) (*PrivateKey, 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) (*PrivateKey, error) {
 	priv := new(PrivateKey)
 	priv.E = 65537

 	if nprimes < 2 {
 		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
 	}

 	if bits < 64 {
 		primeLimit := float64(uint64(1) << uint(bits/nprimes))
 		// pi approximates the number of primes less than primeLimit
 		pi := primeLimit / (math.Log(primeLimit) - 1)
 		// Generated primes start with 11 (in binary) so we can only
 		// use a quarter of them.
 		pi /= 4
 		// Use a factor of two to ensure that key generation terminates
 		// in a reasonable amount of time.
 		pi /= 2
 		if pi <= float64(nprimes) {
 			return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
 		}
 	}

 	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++ {
 			var err error
 			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)
 		e := big.NewInt(int64(priv.E))
 		g.GCD(priv.D, nil, 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 priv, nil
 }

 // 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.
 //
 // OAEP is parameterised by a hash function that is used as a random oracle.
 // Encryption and decryption of a given message must use the same hash function
 // and sha256.New() is a reasonable choice.
 //
 // The random parameter is used as a source of entropy to ensure that
 // encrypting the same message twice doesn't result in the same ciphertext.
 //
 // The label parameter may contain arbitrary data that will not be encrypted,
 // but which gives important context to the message. For example, if a given
 // public key is used to decrypt two types of messages then distinct label
 // values could be used to ensure that a ciphertext for one purpose cannot be
 // used for another by an attacker. If not required it can be empty.
 //
 // The message must be no longer than the length of the public modulus minus
 // twice the hash length, minus a further 2.
 func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, 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 {
 		return nil, ErrMessageTooLong
 	}

 	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 nil, err
 	}

 	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 out, nil
 }

 // 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)
 	g.GCD(x, nil, 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
 	}
 	if priv.N.Sign() == 0 {
 		return nil, ErrDecryption
 	}

 	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) // N != 0
 		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
 }

 func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
 	m, err = decrypt(random, priv, c)
 	if err != nil {
 		return nil, err
 	}

 	// In order to defend against errors in the CRT computation, m^e is
 	// calculated, which should match the original ciphertext.
 	check := encrypt(new(big.Int), &priv.PublicKey, m)
 	if c.Cmp(check) != 0 {
 		return nil, errors.New("rsa: internal error")
 	}
 	return m, nil
 }

 // DecryptOAEP decrypts ciphertext using RSA-OAEP.

 // OAEP is parameterised by a hash function that is used as a random oracle.
 // Encryption and decryption of a given message must use the same hash function
 // and sha256.New() is a reasonable choice.
 //
 // The random parameter, if not nil, is used to blind the private-key operation
 // and avoid timing side-channel attacks. Blinding is purely internal to this
 // function – the random data need not match that used when encrypting.
 //
 // The label parameter must match the value given when encrypting. See
 // EncryptOAEP for details.
 func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, 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 {
 		return nil, ErrDecryption
 	}

 	c := new(big.Int).SetBytes(ciphertext)

 	m, err := decrypt(random, priv, c)
 	if err != nil {
 		return nil, err
 	}

 	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 {
 		return nil, ErrDecryption
 	}

 	return rest[index+1:], nil
 }

 // 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
 }
	// 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.
	//
	// RSA is a single, fundamental operation that is used in this package to
	// implement either public-key encryption or public-key signatures.
	//
	// The original specification for encryption and signatures with RSA is PKCS#1
	// and the terms "RSA encryption" and "RSA signatures" by default refer to
	// PKCS#1 version 1.5. However, that specification has flaws and new designs
	// should use version two, usually called by just OAEP and PSS, where
	// possible.
	//
	// Two sets of interfaces are included in this package. When a more abstract
	// interface isn't necessary, there are functions for encrypting/decrypting
	// with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract
	// over the public-key primitive, the PrivateKey struct implements the
	// Decrypter and Signer interfaces from the crypto package.
	//
	// The RSA operations in this package are not implemented using constant-time algorithms.
	package rsa

	import (
	"crypto"
	"crypto/rand"
	"crypto/subtle"
	"errors"
	"hash"
	"io"
	"math"
	"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
	}

	// OAEPOptions is an interface for passing options to OAEP decryption using the
	// crypto.Decrypter interface.
	type OAEPOptions struct {
	// Hash is the hash function that will be used when generating the mask.
	Hash crypto.Hash
	// Label is an arbitrary byte string that must be equal to the value
	// used when encrypting.
	Label []byte
	}

	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 digest 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 implements crypto.Signer, which is an interface 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 directly.
	func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
	if pssOpts, ok := opts.(*PSSOptions); ok {
	return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
	}

	return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
	}

	// Decrypt decrypts ciphertext with priv. If opts is nil or of type
	// *PKCS1v15DecryptOptions then PKCS#1 v1.5 decryption is performed. Otherwise
	// opts must have type *OAEPOptions and OAEP decryption is done.
	func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
	if opts == nil {
	return DecryptPKCS1v15(rand, priv, ciphertext)
	}

	switch opts := opts.(type) {
	case *OAEPOptions:
	return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)

	case *PKCS1v15DecryptOptions:
	if l := opts.SessionKeyLen; l > 0 {
	plaintext = make([]byte, l)
	if _, err := io.ReadFull(rand, plaintext); err != nil {
	return nil, err
	}
	if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
	return nil, err
	}
	return plaintext, nil
	} else {
	return DecryptPKCS1v15(rand, priv, ciphertext)
	}

	default:
	return nil, errors.New("crypto/rsa: invalid options for Decrypt")
	}
	}

	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 Πprimes == n.
	modulus := new(big.Int).Set(bigOne)
	for _, prime := range priv.Primes {
	// Any primes ≤ 1 will cause divide-by-zero panics later.
	if prime.Cmp(bigOne) <= 0 {
	return errors.New("crypto/rsa: invalid prime value")
	}
	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) (*PrivateKey, 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) (*PrivateKey, error) {
	priv := new(PrivateKey)
	priv.E = 65537

	if nprimes < 2 {
	return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	if bits < 64 {
	primeLimit := float64(uint64(1) << uint(bits/nprimes))
	// pi approximates the number of primes less than primeLimit
	pi := primeLimit / (math.Log(primeLimit) - 1)
	// Generated primes start with 11 (in binary) so we can only
	// use a quarter of them.
	pi /= 4
	// Use a factor of two to ensure that key generation terminates
	// in a reasonable amount of time.
	pi /= 2
	if pi <= float64(nprimes) {
	return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
	}
	}

	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++ {
	var err error
	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)
	e := big.NewInt(int64(priv.E))
	g.GCD(priv.D, nil, 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 priv, nil
	}

	// 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.
	//
	// OAEP is parameterised by a hash function that is used as a random oracle.
	// Encryption and decryption of a given message must use the same hash function
	// and sha256.New() is a reasonable choice.
	//
	// The random parameter is used as a source of entropy to ensure that
	// encrypting the same message twice doesn't result in the same ciphertext.
	//
	// The label parameter may contain arbitrary data that will not be encrypted,
	// but which gives important context to the message. For example, if a given
	// public key is used to decrypt two types of messages then distinct label
	// values could be used to ensure that a ciphertext for one purpose cannot be
	// used for another by an attacker. If not required it can be empty.
	//
	// The message must be no longer than the length of the public modulus minus
	// twice the hash length, minus a further 2.
	func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, 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 {
	return nil, ErrMessageTooLong
	}

	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 nil, err
	}

	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 out, nil
	}

	// 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)
	g.GCD(x, nil, 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
	}
	if priv.N.Sign() == 0 {
	return nil, ErrDecryption
	}

	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) // N != 0
	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
	}

	func decryptAndCheck(random io.Reader, priv PrivateKey, c big.Int) (m *big.Int, err error) {
	m, err = decrypt(random, priv, c)
	if err != nil {
	return nil, err
	}

	// In order to defend against errors in the CRT computation, m^e is
	// calculated, which should match the original ciphertext.
	check := encrypt(new(big.Int), &priv.PublicKey, m)
	if c.Cmp(check) != 0 {
	return nil, errors.New("rsa: internal error")
	}
	return m, nil
	}

	// DecryptOAEP decrypts ciphertext using RSA-OAEP.

	// OAEP is parameterised by a hash function that is used as a random oracle.
	// Encryption and decryption of a given message must use the same hash function
	// and sha256.New() is a reasonable choice.
	//
	// The random parameter, if not nil, is used to blind the private-key operation
	// and avoid timing side-channel attacks. Blinding is purely internal to this
	// function – the random data need not match that used when encrypting.
	//
	// The label parameter must match the value given when encrypting. See
	// EncryptOAEP for details.
	func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, 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 {
	return nil, ErrDecryption
	}

	c := new(big.Int).SetBytes(ciphertext)

	m, err := decrypt(random, priv, c)
	if err != nil {
	return nil, err
	}

	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 {
	return nil, ErrDecryption
	}

	return rest[index+1:], nil
	}

	// 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
	}