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