Run Format

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

View as plain text