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