// 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. // // The value of the modulus N is considered secret by this library and protected // from leaking through timing side-channels. However, neither the value of the // exponent E nor the precise bit size of N are similarly protected. 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() 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().ExpShortVarTime(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().ExpShortVarTime(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 }