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

View as plain text