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

View as plain text