// 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. // // The RSA operations in this package are not implemented using constant-time algorithms.
package rsa import ( ) var bigZero = big.NewInt(0) 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 // 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 private // operations, if available. 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: return DecryptOAEP(.Hash.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. CRTValues []CRTValue } // 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, as suggested in [1]. 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. // // Table 1 in [2] suggests maximum numbers of primes for a given size. // // [1] US patent 4405829 (1972, expired) // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf func ( io.Reader, int, int) (*PrivateKey, error) { randutil.MaybeReadByte() := 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 a message which is // too large for the size of the public key. var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size") func encrypt( *big.Int, *PublicKey, *big.Int) *big.Int { := big.NewInt(int64(.E)) .Exp(, , .N) 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 decrypt 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 } .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(, , ) := new(big.Int) .SetBytes() := encrypt(new(big.Int), , ) := make([]byte, ) return .FillBytes(), nil } // 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.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(, ) } } // decrypt performs an RSA decryption, resulting in a plaintext integer. If a // random source is given, RSA blinding is used. func decrypt( io.Reader, *PrivateKey, *big.Int) ( *big.Int, error) { // TODO(agl): can we get away with reusing blinds? if .Cmp(.N) > 0 { = ErrDecryption return } if .N.Sign() == 0 { return nil, ErrDecryption } var *big.Int if != nil { randutil.MaybeReadByte() // Blinding enabled. Blinding involves multiplying c by r^e. // Then the decryption operation performs (m^e * r^e)^d mod n // which equals mr mod n. The factor of r can then be removed // by multiplying by the multiplicative inverse of r. var *big.Int = new(big.Int) for { , = rand.Int(, .N) if != nil { return } if .Cmp(bigZero) == 0 { = bigOne } := .ModInverse(, .N) if != nil { break } } := big.NewInt(int64(.E)) := new(big.Int).Exp(, , .N) // N != 0 := new(big.Int).Set() .Mul(, ) .Mod(, .N) = } if .Precomputed.Dp == nil { = new(big.Int).Exp(, .D, .N) } else { // We have the precalculated values needed for the CRT. = new(big.Int).Exp(, .Precomputed.Dp, .Primes[0]) := new(big.Int).Exp(, .Precomputed.Dq, .Primes[1]) .Sub(, ) if .Sign() < 0 { .Add(, .Primes[0]) } .Mul(, .Precomputed.Qinv) .Mod(, .Primes[0]) .Mul(, .Primes[1]) .Add(, ) for , := range .Precomputed.CRTValues { := .Primes[2+] .Exp(, .Exp, ) .Sub(, ) .Mul(, .Coeff) .Mod(, ) if .Sign() < 0 { .Add(, ) } .Mul(, .R) .Add(, ) } } if != nil { // Unblind. .Mul(, ) .Mod(, .N) } return } func decryptAndCheck( io.Reader, *PrivateKey, *big.Int) ( *big.Int, error) { , = decrypt(, , ) if != nil { return nil, } // In order to defend against errors in the CRT computation, m^e is // calculated, which should match the original ciphertext. := encrypt(new(big.Int), &.PublicKey, ) if .Cmp() != 0 { return nil, errors.New("rsa: internal error") } return , 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, if not nil, is used to blind the private-key operation // and avoid timing side-channel attacks. Blinding is purely internal to this // function – the random data need not match that used when encrypting. // // The label parameter must match the value given when encrypting. See // EncryptOAEP for details. func ( hash.Hash, io.Reader, *PrivateKey, []byte, []byte) ([]byte, error) { if := checkPub(&.PublicKey); != nil { return nil, } := .Size() if len() > || < .Size()*2+2 { return nil, ErrDecryption } := new(big.Int).SetBytes() , := decrypt(, , ) if != nil { return nil, } .Write() := .Sum(nil) .Reset() // We probably leak the number of leading zeros. // It's not clear that we can do anything about this. := .FillBytes(make([]byte, )) := 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 }