rsa.go

Documentation: crypto/rsa

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package rsa implements RSA encryption as specified in PKCS #1 and RFC 8017.
     6  //
     7  // RSA is a single, fundamental operation that is used in this package to
     8  // implement either public-key encryption or public-key signatures.
     9  //
    10  // The original specification for encryption and signatures with RSA is PKCS #1
    11  // and the terms "RSA encryption" and "RSA signatures" by default refer to
    12  // PKCS #1 version 1.5. However, that specification has flaws and new designs
    13  // should use version 2, usually called by just OAEP and PSS, where
    14  // possible.
    15  //
    16  // Two sets of interfaces are included in this package. When a more abstract
    17  // interface isn't necessary, there are functions for encrypting/decrypting
    18  // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract
    19  // over the public key primitive, the PrivateKey type implements the
    20  // Decrypter and Signer interfaces from the crypto package.
    21  //
    22  // The RSA operations in this package are not implemented using constant-time algorithms.
    23  package rsa
    24  
    25  import (
    26  	"crypto"
    27  	"crypto/internal/boring"
    28  	"crypto/internal/boring/bbig"
    29  	"crypto/internal/randutil"
    30  	"crypto/rand"
    31  	"crypto/subtle"
    32  	"errors"
    33  	"hash"
    34  	"io"
    35  	"math"
    36  	"math/big"
    37  )
    38  
    39  var bigZero = big.NewInt(0)
    40  var bigOne = big.NewInt(1)
    41  
    42  // A PublicKey represents the public part of an RSA key.
    43  type PublicKey struct {
    44  	N *big.Int // modulus
    45  	E int      // public exponent
    46  }
    47  
    48  // Any methods implemented on PublicKey might need to also be implemented on
    49  // PrivateKey, as the latter embeds the former and will expose its methods.
    50  
    51  // Size returns the modulus size in bytes. Raw signatures and ciphertexts
    52  // for or by this public key will have the same size.
    53  func (pub *PublicKey) Size() int {
    54  	return (pub.N.BitLen() + 7) / 8
    55  }
    56  
    57  // Equal reports whether pub and x have the same value.
    58  func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
    59  	xx, ok := x.(*PublicKey)
    60  	if !ok {
    61  		return false
    62  	}
    63  	return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E
    64  }
    65  
    66  // OAEPOptions is an interface for passing options to OAEP decryption using the
    67  // crypto.Decrypter interface.
    68  type OAEPOptions struct {
    69  	// Hash is the hash function that will be used when generating the mask.
    70  	Hash crypto.Hash
    71  	// Label is an arbitrary byte string that must be equal to the value
    72  	// used when encrypting.
    73  	Label []byte
    74  }
    75  
    76  var (
    77  	errPublicModulus       = errors.New("crypto/rsa: missing public modulus")
    78  	errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
    79  	errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
    80  )
    81  
    82  // checkPub sanity checks the public key before we use it.
    83  // We require pub.E to fit into a 32-bit integer so that we
    84  // do not have different behavior depending on whether
    85  // int is 32 or 64 bits. See also
    86  // https://www.imperialviolet.org/2012/03/16/rsae.html.
    87  func checkPub(pub *PublicKey) error {
    88  	if pub.N == nil {
    89  		return errPublicModulus
    90  	}
    91  	if pub.E < 2 {
    92  		return errPublicExponentSmall
    93  	}
    94  	if pub.E > 1<<31-1 {
    95  		return errPublicExponentLarge
    96  	}
    97  	return nil
    98  }
    99  
   100  // A PrivateKey represents an RSA key
   101  type PrivateKey struct {
   102  	PublicKey            // public part.
   103  	D         *big.Int   // private exponent
   104  	Primes    []*big.Int // prime factors of N, has >= 2 elements.
   105  
   106  	// Precomputed contains precomputed values that speed up private
   107  	// operations, if available.
   108  	Precomputed PrecomputedValues
   109  }
   110  
   111  // Public returns the public key corresponding to priv.
   112  func (priv *PrivateKey) Public() crypto.PublicKey {
   113  	return &priv.PublicKey
   114  }
   115  
   116  // Equal reports whether priv and x have equivalent values. It ignores
   117  // Precomputed values.
   118  func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
   119  	xx, ok := x.(*PrivateKey)
   120  	if !ok {
   121  		return false
   122  	}
   123  	if !priv.PublicKey.Equal(&xx.PublicKey) || priv.D.Cmp(xx.D) != 0 {
   124  		return false
   125  	}
   126  	if len(priv.Primes) != len(xx.Primes) {
   127  		return false
   128  	}
   129  	for i := range priv.Primes {
   130  		if priv.Primes[i].Cmp(xx.Primes[i]) != 0 {
   131  			return false
   132  		}
   133  	}
   134  	return true
   135  }
   136  
   137  // Sign signs digest with priv, reading randomness from rand. If opts is a
   138  // *PSSOptions then the PSS algorithm will be used, otherwise PKCS #1 v1.5 will
   139  // be used. digest must be the result of hashing the input message using
   140  // opts.HashFunc().
   141  //
   142  // This method implements crypto.Signer, which is an interface to support keys
   143  // where the private part is kept in, for example, a hardware module. Common
   144  // uses should use the Sign* functions in this package directly.
   145  func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
   146  	if pssOpts, ok := opts.(*PSSOptions); ok {
   147  		return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
   148  	}
   149  
   150  	return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
   151  }
   152  
   153  // Decrypt decrypts ciphertext with priv. If opts is nil or of type
   154  // *PKCS1v15DecryptOptions then PKCS #1 v1.5 decryption is performed. Otherwise
   155  // opts must have type *OAEPOptions and OAEP decryption is done.
   156  func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
   157  	if opts == nil {
   158  		return DecryptPKCS1v15(rand, priv, ciphertext)
   159  	}
   160  
   161  	switch opts := opts.(type) {
   162  	case *OAEPOptions:
   163  		return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)
   164  
   165  	case *PKCS1v15DecryptOptions:
   166  		if l := opts.SessionKeyLen; l > 0 {
   167  			plaintext = make([]byte, l)
   168  			if _, err := io.ReadFull(rand, plaintext); err != nil {
   169  				return nil, err
   170  			}
   171  			if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
   172  				return nil, err
   173  			}
   174  			return plaintext, nil
   175  		} else {
   176  			return DecryptPKCS1v15(rand, priv, ciphertext)
   177  		}
   178  
   179  	default:
   180  		return nil, errors.New("crypto/rsa: invalid options for Decrypt")
   181  	}
   182  }
   183  
   184  type PrecomputedValues struct {
   185  	Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
   186  	Qinv   *big.Int // Q^-1 mod P
   187  
   188  	// CRTValues is used for the 3rd and subsequent primes. Due to a
   189  	// historical accident, the CRT for the first two primes is handled
   190  	// differently in PKCS #1 and interoperability is sufficiently
   191  	// important that we mirror this.
   192  	CRTValues []CRTValue
   193  }
   194  
   195  // CRTValue contains the precomputed Chinese remainder theorem values.
   196  type CRTValue struct {
   197  	Exp   *big.Int // D mod (prime-1).
   198  	Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
   199  	R     *big.Int // product of primes prior to this (inc p and q).
   200  }
   201  
   202  // Validate performs basic sanity checks on the key.
   203  // It returns nil if the key is valid, or else an error describing a problem.
   204  func (priv *PrivateKey) Validate() error {
   205  	if err := checkPub(&priv.PublicKey); err != nil {
   206  		return err
   207  	}
   208  
   209  	// Check that Πprimes == n.
   210  	modulus := new(big.Int).Set(bigOne)
   211  	for _, prime := range priv.Primes {
   212  		// Any primes ≤ 1 will cause divide-by-zero panics later.
   213  		if prime.Cmp(bigOne) <= 0 {
   214  			return errors.New("crypto/rsa: invalid prime value")
   215  		}
   216  		modulus.Mul(modulus, prime)
   217  	}
   218  	if modulus.Cmp(priv.N) != 0 {
   219  		return errors.New("crypto/rsa: invalid modulus")
   220  	}
   221  
   222  	// Check that de ≡ 1 mod p-1, for each prime.
   223  	// This implies that e is coprime to each p-1 as e has a multiplicative
   224  	// inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
   225  	// exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
   226  	// mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.
   227  	congruence := new(big.Int)
   228  	de := new(big.Int).SetInt64(int64(priv.E))
   229  	de.Mul(de, priv.D)
   230  	for _, prime := range priv.Primes {
   231  		pminus1 := new(big.Int).Sub(prime, bigOne)
   232  		congruence.Mod(de, pminus1)
   233  		if congruence.Cmp(bigOne) != 0 {
   234  			return errors.New("crypto/rsa: invalid exponents")
   235  		}
   236  	}
   237  	return nil
   238  }
   239  
   240  // GenerateKey generates an RSA keypair of the given bit size using the
   241  // random source random (for example, crypto/rand.Reader).
   242  func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
   243  	return GenerateMultiPrimeKey(random, 2, bits)
   244  }
   245  
   246  // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
   247  // size and the given random source, as suggested in [1]. Although the public
   248  // keys are compatible (actually, indistinguishable) from the 2-prime case,
   249  // the private keys are not. Thus it may not be possible to export multi-prime
   250  // private keys in certain formats or to subsequently import them into other
   251  // code.
   252  //
   253  // Table 1 in [2] suggests maximum numbers of primes for a given size.
   254  //
   255  // [1] US patent 4405829 (1972, expired)
   256  // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
   257  func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
   258  	randutil.MaybeReadByte(random)
   259  
   260  	if boring.Enabled && random == boring.RandReader && nprimes == 2 && (bits == 2048 || bits == 3072) {
   261  		bN, bE, bD, bP, bQ, bDp, bDq, bQinv, err := boring.GenerateKeyRSA(bits)
   262  		if err != nil {
   263  			return nil, err
   264  		}
   265  		N := bbig.Dec(bN)
   266  		E := bbig.Dec(bE)
   267  		D := bbig.Dec(bD)
   268  		P := bbig.Dec(bP)
   269  		Q := bbig.Dec(bQ)
   270  		Dp := bbig.Dec(bDp)
   271  		Dq := bbig.Dec(bDq)
   272  		Qinv := bbig.Dec(bQinv)
   273  		e64 := E.Int64()
   274  		if !E.IsInt64() || int64(int(e64)) != e64 {
   275  			return nil, errors.New("crypto/rsa: generated key exponent too large")
   276  		}
   277  		key := &PrivateKey{
   278  			PublicKey: PublicKey{
   279  				N: N,
   280  				E: int(e64),
   281  			},
   282  			D:      D,
   283  			Primes: []*big.Int{P, Q},
   284  			Precomputed: PrecomputedValues{
   285  				Dp:        Dp,
   286  				Dq:        Dq,
   287  				Qinv:      Qinv,
   288  				CRTValues: make([]CRTValue, 0), // non-nil, to match Precompute
   289  			},
   290  		}
   291  		return key, nil
   292  	}
   293  
   294  	priv := new(PrivateKey)
   295  	priv.E = 65537
   296  
   297  	if nprimes < 2 {
   298  		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
   299  	}
   300  
   301  	if bits < 64 {
   302  		primeLimit := float64(uint64(1) << uint(bits/nprimes))
   303  		// pi approximates the number of primes less than primeLimit
   304  		pi := primeLimit / (math.Log(primeLimit) - 1)
   305  		// Generated primes start with 11 (in binary) so we can only
   306  		// use a quarter of them.
   307  		pi /= 4
   308  		// Use a factor of two to ensure that key generation terminates
   309  		// in a reasonable amount of time.
   310  		pi /= 2
   311  		if pi <= float64(nprimes) {
   312  			return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
   313  		}
   314  	}
   315  
   316  	primes := make([]*big.Int, nprimes)
   317  
   318  NextSetOfPrimes:
   319  	for {
   320  		todo := bits
   321  		// crypto/rand should set the top two bits in each prime.
   322  		// Thus each prime has the form
   323  		//   p_i = 2^bitlen(p_i) × 0.11... (in base 2).
   324  		// And the product is:
   325  		//   P = 2^todo × α
   326  		// where α is the product of nprimes numbers of the form 0.11...
   327  		//
   328  		// If α < 1/2 (which can happen for nprimes > 2), we need to
   329  		// shift todo to compensate for lost bits: the mean value of 0.11...
   330  		// is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
   331  		// will give good results.
   332  		if nprimes >= 7 {
   333  			todo += (nprimes - 2) / 5
   334  		}
   335  		for i := 0; i < nprimes; i++ {
   336  			var err error
   337  			primes[i], err = rand.Prime(random, todo/(nprimes-i))
   338  			if err != nil {
   339  				return nil, err
   340  			}
   341  			todo -= primes[i].BitLen()
   342  		}
   343  
   344  		// Make sure that primes is pairwise unequal.
   345  		for i, prime := range primes {
   346  			for j := 0; j < i; j++ {
   347  				if prime.Cmp(primes[j]) == 0 {
   348  					continue NextSetOfPrimes
   349  				}
   350  			}
   351  		}
   352  
   353  		n := new(big.Int).Set(bigOne)
   354  		totient := new(big.Int).Set(bigOne)
   355  		pminus1 := new(big.Int)
   356  		for _, prime := range primes {
   357  			n.Mul(n, prime)
   358  			pminus1.Sub(prime, bigOne)
   359  			totient.Mul(totient, pminus1)
   360  		}
   361  		if n.BitLen() != bits {
   362  			// This should never happen for nprimes == 2 because
   363  			// crypto/rand should set the top two bits in each prime.
   364  			// For nprimes > 2 we hope it does not happen often.
   365  			continue NextSetOfPrimes
   366  		}
   367  
   368  		priv.D = new(big.Int)
   369  		e := big.NewInt(int64(priv.E))
   370  		ok := priv.D.ModInverse(e, totient)
   371  
   372  		if ok != nil {
   373  			priv.Primes = primes
   374  			priv.N = n
   375  			break
   376  		}
   377  	}
   378  
   379  	priv.Precompute()
   380  	return priv, nil
   381  }
   382  
   383  // incCounter increments a four byte, big-endian counter.
   384  func incCounter(c *[4]byte) {
   385  	if c[3]++; c[3] != 0 {
   386  		return
   387  	}
   388  	if c[2]++; c[2] != 0 {
   389  		return
   390  	}
   391  	if c[1]++; c[1] != 0 {
   392  		return
   393  	}
   394  	c[0]++
   395  }
   396  
   397  // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
   398  // specified in PKCS #1 v2.1.
   399  func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
   400  	var counter [4]byte
   401  	var digest []byte
   402  
   403  	done := 0
   404  	for done < len(out) {
   405  		hash.Write(seed)
   406  		hash.Write(counter[0:4])
   407  		digest = hash.Sum(digest[:0])
   408  		hash.Reset()
   409  
   410  		for i := 0; i < len(digest) && done < len(out); i++ {
   411  			out[done] ^= digest[i]
   412  			done++
   413  		}
   414  		incCounter(&counter)
   415  	}
   416  }
   417  
   418  // ErrMessageTooLong is returned when attempting to encrypt a message which is
   419  // too large for the size of the public key.
   420  var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")
   421  
   422  func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
   423  	boring.Unreachable()
   424  	e := big.NewInt(int64(pub.E))
   425  	c.Exp(m, e, pub.N)
   426  	return c
   427  }
   428  
   429  // EncryptOAEP encrypts the given message with RSA-OAEP.
   430  //
   431  // OAEP is parameterised by a hash function that is used as a random oracle.
   432  // Encryption and decryption of a given message must use the same hash function
   433  // and sha256.New() is a reasonable choice.
   434  //
   435  // The random parameter is used as a source of entropy to ensure that
   436  // encrypting the same message twice doesn't result in the same ciphertext.
   437  //
   438  // The label parameter may contain arbitrary data that will not be encrypted,
   439  // but which gives important context to the message. For example, if a given
   440  // public key is used to encrypt two types of messages then distinct label
   441  // values could be used to ensure that a ciphertext for one purpose cannot be
   442  // used for another by an attacker. If not required it can be empty.
   443  //
   444  // The message must be no longer than the length of the public modulus minus
   445  // twice the hash length, minus a further 2.
   446  func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) {
   447  	if err := checkPub(pub); err != nil {
   448  		return nil, err
   449  	}
   450  	hash.Reset()
   451  	k := pub.Size()
   452  	if len(msg) > k-2*hash.Size()-2 {
   453  		return nil, ErrMessageTooLong
   454  	}
   455  
   456  	if boring.Enabled && random == boring.RandReader {
   457  		bkey, err := boringPublicKey(pub)
   458  		if err != nil {
   459  			return nil, err
   460  		}
   461  		return boring.EncryptRSAOAEP(hash, bkey, msg, label)
   462  	}
   463  	boring.UnreachableExceptTests()
   464  
   465  	hash.Write(label)
   466  	lHash := hash.Sum(nil)
   467  	hash.Reset()
   468  
   469  	em := make([]byte, k)
   470  	seed := em[1 : 1+hash.Size()]
   471  	db := em[1+hash.Size():]
   472  
   473  	copy(db[0:hash.Size()], lHash)
   474  	db[len(db)-len(msg)-1] = 1
   475  	copy(db[len(db)-len(msg):], msg)
   476  
   477  	_, err := io.ReadFull(random, seed)
   478  	if err != nil {
   479  		return nil, err
   480  	}
   481  
   482  	mgf1XOR(db, hash, seed)
   483  	mgf1XOR(seed, hash, db)
   484  
   485  	if boring.Enabled {
   486  		var bkey *boring.PublicKeyRSA
   487  		bkey, err = boringPublicKey(pub)
   488  		if err != nil {
   489  			return nil, err
   490  		}
   491  		return boring.EncryptRSANoPadding(bkey, em)
   492  	}
   493  
   494  	m := new(big.Int)
   495  	m.SetBytes(em)
   496  	c := encrypt(new(big.Int), pub, m)
   497  
   498  	out := make([]byte, k)
   499  	return c.FillBytes(out), nil
   500  }
   501  
   502  // ErrDecryption represents a failure to decrypt a message.
   503  // It is deliberately vague to avoid adaptive attacks.
   504  var ErrDecryption = errors.New("crypto/rsa: decryption error")
   505  
   506  // ErrVerification represents a failure to verify a signature.
   507  // It is deliberately vague to avoid adaptive attacks.
   508  var ErrVerification = errors.New("crypto/rsa: verification error")
   509  
   510  // Precompute performs some calculations that speed up private key operations
   511  // in the future.
   512  func (priv *PrivateKey) Precompute() {
   513  	if priv.Precomputed.Dp != nil {
   514  		return
   515  	}
   516  
   517  	priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
   518  	priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
   519  
   520  	priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
   521  	priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
   522  
   523  	priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
   524  
   525  	r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
   526  	priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
   527  	for i := 2; i < len(priv.Primes); i++ {
   528  		prime := priv.Primes[i]
   529  		values := &priv.Precomputed.CRTValues[i-2]
   530  
   531  		values.Exp = new(big.Int).Sub(prime, bigOne)
   532  		values.Exp.Mod(priv.D, values.Exp)
   533  
   534  		values.R = new(big.Int).Set(r)
   535  		values.Coeff = new(big.Int).ModInverse(r, prime)
   536  
   537  		r.Mul(r, prime)
   538  	}
   539  }
   540  
   541  // decrypt performs an RSA decryption, resulting in a plaintext integer. If a
   542  // random source is given, RSA blinding is used.
   543  func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
   544  	if len(priv.Primes) <= 2 {
   545  		boring.Unreachable()
   546  	}
   547  	// TODO(agl): can we get away with reusing blinds?
   548  	if c.Cmp(priv.N) > 0 {
   549  		err = ErrDecryption
   550  		return
   551  	}
   552  	if priv.N.Sign() == 0 {
   553  		return nil, ErrDecryption
   554  	}
   555  
   556  	var ir *big.Int
   557  	if random != nil {
   558  		randutil.MaybeReadByte(random)
   559  
   560  		// Blinding enabled. Blinding involves multiplying c by r^e.
   561  		// Then the decryption operation performs (m^e * r^e)^d mod n
   562  		// which equals mr mod n. The factor of r can then be removed
   563  		// by multiplying by the multiplicative inverse of r.
   564  
   565  		var r *big.Int
   566  		ir = new(big.Int)
   567  		for {
   568  			r, err = rand.Int(random, priv.N)
   569  			if err != nil {
   570  				return
   571  			}
   572  			if r.Cmp(bigZero) == 0 {
   573  				r = bigOne
   574  			}
   575  			ok := ir.ModInverse(r, priv.N)
   576  			if ok != nil {
   577  				break
   578  			}
   579  		}
   580  		bigE := big.NewInt(int64(priv.E))
   581  		rpowe := new(big.Int).Exp(r, bigE, priv.N) // N != 0
   582  		cCopy := new(big.Int).Set(c)
   583  		cCopy.Mul(cCopy, rpowe)
   584  		cCopy.Mod(cCopy, priv.N)
   585  		c = cCopy
   586  	}
   587  
   588  	if priv.Precomputed.Dp == nil {
   589  		m = new(big.Int).Exp(c, priv.D, priv.N)
   590  	} else {
   591  		// We have the precalculated values needed for the CRT.
   592  		m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
   593  		m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
   594  		m.Sub(m, m2)
   595  		if m.Sign() < 0 {
   596  			m.Add(m, priv.Primes[0])
   597  		}
   598  		m.Mul(m, priv.Precomputed.Qinv)
   599  		m.Mod(m, priv.Primes[0])
   600  		m.Mul(m, priv.Primes[1])
   601  		m.Add(m, m2)
   602  
   603  		for i, values := range priv.Precomputed.CRTValues {
   604  			prime := priv.Primes[2+i]
   605  			m2.Exp(c, values.Exp, prime)
   606  			m2.Sub(m2, m)
   607  			m2.Mul(m2, values.Coeff)
   608  			m2.Mod(m2, prime)
   609  			if m2.Sign() < 0 {
   610  				m2.Add(m2, prime)
   611  			}
   612  			m2.Mul(m2, values.R)
   613  			m.Add(m, m2)
   614  		}
   615  	}
   616  
   617  	if ir != nil {
   618  		// Unblind.
   619  		m.Mul(m, ir)
   620  		m.Mod(m, priv.N)
   621  	}
   622  
   623  	return
   624  }
   625  
   626  func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
   627  	m, err = decrypt(random, priv, c)
   628  	if err != nil {
   629  		return nil, err
   630  	}
   631  
   632  	// In order to defend against errors in the CRT computation, m^e is
   633  	// calculated, which should match the original ciphertext.
   634  	check := encrypt(new(big.Int), &priv.PublicKey, m)
   635  	if c.Cmp(check) != 0 {
   636  		return nil, errors.New("rsa: internal error")
   637  	}
   638  	return m, nil
   639  }
   640  
   641  // DecryptOAEP decrypts ciphertext using RSA-OAEP.
   642  //
   643  // OAEP is parameterised by a hash function that is used as a random oracle.
   644  // Encryption and decryption of a given message must use the same hash function
   645  // and sha256.New() is a reasonable choice.
   646  //
   647  // The random parameter, if not nil, is used to blind the private-key operation
   648  // and avoid timing side-channel attacks. Blinding is purely internal to this
   649  // function – the random data need not match that used when encrypting.
   650  //
   651  // The label parameter must match the value given when encrypting. See
   652  // EncryptOAEP for details.
   653  func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
   654  	if err := checkPub(&priv.PublicKey); err != nil {
   655  		return nil, err
   656  	}
   657  	k := priv.Size()
   658  	if len(ciphertext) > k ||
   659  		k < hash.Size()*2+2 {
   660  		return nil, ErrDecryption
   661  	}
   662  
   663  	if boring.Enabled {
   664  		bkey, err := boringPrivateKey(priv)
   665  		if err != nil {
   666  			return nil, err
   667  		}
   668  		out, err := boring.DecryptRSAOAEP(hash, bkey, ciphertext, label)
   669  		if err != nil {
   670  			return nil, ErrDecryption
   671  		}
   672  		return out, nil
   673  	}
   674  	c := new(big.Int).SetBytes(ciphertext)
   675  
   676  	m, err := decrypt(random, priv, c)
   677  	if err != nil {
   678  		return nil, err
   679  	}
   680  
   681  	hash.Write(label)
   682  	lHash := hash.Sum(nil)
   683  	hash.Reset()
   684  
   685  	// We probably leak the number of leading zeros.
   686  	// It's not clear that we can do anything about this.
   687  	em := m.FillBytes(make([]byte, k))
   688  
   689  	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
   690  
   691  	seed := em[1 : hash.Size()+1]
   692  	db := em[hash.Size()+1:]
   693  
   694  	mgf1XOR(seed, hash, db)
   695  	mgf1XOR(db, hash, seed)
   696  
   697  	lHash2 := db[0:hash.Size()]
   698  
   699  	// We have to validate the plaintext in constant time in order to avoid
   700  	// attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
   701  	// Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
   702  	// v2.0. In J. Kilian, editor, Advances in Cryptology.
   703  	lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
   704  
   705  	// The remainder of the plaintext must be zero or more 0x00, followed
   706  	// by 0x01, followed by the message.
   707  	//   lookingForIndex: 1 iff we are still looking for the 0x01
   708  	//   index: the offset of the first 0x01 byte
   709  	//   invalid: 1 iff we saw a non-zero byte before the 0x01.
   710  	var lookingForIndex, index, invalid int
   711  	lookingForIndex = 1
   712  	rest := db[hash.Size():]
   713  
   714  	for i := 0; i < len(rest); i++ {
   715  		equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
   716  		equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
   717  		index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
   718  		lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
   719  		invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
   720  	}
   721  
   722  	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
   723  		return nil, ErrDecryption
   724  	}
   725  
   726  	return rest[index+1:], nil
   727  }
   728
View as plain text