| // Copyright 2009 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Package rsa implements RSA encryption as specified in PKCS #1 and RFC 8017. |
| // |
| // RSA is a single, fundamental operation that is used in this package to |
| // implement either public-key encryption or public-key signatures. |
| // |
| // The original specification for encryption and signatures with RSA is PKCS #1 |
| // and the terms "RSA encryption" and "RSA signatures" by default refer to |
| // PKCS #1 version 1.5. However, that specification has flaws and new designs |
| // should use version 2, usually called by just OAEP and PSS, where |
| // possible. |
| // |
| // Two sets of interfaces are included in this package. When a more abstract |
| // interface isn't necessary, there are functions for encrypting/decrypting |
| // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract |
| // over the public key primitive, the PrivateKey type implements the |
| // Decrypter and Signer interfaces from the crypto package. |
| // |
| // Operations in this package are implemented using constant-time algorithms, |
| // except for [GenerateKey], [PrivateKey.Precompute], and [PrivateKey.Validate]. |
| // Every other operation only leaks the bit size of the involved values, which |
| // all depend on the selected key size. |
| package rsa |
| |
| import ( |
| "crypto" |
| "crypto/internal/bigmod" |
| "crypto/internal/boring" |
| "crypto/internal/boring/bbig" |
| "crypto/internal/randutil" |
| "crypto/rand" |
| "crypto/subtle" |
| "errors" |
| "hash" |
| "io" |
| "math" |
| "math/big" |
| ) |
| |
| var bigOne = big.NewInt(1) |
| |
| // A PublicKey represents the public part of an RSA key. |
| type PublicKey struct { |
| N *big.Int // modulus |
| E int // public exponent |
| } |
| |
| // Any methods implemented on PublicKey might need to also be implemented on |
| // PrivateKey, as the latter embeds the former and will expose its methods. |
| |
| // Size returns the modulus size in bytes. Raw signatures and ciphertexts |
| // for or by this public key will have the same size. |
| func (pub *PublicKey) Size() int { |
| return (pub.N.BitLen() + 7) / 8 |
| } |
| |
| // Equal reports whether pub and x have the same value. |
| func (pub *PublicKey) Equal(x crypto.PublicKey) bool { |
| xx, ok := x.(*PublicKey) |
| if !ok { |
| return false |
| } |
| return bigIntEqual(pub.N, xx.N) && pub.E == xx.E |
| } |
| |
| // OAEPOptions is an interface for passing options to OAEP decryption using the |
| // crypto.Decrypter interface. |
| type OAEPOptions struct { |
| // Hash is the hash function that will be used when generating the mask. |
| Hash crypto.Hash |
| |
| // MGFHash is the hash function used for MGF1. |
| // If zero, Hash is used instead. |
| MGFHash crypto.Hash |
| |
| // Label is an arbitrary byte string that must be equal to the value |
| // used when encrypting. |
| Label []byte |
| } |
| |
| var ( |
| errPublicModulus = errors.New("crypto/rsa: missing public modulus") |
| errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small") |
| errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large") |
| ) |
| |
| // checkPub sanity checks the public key before we use it. |
| // We require pub.E to fit into a 32-bit integer so that we |
| // do not have different behavior depending on whether |
| // int is 32 or 64 bits. See also |
| // https://www.imperialviolet.org/2012/03/16/rsae.html. |
| func checkPub(pub *PublicKey) error { |
| if pub.N == nil { |
| return errPublicModulus |
| } |
| if pub.E < 2 { |
| return errPublicExponentSmall |
| } |
| if pub.E > 1<<31-1 { |
| return errPublicExponentLarge |
| } |
| return nil |
| } |
| |
| // A PrivateKey represents an RSA key |
| type PrivateKey struct { |
| PublicKey // public part. |
| D *big.Int // private exponent |
| Primes []*big.Int // prime factors of N, has >= 2 elements. |
| |
| // Precomputed contains precomputed values that speed up RSA operations, |
| // if available. It must be generated by calling PrivateKey.Precompute and |
| // must not be modified. |
| Precomputed PrecomputedValues |
| } |
| |
| // Public returns the public key corresponding to priv. |
| func (priv *PrivateKey) Public() crypto.PublicKey { |
| return &priv.PublicKey |
| } |
| |
| // Equal reports whether priv and x have equivalent values. It ignores |
| // Precomputed values. |
| func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool { |
| xx, ok := x.(*PrivateKey) |
| if !ok { |
| return false |
| } |
| if !priv.PublicKey.Equal(&xx.PublicKey) || !bigIntEqual(priv.D, xx.D) { |
| return false |
| } |
| if len(priv.Primes) != len(xx.Primes) { |
| return false |
| } |
| for i := range priv.Primes { |
| if !bigIntEqual(priv.Primes[i], xx.Primes[i]) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| // bigIntEqual reports whether a and b are equal leaking only their bit length |
| // through timing side-channels. |
| func bigIntEqual(a, b *big.Int) bool { |
| return subtle.ConstantTimeCompare(a.Bytes(), b.Bytes()) == 1 |
| } |
| |
| // Sign signs digest with priv, reading randomness from rand. If opts is a |
| // *PSSOptions then the PSS algorithm will be used, otherwise PKCS #1 v1.5 will |
| // be used. digest must be the result of hashing the input message using |
| // opts.HashFunc(). |
| // |
| // This method implements crypto.Signer, which is an interface to support keys |
| // where the private part is kept in, for example, a hardware module. Common |
| // uses should use the Sign* functions in this package directly. |
| func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) { |
| if pssOpts, ok := opts.(*PSSOptions); ok { |
| return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts) |
| } |
| |
| return SignPKCS1v15(rand, priv, opts.HashFunc(), digest) |
| } |
| |
| // Decrypt decrypts ciphertext with priv. If opts is nil or of type |
| // *PKCS1v15DecryptOptions then PKCS #1 v1.5 decryption is performed. Otherwise |
| // opts must have type *OAEPOptions and OAEP decryption is done. |
| func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) { |
| if opts == nil { |
| return DecryptPKCS1v15(rand, priv, ciphertext) |
| } |
| |
| switch opts := opts.(type) { |
| case *OAEPOptions: |
| if opts.MGFHash == 0 { |
| return decryptOAEP(opts.Hash.New(), opts.Hash.New(), rand, priv, ciphertext, opts.Label) |
| } else { |
| return decryptOAEP(opts.Hash.New(), opts.MGFHash.New(), rand, priv, ciphertext, opts.Label) |
| } |
| |
| case *PKCS1v15DecryptOptions: |
| if l := opts.SessionKeyLen; l > 0 { |
| plaintext = make([]byte, l) |
| if _, err := io.ReadFull(rand, plaintext); err != nil { |
| return nil, err |
| } |
| if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil { |
| return nil, err |
| } |
| return plaintext, nil |
| } else { |
| return DecryptPKCS1v15(rand, priv, ciphertext) |
| } |
| |
| default: |
| return nil, errors.New("crypto/rsa: invalid options for Decrypt") |
| } |
| } |
| |
| type PrecomputedValues struct { |
| Dp, Dq *big.Int // D mod (P-1) (or mod Q-1) |
| Qinv *big.Int // Q^-1 mod P |
| |
| // CRTValues is used for the 3rd and subsequent primes. Due to a |
| // historical accident, the CRT for the first two primes is handled |
| // differently in PKCS #1 and interoperability is sufficiently |
| // important that we mirror this. |
| // |
| // Deprecated: These values are still filled in by Precompute for |
| // backwards compatibility but are not used. Multi-prime RSA is very rare, |
| // and is implemented by this package without CRT optimizations to limit |
| // complexity. |
| CRTValues []CRTValue |
| |
| n, p, q *bigmod.Modulus // moduli for CRT with Montgomery precomputed constants |
| } |
| |
| // CRTValue contains the precomputed Chinese remainder theorem values. |
| type CRTValue struct { |
| Exp *big.Int // D mod (prime-1). |
| Coeff *big.Int // R·Coeff ≡ 1 mod Prime. |
| R *big.Int // product of primes prior to this (inc p and q). |
| } |
| |
| // Validate performs basic sanity checks on the key. |
| // It returns nil if the key is valid, or else an error describing a problem. |
| func (priv *PrivateKey) Validate() error { |
| if err := checkPub(&priv.PublicKey); err != nil { |
| return err |
| } |
| |
| // Check that Πprimes == n. |
| modulus := new(big.Int).Set(bigOne) |
| for _, prime := range priv.Primes { |
| // Any primes ≤ 1 will cause divide-by-zero panics later. |
| if prime.Cmp(bigOne) <= 0 { |
| return errors.New("crypto/rsa: invalid prime value") |
| } |
| modulus.Mul(modulus, prime) |
| } |
| if modulus.Cmp(priv.N) != 0 { |
| return errors.New("crypto/rsa: invalid modulus") |
| } |
| |
| // Check that de ≡ 1 mod p-1, for each prime. |
| // This implies that e is coprime to each p-1 as e has a multiplicative |
| // inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) = |
| // exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1 |
| // mod p. Thus a^de ≡ a mod n for all a coprime to n, as required. |
| congruence := new(big.Int) |
| de := new(big.Int).SetInt64(int64(priv.E)) |
| de.Mul(de, priv.D) |
| for _, prime := range priv.Primes { |
| pminus1 := new(big.Int).Sub(prime, bigOne) |
| congruence.Mod(de, pminus1) |
| if congruence.Cmp(bigOne) != 0 { |
| return errors.New("crypto/rsa: invalid exponents") |
| } |
| } |
| return nil |
| } |
| |
| // GenerateKey generates a random RSA private key of the given bit size. |
| // |
| // Most applications should use [crypto/rand.Reader] as rand. Note that the |
| // returned key does not depend deterministically on the bytes read from rand, |
| // and may change between calls and/or between versions. |
| func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) { |
| return GenerateMultiPrimeKey(random, 2, bits) |
| } |
| |
| // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit |
| // size and the given random source. |
| // |
| // Table 1 in "[On the Security of Multi-prime RSA]" suggests maximum numbers of |
| // primes for a given bit size. |
| // |
| // Although the public keys are compatible (actually, indistinguishable) from |
| // the 2-prime case, the private keys are not. Thus it may not be possible to |
| // export multi-prime private keys in certain formats or to subsequently import |
| // them into other code. |
| // |
| // This package does not implement CRT optimizations for multi-prime RSA, so the |
| // keys with more than two primes will have worse performance. |
| // |
| // Deprecated: The use of this function with a number of primes different from |
| // two is not recommended for the above security, compatibility, and performance |
| // reasons. Use GenerateKey instead. |
| // |
| // [On the Security of Multi-prime RSA]: http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf |
| func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) { |
| randutil.MaybeReadByte(random) |
| |
| if boring.Enabled && random == boring.RandReader && nprimes == 2 && |
| (bits == 2048 || bits == 3072 || bits == 4096) { |
| bN, bE, bD, bP, bQ, bDp, bDq, bQinv, err := boring.GenerateKeyRSA(bits) |
| if err != nil { |
| return nil, err |
| } |
| N := bbig.Dec(bN) |
| E := bbig.Dec(bE) |
| D := bbig.Dec(bD) |
| P := bbig.Dec(bP) |
| Q := bbig.Dec(bQ) |
| Dp := bbig.Dec(bDp) |
| Dq := bbig.Dec(bDq) |
| Qinv := bbig.Dec(bQinv) |
| e64 := E.Int64() |
| if !E.IsInt64() || int64(int(e64)) != e64 { |
| return nil, errors.New("crypto/rsa: generated key exponent too large") |
| } |
| |
| mn, err := bigmod.NewModulusFromBig(N) |
| if err != nil { |
| return nil, err |
| } |
| mp, err := bigmod.NewModulusFromBig(P) |
| if err != nil { |
| return nil, err |
| } |
| mq, err := bigmod.NewModulusFromBig(Q) |
| if err != nil { |
| return nil, err |
| } |
| |
| key := &PrivateKey{ |
| PublicKey: PublicKey{ |
| N: N, |
| E: int(e64), |
| }, |
| D: D, |
| Primes: []*big.Int{P, Q}, |
| Precomputed: PrecomputedValues{ |
| Dp: Dp, |
| Dq: Dq, |
| Qinv: Qinv, |
| CRTValues: make([]CRTValue, 0), // non-nil, to match Precompute |
| n: mn, |
| p: mp, |
| q: mq, |
| }, |
| } |
| return key, nil |
| } |
| |
| priv := new(PrivateKey) |
| priv.E = 65537 |
| |
| if nprimes < 2 { |
| return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2") |
| } |
| |
| if bits < 64 { |
| primeLimit := float64(uint64(1) << uint(bits/nprimes)) |
| // pi approximates the number of primes less than primeLimit |
| pi := primeLimit / (math.Log(primeLimit) - 1) |
| // Generated primes start with 11 (in binary) so we can only |
| // use a quarter of them. |
| pi /= 4 |
| // Use a factor of two to ensure that key generation terminates |
| // in a reasonable amount of time. |
| pi /= 2 |
| if pi <= float64(nprimes) { |
| return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key") |
| } |
| } |
| |
| primes := make([]*big.Int, nprimes) |
| |
| NextSetOfPrimes: |
| for { |
| todo := bits |
| // crypto/rand should set the top two bits in each prime. |
| // Thus each prime has the form |
| // p_i = 2^bitlen(p_i) × 0.11... (in base 2). |
| // And the product is: |
| // P = 2^todo × α |
| // where α is the product of nprimes numbers of the form 0.11... |
| // |
| // If α < 1/2 (which can happen for nprimes > 2), we need to |
| // shift todo to compensate for lost bits: the mean value of 0.11... |
| // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2 |
| // will give good results. |
| if nprimes >= 7 { |
| todo += (nprimes - 2) / 5 |
| } |
| for i := 0; i < nprimes; i++ { |
| var err error |
| primes[i], err = rand.Prime(random, todo/(nprimes-i)) |
| if err != nil { |
| return nil, err |
| } |
| todo -= primes[i].BitLen() |
| } |
| |
| // Make sure that primes is pairwise unequal. |
| for i, prime := range primes { |
| for j := 0; j < i; j++ { |
| if prime.Cmp(primes[j]) == 0 { |
| continue NextSetOfPrimes |
| } |
| } |
| } |
| |
| n := new(big.Int).Set(bigOne) |
| totient := new(big.Int).Set(bigOne) |
| pminus1 := new(big.Int) |
| for _, prime := range primes { |
| n.Mul(n, prime) |
| pminus1.Sub(prime, bigOne) |
| totient.Mul(totient, pminus1) |
| } |
| if n.BitLen() != bits { |
| // This should never happen for nprimes == 2 because |
| // crypto/rand should set the top two bits in each prime. |
| // For nprimes > 2 we hope it does not happen often. |
| continue NextSetOfPrimes |
| } |
| |
| priv.D = new(big.Int) |
| e := big.NewInt(int64(priv.E)) |
| ok := priv.D.ModInverse(e, totient) |
| |
| if ok != nil { |
| priv.Primes = primes |
| priv.N = n |
| break |
| } |
| } |
| |
| priv.Precompute() |
| return priv, nil |
| } |
| |
| // incCounter increments a four byte, big-endian counter. |
| func incCounter(c *[4]byte) { |
| if c[3]++; c[3] != 0 { |
| return |
| } |
| if c[2]++; c[2] != 0 { |
| return |
| } |
| if c[1]++; c[1] != 0 { |
| return |
| } |
| c[0]++ |
| } |
| |
| // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function |
| // specified in PKCS #1 v2.1. |
| func mgf1XOR(out []byte, hash hash.Hash, seed []byte) { |
| var counter [4]byte |
| var digest []byte |
| |
| done := 0 |
| for done < len(out) { |
| hash.Write(seed) |
| hash.Write(counter[0:4]) |
| digest = hash.Sum(digest[:0]) |
| hash.Reset() |
| |
| for i := 0; i < len(digest) && done < len(out); i++ { |
| out[done] ^= digest[i] |
| done++ |
| } |
| incCounter(&counter) |
| } |
| } |
| |
| // ErrMessageTooLong is returned when attempting to encrypt or sign a message |
| // which is too large for the size of the key. When using SignPSS, this can also |
| // be returned if the size of the salt is too large. |
| var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA key size") |
| |
| func encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) { |
| boring.Unreachable() |
| |
| // Most of the CPU time for encryption and verification is spent in this |
| // NewModulusFromBig call, because PublicKey doesn't have a Precomputed |
| // field. If performance becomes an issue, consider placing a private |
| // sync.Once on PublicKey to compute this. |
| N, err := bigmod.NewModulusFromBig(pub.N) |
| if err != nil { |
| return nil, err |
| } |
| m, err := bigmod.NewNat().SetBytes(plaintext, N) |
| if err != nil { |
| return nil, err |
| } |
| e := uint(pub.E) |
| |
| return bigmod.NewNat().ExpShort(m, e, N).Bytes(N), nil |
| } |
| |
| // EncryptOAEP encrypts the given message with RSA-OAEP. |
| // |
| // OAEP is parameterised by a hash function that is used as a random oracle. |
| // Encryption and decryption of a given message must use the same hash function |
| // and sha256.New() is a reasonable choice. |
| // |
| // The random parameter is used as a source of entropy to ensure that |
| // encrypting the same message twice doesn't result in the same ciphertext. |
| // Most applications should use [crypto/rand.Reader] as random. |
| // |
| // The label parameter may contain arbitrary data that will not be encrypted, |
| // but which gives important context to the message. For example, if a given |
| // public key is used to encrypt two types of messages then distinct label |
| // values could be used to ensure that a ciphertext for one purpose cannot be |
| // used for another by an attacker. If not required it can be empty. |
| // |
| // The message must be no longer than the length of the public modulus minus |
| // twice the hash length, minus a further 2. |
| func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) { |
| // Note that while we don't commit to deterministic execution with respect |
| // to the random stream, we also don't apply MaybeReadByte, so per Hyrum's |
| // Law it's probably relied upon by some. It's a tolerable promise because a |
| // well-specified number of random bytes is included in the ciphertext, in a |
| // well-specified way. |
| |
| if err := checkPub(pub); err != nil { |
| return nil, err |
| } |
| hash.Reset() |
| k := pub.Size() |
| if len(msg) > k-2*hash.Size()-2 { |
| return nil, ErrMessageTooLong |
| } |
| |
| if boring.Enabled && random == boring.RandReader { |
| bkey, err := boringPublicKey(pub) |
| if err != nil { |
| return nil, err |
| } |
| return boring.EncryptRSAOAEP(hash, hash, bkey, msg, label) |
| } |
| boring.UnreachableExceptTests() |
| |
| hash.Write(label) |
| lHash := hash.Sum(nil) |
| hash.Reset() |
| |
| em := make([]byte, k) |
| seed := em[1 : 1+hash.Size()] |
| db := em[1+hash.Size():] |
| |
| copy(db[0:hash.Size()], lHash) |
| db[len(db)-len(msg)-1] = 1 |
| copy(db[len(db)-len(msg):], msg) |
| |
| _, err := io.ReadFull(random, seed) |
| if err != nil { |
| return nil, err |
| } |
| |
| mgf1XOR(db, hash, seed) |
| mgf1XOR(seed, hash, db) |
| |
| if boring.Enabled { |
| var bkey *boring.PublicKeyRSA |
| bkey, err = boringPublicKey(pub) |
| if err != nil { |
| return nil, err |
| } |
| return boring.EncryptRSANoPadding(bkey, em) |
| } |
| |
| return encrypt(pub, em) |
| } |
| |
| // ErrDecryption represents a failure to decrypt a message. |
| // It is deliberately vague to avoid adaptive attacks. |
| var ErrDecryption = errors.New("crypto/rsa: decryption error") |
| |
| // ErrVerification represents a failure to verify a signature. |
| // It is deliberately vague to avoid adaptive attacks. |
| var ErrVerification = errors.New("crypto/rsa: verification error") |
| |
| // Precompute performs some calculations that speed up private key operations |
| // in the future. |
| func (priv *PrivateKey) Precompute() { |
| if priv.Precomputed.n == nil && len(priv.Primes) == 2 { |
| // Precomputed values _should_ always be valid, but if they aren't |
| // just return. We could also panic. |
| var err error |
| priv.Precomputed.n, err = bigmod.NewModulusFromBig(priv.N) |
| if err != nil { |
| return |
| } |
| priv.Precomputed.p, err = bigmod.NewModulusFromBig(priv.Primes[0]) |
| if err != nil { |
| // Unset previous values, so we either have everything or nothing |
| priv.Precomputed.n = nil |
| return |
| } |
| priv.Precomputed.q, err = bigmod.NewModulusFromBig(priv.Primes[1]) |
| if err != nil { |
| // Unset previous values, so we either have everything or nothing |
| priv.Precomputed.n, priv.Precomputed.p = nil, nil |
| return |
| } |
| } |
| |
| // Fill in the backwards-compatibility *big.Int values. |
| if priv.Precomputed.Dp != nil { |
| return |
| } |
| |
| priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne) |
| priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp) |
| |
| priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne) |
| priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq) |
| |
| priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0]) |
| |
| r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1]) |
| priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2) |
| for i := 2; i < len(priv.Primes); i++ { |
| prime := priv.Primes[i] |
| values := &priv.Precomputed.CRTValues[i-2] |
| |
| values.Exp = new(big.Int).Sub(prime, bigOne) |
| values.Exp.Mod(priv.D, values.Exp) |
| |
| values.R = new(big.Int).Set(r) |
| values.Coeff = new(big.Int).ModInverse(r, prime) |
| |
| r.Mul(r, prime) |
| } |
| } |
| |
| const withCheck = true |
| const noCheck = false |
| |
| // decrypt performs an RSA decryption of ciphertext into out. If check is true, |
| // m^e is calculated and compared with ciphertext, in order to defend against |
| // errors in the CRT computation. |
| func decrypt(priv *PrivateKey, ciphertext []byte, check bool) ([]byte, error) { |
| if len(priv.Primes) <= 2 { |
| boring.Unreachable() |
| } |
| |
| var ( |
| err error |
| m, c *bigmod.Nat |
| N *bigmod.Modulus |
| t0 = bigmod.NewNat() |
| ) |
| if priv.Precomputed.n == nil { |
| N, err = bigmod.NewModulusFromBig(priv.N) |
| if err != nil { |
| return nil, ErrDecryption |
| } |
| c, err = bigmod.NewNat().SetBytes(ciphertext, N) |
| if err != nil { |
| return nil, ErrDecryption |
| } |
| m = bigmod.NewNat().Exp(c, priv.D.Bytes(), N) |
| } else { |
| N = priv.Precomputed.n |
| P, Q := priv.Precomputed.p, priv.Precomputed.q |
| Qinv, err := bigmod.NewNat().SetBytes(priv.Precomputed.Qinv.Bytes(), P) |
| if err != nil { |
| return nil, ErrDecryption |
| } |
| c, err = bigmod.NewNat().SetBytes(ciphertext, N) |
| if err != nil { |
| return nil, ErrDecryption |
| } |
| |
| // m = c ^ Dp mod p |
| m = bigmod.NewNat().Exp(t0.Mod(c, P), priv.Precomputed.Dp.Bytes(), P) |
| // m2 = c ^ Dq mod q |
| m2 := bigmod.NewNat().Exp(t0.Mod(c, Q), priv.Precomputed.Dq.Bytes(), Q) |
| // m = m - m2 mod p |
| m.Sub(t0.Mod(m2, P), P) |
| // m = m * Qinv mod p |
| m.Mul(Qinv, P) |
| // m = m * q mod N |
| m.ExpandFor(N).Mul(t0.Mod(Q.Nat(), N), N) |
| // m = m + m2 mod N |
| m.Add(m2.ExpandFor(N), N) |
| } |
| |
| if check { |
| c1 := bigmod.NewNat().ExpShort(m, uint(priv.E), N) |
| if c1.Equal(c) != 1 { |
| return nil, ErrDecryption |
| } |
| } |
| |
| return m.Bytes(N), nil |
| } |
| |
| // DecryptOAEP decrypts ciphertext using RSA-OAEP. |
| // |
| // OAEP is parameterised by a hash function that is used as a random oracle. |
| // Encryption and decryption of a given message must use the same hash function |
| // and sha256.New() is a reasonable choice. |
| // |
| // The random parameter is legacy and ignored, and it can be nil. |
| // |
| // The label parameter must match the value given when encrypting. See |
| // EncryptOAEP for details. |
| func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) { |
| return decryptOAEP(hash, hash, random, priv, ciphertext, label) |
| } |
| |
| func decryptOAEP(hash, mgfHash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) { |
| if err := checkPub(&priv.PublicKey); err != nil { |
| return nil, err |
| } |
| k := priv.Size() |
| if len(ciphertext) > k || |
| k < hash.Size()*2+2 { |
| return nil, ErrDecryption |
| } |
| |
| if boring.Enabled { |
| bkey, err := boringPrivateKey(priv) |
| if err != nil { |
| return nil, err |
| } |
| out, err := boring.DecryptRSAOAEP(hash, mgfHash, bkey, ciphertext, label) |
| if err != nil { |
| return nil, ErrDecryption |
| } |
| return out, nil |
| } |
| |
| em, err := decrypt(priv, ciphertext, noCheck) |
| if err != nil { |
| return nil, err |
| } |
| |
| hash.Write(label) |
| lHash := hash.Sum(nil) |
| hash.Reset() |
| |
| firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0) |
| |
| seed := em[1 : hash.Size()+1] |
| db := em[hash.Size()+1:] |
| |
| mgf1XOR(seed, mgfHash, db) |
| mgf1XOR(db, mgfHash, seed) |
| |
| lHash2 := db[0:hash.Size()] |
| |
| // We have to validate the plaintext in constant time in order to avoid |
| // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal |
| // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 |
| // v2.0. In J. Kilian, editor, Advances in Cryptology. |
| lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2) |
| |
| // The remainder of the plaintext must be zero or more 0x00, followed |
| // by 0x01, followed by the message. |
| // lookingForIndex: 1 iff we are still looking for the 0x01 |
| // index: the offset of the first 0x01 byte |
| // invalid: 1 iff we saw a non-zero byte before the 0x01. |
| var lookingForIndex, index, invalid int |
| lookingForIndex = 1 |
| rest := db[hash.Size():] |
| |
| for i := 0; i < len(rest); i++ { |
| equals0 := subtle.ConstantTimeByteEq(rest[i], 0) |
| equals1 := subtle.ConstantTimeByteEq(rest[i], 1) |
| index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index) |
| lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex) |
| invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid) |
| } |
| |
| if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 { |
| return nil, ErrDecryption |
| } |
| |
| return rest[index+1:], nil |
| } |