...
Run Format

Source file src/crypto/rsa/rsa.go

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

View as plain text