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