...
Run Format

Source file src/crypto/rsa/rsa.go

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

View as plain text