// 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 ( ) 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 ( *PublicKey) () int { return (.N.BitLen() + 7) / 8 } // Equal reports whether pub and x have the same value. func ( *PublicKey) ( crypto.PublicKey) bool { , := .(*PublicKey) if ! { return false } return .N.Cmp(.N) == 0 && .E == .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( *PublicKey) error { if .N == nil { return errPublicModulus } if .E < 2 { return errPublicExponentSmall } if .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 ( *PrivateKey) () crypto.PublicKey { return &.PublicKey } // Equal reports whether priv and x have equivalent values. It ignores // Precomputed values. func ( *PrivateKey) ( crypto.PrivateKey) bool { , := .(*PrivateKey) if ! { return false } if !.PublicKey.Equal(&.PublicKey) || .D.Cmp(.D) != 0 { return false } if len(.Primes) != len(.Primes) { return false } for := range .Primes { if .Primes[].Cmp(.Primes[]) != 0 { return false } } return true } // 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 ( *PrivateKey) ( io.Reader, []byte, crypto.SignerOpts) ([]byte, error) { if , := .(*PSSOptions); { return SignPSS(, , .Hash, , ) } return SignPKCS1v15(, , .HashFunc(), ) } // 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 ( *PrivateKey) ( io.Reader, []byte, crypto.DecrypterOpts) ( []byte, error) { if == nil { return DecryptPKCS1v15(, , ) } switch opts := .(type) { case *OAEPOptions: if .MGFHash == 0 { return decryptOAEP(.Hash.New(), .Hash.New(), , , , .Label) } else { return decryptOAEP(.Hash.New(), .MGFHash.New(), , , , .Label) } case *PKCS1v15DecryptOptions: if := .SessionKeyLen; > 0 { = make([]byte, ) if , := io.ReadFull(, ); != nil { return nil, } if := DecryptPKCS1v15SessionKey(, , , ); != nil { return nil, } return , nil } else { return DecryptPKCS1v15(, , ) } 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. // // Note: 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 ( *PrivateKey) () error { if := checkPub(&.PublicKey); != nil { return } // Check that Πprimes == n. := new(big.Int).Set(bigOne) for , := range .Primes { // Any primes ≤ 1 will cause divide-by-zero panics later. if .Cmp(bigOne) <= 0 { return errors.New("crypto/rsa: invalid prime value") } .Mul(, ) } if .Cmp(.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. := new(big.Int) := new(big.Int).SetInt64(int64(.E)) .Mul(, .D) for , := range .Primes { := new(big.Int).Sub(, bigOne) .Mod(, ) if .Cmp(bigOne) != 0 { return errors.New("crypto/rsa: invalid exponents") } } return nil } // GenerateKey generates an RSA keypair of the given bit size using the // random source random (for example, crypto/rand.Reader). func ( io.Reader, int) (*PrivateKey, error) { return GenerateMultiPrimeKey(, 2, ) } // 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. // // Note: 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 ( io.Reader, int, int) (*PrivateKey, error) { randutil.MaybeReadByte() if boring.Enabled && == boring.RandReader && == 2 && ( == 2048 || == 3072) { , , , , , , , , := boring.GenerateKeyRSA() if != nil { return nil, } := bbig.Dec() := bbig.Dec() := bbig.Dec() := bbig.Dec() := bbig.Dec() := bbig.Dec() := bbig.Dec() := bbig.Dec() := .Int64() if !.IsInt64() || int64(int()) != { return nil, errors.New("crypto/rsa: generated key exponent too large") } := &PrivateKey{ PublicKey: PublicKey{ N: , E: int(), }, D: , Primes: []*big.Int{, }, Precomputed: PrecomputedValues{ Dp: , Dq: , Qinv: , CRTValues: make([]CRTValue, 0), // non-nil, to match Precompute n: bigmod.NewModulusFromBig(), p: bigmod.NewModulusFromBig(), q: bigmod.NewModulusFromBig(), }, } return , nil } := new(PrivateKey) .E = 65537 if < 2 { return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2") } if < 64 { := float64(uint64(1) << uint(/)) // pi approximates the number of primes less than primeLimit := / (math.Log() - 1) // Generated primes start with 11 (in binary) so we can only // use a quarter of them. /= 4 // Use a factor of two to ensure that key generation terminates // in a reasonable amount of time. /= 2 if <= float64() { return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key") } } := make([]*big.Int, ) : for { := // 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 >= 7 { += ( - 2) / 5 } for := 0; < ; ++ { var error [], = rand.Prime(, /(-)) if != nil { return nil, } -= [].BitLen() } // Make sure that primes is pairwise unequal. for , := range { for := 0; < ; ++ { if .Cmp([]) == 0 { continue } } } := new(big.Int).Set(bigOne) := new(big.Int).Set(bigOne) := new(big.Int) for , := range { .Mul(, ) .Sub(, bigOne) .Mul(, ) } if .BitLen() != { // 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 } .D = new(big.Int) := big.NewInt(int64(.E)) := .D.ModInverse(, ) if != nil { .Primes = .N = break } } .Precompute() return , nil } // incCounter increments a four byte, big-endian counter. func incCounter( *[4]byte) { if [3]++; [3] != 0 { return } if [2]++; [2] != 0 { return } if [1]++; [1] != 0 { return } [0]++ } // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function // specified in PKCS #1 v2.1. func mgf1XOR( []byte, hash.Hash, []byte) { var [4]byte var []byte := 0 for < len() { .Write() .Write([0:4]) = .Sum([:0]) .Reset() for := 0; < len() && < len(); ++ { [] ^= [] ++ } incCounter(&) } } // 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( *PublicKey, []byte) ([]byte, error) { boring.Unreachable() := bigmod.NewModulusFromBig(.N) , := bigmod.NewNat().SetBytes(, ) if != nil { return nil, } := intToBytes(.E) return bigmod.NewNat().Exp(, , ).Bytes(), nil } // intToBytes returns i as a big-endian slice of bytes with no leading zeroes, // leaking only the bit size of i through timing side-channels. func intToBytes( int) []byte { := make([]byte, 8) binary.BigEndian.PutUint64(, uint64()) for len() > 1 && [0] == 0 { = [1:] } return } // 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. // // 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 ( hash.Hash, io.Reader, *PublicKey, []byte, []byte) ([]byte, error) { if := checkPub(); != nil { return nil, } .Reset() := .Size() if len() > -2*.Size()-2 { return nil, ErrMessageTooLong } if boring.Enabled && == boring.RandReader { , := boringPublicKey() if != nil { return nil, } return boring.EncryptRSAOAEP(, , , , ) } boring.UnreachableExceptTests() .Write() := .Sum(nil) .Reset() := make([]byte, ) := [1 : 1+.Size()] := [1+.Size():] copy([0:.Size()], ) [len()-len()-1] = 1 copy([len()-len():], ) , := io.ReadFull(, ) if != nil { return nil, } mgf1XOR(, , ) mgf1XOR(, , ) if boring.Enabled { var *boring.PublicKeyRSA , = boringPublicKey() if != nil { return nil, } return boring.EncryptRSANoPadding(, ) } return encrypt(, ) } // 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 ( *PrivateKey) () { if .Precomputed.n == nil && len(.Primes) == 2 { .Precomputed.n = bigmod.NewModulusFromBig(.N) .Precomputed.p = bigmod.NewModulusFromBig(.Primes[0]) .Precomputed.q = bigmod.NewModulusFromBig(.Primes[1]) } // Fill in the backwards-compatibility *big.Int values. if .Precomputed.Dp != nil { return } .Precomputed.Dp = new(big.Int).Sub(.Primes[0], bigOne) .Precomputed.Dp.Mod(.D, .Precomputed.Dp) .Precomputed.Dq = new(big.Int).Sub(.Primes[1], bigOne) .Precomputed.Dq.Mod(.D, .Precomputed.Dq) .Precomputed.Qinv = new(big.Int).ModInverse(.Primes[1], .Primes[0]) := new(big.Int).Mul(.Primes[0], .Primes[1]) .Precomputed.CRTValues = make([]CRTValue, len(.Primes)-2) for := 2; < len(.Primes); ++ { := .Primes[] := &.Precomputed.CRTValues[-2] .Exp = new(big.Int).Sub(, bigOne) .Exp.Mod(.D, .Exp) .R = new(big.Int).Set() .Coeff = new(big.Int).ModInverse(, ) .Mul(, ) } } 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( *PrivateKey, []byte, bool) ([]byte, error) { if len(.Primes) <= 2 { boring.Unreachable() } var ( error , *bigmod.Nat *bigmod.Modulus = bigmod.NewNat() ) if .Precomputed.n == nil { = bigmod.NewModulusFromBig(.N) , = bigmod.NewNat().SetBytes(, ) if != nil { return nil, ErrDecryption } = bigmod.NewNat().Exp(, .D.Bytes(), ) } else { = .Precomputed.n , := .Precomputed.p, .Precomputed.q , := bigmod.NewNat().SetBytes(.Precomputed.Qinv.Bytes(), ) if != nil { return nil, ErrDecryption } , = bigmod.NewNat().SetBytes(, ) if != nil { return nil, ErrDecryption } // m = c ^ Dp mod p = bigmod.NewNat().Exp(.Mod(, ), .Precomputed.Dp.Bytes(), ) // m2 = c ^ Dq mod q := bigmod.NewNat().Exp(.Mod(, ), .Precomputed.Dq.Bytes(), ) // m = m - m2 mod p .Sub(.Mod(, ), ) // m = m * Qinv mod p .Mul(, ) // m = m * q mod N .ExpandFor().Mul(.Mod(.Nat(), ), ) // m = m + m2 mod N .Add(.ExpandFor(), ) } if { := bigmod.NewNat().Exp(, intToBytes(.E), ) if .Equal() != 1 { return nil, ErrDecryption } } return .Bytes(), 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 as nil. // // The label parameter must match the value given when encrypting. See // EncryptOAEP for details. func ( hash.Hash, io.Reader, *PrivateKey, []byte, []byte) ([]byte, error) { return decryptOAEP(, , , , , ) } func decryptOAEP(, hash.Hash, io.Reader, *PrivateKey, []byte, []byte) ([]byte, error) { if := checkPub(&.PublicKey); != nil { return nil, } := .Size() if len() > || < .Size()*2+2 { return nil, ErrDecryption } if boring.Enabled { , := boringPrivateKey() if != nil { return nil, } , := boring.DecryptRSAOAEP(, , , , ) if != nil { return nil, ErrDecryption } return , nil } , := decrypt(, , noCheck) if != nil { return nil, } .Write() := .Sum(nil) .Reset() := subtle.ConstantTimeByteEq([0], 0) := [1 : .Size()+1] := [.Size()+1:] mgf1XOR(, , ) mgf1XOR(, , ) := [0:.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. := subtle.ConstantTimeCompare(, ) // 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 , , int = 1 := [.Size():] for := 0; < len(); ++ { := subtle.ConstantTimeByteEq([], 0) := subtle.ConstantTimeByteEq([], 1) = subtle.ConstantTimeSelect(&, , ) = subtle.ConstantTimeSelect(, 0, ) = subtle.ConstantTimeSelect(&^, 1, ) } if &&^&^ != 1 { return nil, ErrDecryption } return [+1:], nil }