...
Run Format

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

View as plain text