keygen.go

Documentation: crypto/internal/fips140/rsa

     1  // Copyright 2024 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
     6  
     7  import (
     8  	"crypto/internal/fips140"
     9  	"crypto/internal/fips140/bigmod"
    10  	"crypto/internal/fips140/drbg"
    11  	"errors"
    12  	"io"
    13  )
    14  
    15  // GenerateKey generates a new RSA key pair of the given bit size.
    16  // bits must be at least 32.
    17  func GenerateKey(rand io.Reader, bits int) (*PrivateKey, error) {
    18  	if bits < 32 {
    19  		return nil, errors.New("rsa: key too small")
    20  	}
    21  	fips140.RecordApproved()
    22  	if bits < 2048 || bits%2 == 1 {
    23  		fips140.RecordNonApproved()
    24  	}
    25  
    26  	for {
    27  		p, err := randomPrime(rand, (bits+1)/2)
    28  		if err != nil {
    29  			return nil, err
    30  		}
    31  		q, err := randomPrime(rand, bits/2)
    32  		if err != nil {
    33  			return nil, err
    34  		}
    35  
    36  		P, err := bigmod.NewModulus(p)
    37  		if err != nil {
    38  			return nil, err
    39  		}
    40  		Q, err := bigmod.NewModulus(q)
    41  		if err != nil {
    42  			return nil, err
    43  		}
    44  
    45  		if Q.Nat().ExpandFor(P).Equal(P.Nat()) == 1 {
    46  			return nil, errors.New("rsa: generated p == q, random source is broken")
    47  		}
    48  
    49  		N, err := bigmod.NewModulusProduct(p, q)
    50  		if err != nil {
    51  			return nil, err
    52  		}
    53  		if N.BitLen() != bits {
    54  			return nil, errors.New("rsa: internal error: modulus size incorrect")
    55  		}
    56  
    57  		// d can be safely computed as e⁻¹ mod φ(N) where φ(N) = (p-1)(q-1), and
    58  		// indeed that's what both the original RSA paper and the pre-FIPS
    59  		// crypto/rsa implementation did.
    60  		//
    61  		// However, FIPS 186-5, A.1.1(3) requires computing it as e⁻¹ mod λ(N)
    62  		// where λ(N) = lcm(p-1, q-1).
    63  		//
    64  		// This makes d smaller by 1.5 bits on average, which is irrelevant both
    65  		// because we exclusively use the CRT for private operations and because
    66  		// we use constant time windowed exponentiation. On the other hand, it
    67  		// requires computing a GCD of two values that are not coprime, and then
    68  		// a division, both complex variable-time operations.
    69  		λ, err := totient(P, Q)
    70  		if err == errDivisorTooLarge {
    71  			// The divisor is too large, try again with different primes.
    72  			continue
    73  		}
    74  		if err != nil {
    75  			return nil, err
    76  		}
    77  
    78  		e := bigmod.NewNat().SetUint(65537)
    79  		d, ok := bigmod.NewNat().InverseVarTime(e, λ)
    80  		if !ok {
    81  			// This checks that GCD(e, lcm(p-1, q-1)) = 1, which is equivalent
    82  			// to checking GCD(e, p-1) = 1 and GCD(e, q-1) = 1 separately in
    83  			// FIPS 186-5, Appendix A.1.3, steps 4.5 and 5.6.
    84  			//
    85  			// We waste a prime by retrying the whole process, since 65537 is
    86  			// probably only a factor of one of p-1 or q-1, but the probability
    87  			// of this check failing is only 1/65537, so it doesn't matter.
    88  			continue
    89  		}
    90  
    91  		if e.ExpandFor(λ).Mul(d, λ).IsOne() == 0 {
    92  			return nil, errors.New("rsa: internal error: e*d != 1 mod λ(N)")
    93  		}
    94  
    95  		// FIPS 186-5, A.1.1(3) requires checking that d > 2^(nlen / 2).
    96  		//
    97  		// The probability of this check failing when d is derived from
    98  		// (e, p, q) is roughly
    99  		//
   100  		//   2^(nlen/2) / 2^nlen = 2^(-nlen/2)
   101  		//
   102  		// so less than 2⁻¹²⁸ for keys larger than 256 bits.
   103  		//
   104  		// We still need to check to comply with FIPS 186-5, but knowing it has
   105  		// negligible chance of failure we can defer the check to the end of key
   106  		// generation and return an error if it fails. See [checkPrivateKey].
   107  
   108  		k, err := newPrivateKey(N, 65537, d, P, Q)
   109  		if err != nil {
   110  			return nil, err
   111  		}
   112  
   113  		if k.fipsApproved {
   114  			fips140.PCT("RSA sign and verify PCT", func() error {
   115  				hash := []byte{
   116  					0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
   117  					0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10,
   118  					0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
   119  					0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
   120  				}
   121  				sig, err := signPKCS1v15(k, "SHA-256", hash)
   122  				if err != nil {
   123  					return err
   124  				}
   125  				return verifyPKCS1v15(k.PublicKey(), "SHA-256", hash, sig)
   126  			})
   127  		}
   128  
   129  		return k, nil
   130  	}
   131  }
   132  
   133  // errDivisorTooLarge is returned by [totient] when gcd(p-1, q-1) is too large.
   134  var errDivisorTooLarge = errors.New("divisor too large")
   135  
   136  // totient computes the Carmichael totient function λ(N) = lcm(p-1, q-1).
   137  func totient(p, q *bigmod.Modulus) (*bigmod.Modulus, error) {
   138  	a, b := p.Nat().SubOne(p), q.Nat().SubOne(q)
   139  
   140  	// lcm(a, b) = a×b / gcd(a, b) = a × (b / gcd(a, b))
   141  
   142  	// Our GCD requires at least one of the numbers to be odd. For LCM we only
   143  	// need to preserve the larger prime power of each prime factor, so we can
   144  	// right-shift the number with the fewest trailing zeros until it's odd.
   145  	// For odd a, b and m >= n, lcm(a×2ᵐ, b×2ⁿ) = lcm(a×2ᵐ, b).
   146  	az, bz := a.TrailingZeroBitsVarTime(), b.TrailingZeroBitsVarTime()
   147  	if az < bz {
   148  		a = a.ShiftRightVarTime(az)
   149  	} else {
   150  		b = b.ShiftRightVarTime(bz)
   151  	}
   152  
   153  	gcd, err := bigmod.NewNat().GCDVarTime(a, b)
   154  	if err != nil {
   155  		return nil, err
   156  	}
   157  	if gcd.IsOdd() == 0 {
   158  		return nil, errors.New("rsa: internal error: gcd(a, b) is even")
   159  	}
   160  
   161  	// To avoid implementing multiple-precision division, we just try again if
   162  	// the divisor doesn't fit in a single word. This would have a chance of
   163  	// 2⁻⁶⁴ on 64-bit platforms, and 2⁻³² on 32-bit platforms, but testing 2⁻⁶⁴
   164  	// edge cases is impractical, and we'd rather not behave differently on
   165  	// different platforms, so we reject divisors above 2³²-1.
   166  	if gcd.BitLenVarTime() > 32 {
   167  		return nil, errDivisorTooLarge
   168  	}
   169  	if gcd.IsZero() == 1 || gcd.Bits()[0] == 0 {
   170  		return nil, errors.New("rsa: internal error: gcd(a, b) is zero")
   171  	}
   172  	if rem := b.DivShortVarTime(gcd.Bits()[0]); rem != 0 {
   173  		return nil, errors.New("rsa: internal error: b is not divisible by gcd(a, b)")
   174  	}
   175  
   176  	return bigmod.NewModulusProduct(a.Bytes(p), b.Bytes(q))
   177  }
   178  
   179  // randomPrime returns a random prime number of the given bit size following
   180  // the process in FIPS 186-5, Appendix A.1.3.
   181  func randomPrime(rand io.Reader, bits int) ([]byte, error) {
   182  	if bits < 16 {
   183  		return nil, errors.New("rsa: prime size must be at least 16 bits")
   184  	}
   185  
   186  	b := make([]byte, (bits+7)/8)
   187  	for {
   188  		if err := drbg.ReadWithReader(rand, b); err != nil {
   189  			return nil, err
   190  		}
   191  		if excess := len(b)*8 - bits; excess != 0 {
   192  			b[0] >>= excess
   193  		}
   194  
   195  		// Don't let the value be too small: set the most significant two bits.
   196  		// Setting the top two bits, rather than just the top bit, means that
   197  		// when two of these values are multiplied together, the result isn't
   198  		// ever one bit short.
   199  		if excess := len(b)*8 - bits; excess < 7 {
   200  			b[0] |= 0b1100_0000 >> excess
   201  		} else {
   202  			b[0] |= 0b0000_0001
   203  			b[1] |= 0b1000_0000
   204  		}
   205  
   206  		// Make the value odd since an even number certainly isn't prime.
   207  		b[len(b)-1] |= 1
   208  
   209  		// We don't need to check for p >= √2 × 2^(bits-1) (steps 4.4 and 5.4)
   210  		// because we set the top two bits above, so
   211  		//
   212  		//   p > 2^(bits-1) + 2^(bits-2) = 3⁄2 × 2^(bits-1) > √2 × 2^(bits-1)
   213  		//
   214  
   215  		// Step 5.5 requires checking that |p - q| > 2^(nlen/2 - 100).
   216  		//
   217  		// The probability of |p - q| ≤ k where p and q are uniformly random in
   218  		// the range (a, b) is 1 - (b-a-k)^2 / (b-a)^2, so the probability of
   219  		// this check failing during key generation is 2⁻⁹⁷.
   220  		//
   221  		// We still need to check to comply with FIPS 186-5, but knowing it has
   222  		// negligible chance of failure we can defer the check to the end of key
   223  		// generation and return an error if it fails. See [checkPrivateKey].
   224  
   225  		if isPrime(b) {
   226  			return b, nil
   227  		}
   228  	}
   229  }
   230  
   231  // isPrime runs the Miller-Rabin Probabilistic Primality Test from
   232  // FIPS 186-5, Appendix B.3.1.
   233  //
   234  // w must be a random odd integer greater than three in big-endian order.
   235  // isPrime might return false positives for adversarially chosen values.
   236  //
   237  // isPrime is not constant-time.
   238  func isPrime(w []byte) bool {
   239  	mr, err := millerRabinSetup(w)
   240  	if err != nil {
   241  		// w is zero, one, or even.
   242  		return false
   243  	}
   244  
   245  	primes, err := bigmod.NewNat().SetBytes(productOfPrimes, mr.w)
   246  	// If w is too small for productOfPrimes, key generation is
   247  	// going to be fast enough anyway.
   248  	if err == nil {
   249  		_, hasInverse := primes.InverseVarTime(primes, mr.w)
   250  		if !hasInverse {
   251  			// productOfPrimes doesn't have an inverse mod w,
   252  			// so w is divisible by at least one of the primes.
   253  			return false
   254  		}
   255  	}
   256  
   257  	// iterations is the number of Miller-Rabin rounds, each with a
   258  	// randomly-selected base.
   259  	//
   260  	// The worst case false positive rate for a single iteration is 1/4 per
   261  	// https://eprint.iacr.org/2018/749, so if w were selected adversarially, we
   262  	// would need up to 64 iterations to get to a negligible (2⁻¹²⁸) chance of
   263  	// false positive.
   264  	//
   265  	// However, since this function is only used for randomly-selected w in the
   266  	// context of RSA key generation, we can use a smaller number of iterations.
   267  	// The exact number depends on the size of the prime (and the implied
   268  	// security level). See BoringSSL for the full formula.
   269  	// https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/prime.c.inc;l=208-283;drc=3a138e43
   270  	bits := mr.w.BitLen()
   271  	var iterations int
   272  	switch {
   273  	case bits >= 3747:
   274  		iterations = 3
   275  	case bits >= 1345:
   276  		iterations = 4
   277  	case bits >= 476:
   278  		iterations = 5
   279  	case bits >= 400:
   280  		iterations = 6
   281  	case bits >= 347:
   282  		iterations = 7
   283  	case bits >= 308:
   284  		iterations = 8
   285  	case bits >= 55:
   286  		iterations = 27
   287  	default:
   288  		iterations = 34
   289  	}
   290  
   291  	b := make([]byte, (bits+7)/8)
   292  	for {
   293  		drbg.Read(b)
   294  		if excess := len(b)*8 - bits; excess != 0 {
   295  			b[0] >>= excess
   296  		}
   297  		result, err := millerRabinIteration(mr, b)
   298  		if err != nil {
   299  			// b was rejected.
   300  			continue
   301  		}
   302  		if result == millerRabinCOMPOSITE {
   303  			return false
   304  		}
   305  		iterations--
   306  		if iterations == 0 {
   307  			return true
   308  		}
   309  	}
   310  }
   311  
   312  // productOfPrimes is the product of the first 74 primes higher than 2.
   313  //
   314  // The number of primes was selected to be the highest such that the product fit
   315  // in 512 bits, so to be usable for 1024 bit RSA keys.
   316  //
   317  // Higher values cause fewer Miller-Rabin tests of composites (nothing can help
   318  // with the final test on the actual prime) but make InverseVarTime take longer.
   319  var productOfPrimes = []byte{
   320  	0x10, 0x6a, 0xa9, 0xfb, 0x76, 0x46, 0xfa, 0x6e, 0xb0, 0x81, 0x3c, 0x28, 0xc5, 0xd5, 0xf0, 0x9f,
   321  	0x07, 0x7e, 0xc3, 0xba, 0x23, 0x8b, 0xfb, 0x99, 0xc1, 0xb6, 0x31, 0xa2, 0x03, 0xe8, 0x11, 0x87,
   322  	0x23, 0x3d, 0xb1, 0x17, 0xcb, 0xc3, 0x84, 0x05, 0x6e, 0xf0, 0x46, 0x59, 0xa4, 0xa1, 0x1d, 0xe4,
   323  	0x9f, 0x7e, 0xcb, 0x29, 0xba, 0xda, 0x8f, 0x98, 0x0d, 0xec, 0xec, 0xe9, 0x2e, 0x30, 0xc4, 0x8f,
   324  }
   325  
   326  type millerRabin struct {
   327  	w *bigmod.Modulus
   328  	a uint
   329  	m []byte
   330  }
   331  
   332  // millerRabinSetup prepares state that's reused across multiple iterations of
   333  // the Miller-Rabin test.
   334  func millerRabinSetup(w []byte) (*millerRabin, error) {
   335  	mr := &millerRabin{}
   336  
   337  	// Check that w is odd, and precompute Montgomery parameters.
   338  	wm, err := bigmod.NewModulus(w)
   339  	if err != nil {
   340  		return nil, err
   341  	}
   342  	if wm.Nat().IsOdd() == 0 {
   343  		return nil, errors.New("candidate is even")
   344  	}
   345  	mr.w = wm
   346  
   347  	// Compute m = (w-1)/2^a, where m is odd.
   348  	wMinus1 := mr.w.Nat().SubOne(mr.w)
   349  	if wMinus1.IsZero() == 1 {
   350  		return nil, errors.New("candidate is one")
   351  	}
   352  	mr.a = wMinus1.TrailingZeroBitsVarTime()
   353  
   354  	// Store mr.m as a big-endian byte slice with leading zero bytes removed,
   355  	// for use with [bigmod.Nat.Exp].
   356  	m := wMinus1.ShiftRightVarTime(mr.a)
   357  	mr.m = m.Bytes(mr.w)
   358  	for mr.m[0] == 0 {
   359  		mr.m = mr.m[1:]
   360  	}
   361  
   362  	return mr, nil
   363  }
   364  
   365  const millerRabinCOMPOSITE = false
   366  const millerRabinPOSSIBLYPRIME = true
   367  
   368  func millerRabinIteration(mr *millerRabin, bb []byte) (bool, error) {
   369  	// Reject b ≤ 1 or b ≥ w − 1.
   370  	if len(bb) != (mr.w.BitLen()+7)/8 {
   371  		return false, errors.New("incorrect length")
   372  	}
   373  	b := bigmod.NewNat()
   374  	if _, err := b.SetBytes(bb, mr.w); err != nil {
   375  		return false, err
   376  	}
   377  	if b.IsZero() == 1 || b.IsOne() == 1 || b.IsMinusOne(mr.w) == 1 {
   378  		return false, errors.New("out-of-range candidate")
   379  	}
   380  
   381  	// Compute b^(m*2^i) mod w for successive i.
   382  	// If b^m mod w = 1, b is a possible prime.
   383  	// If b^(m*2^i) mod w = -1 for some 0 <= i < a, b is a possible prime.
   384  	// Otherwise b is composite.
   385  
   386  	// Start by computing and checking b^m mod w (also the i = 0 case).
   387  	z := bigmod.NewNat().Exp(b, mr.m, mr.w)
   388  	if z.IsOne() == 1 || z.IsMinusOne(mr.w) == 1 {
   389  		return millerRabinPOSSIBLYPRIME, nil
   390  	}
   391  
   392  	// Check b^(m*2^i) mod w = -1 for 0 < i < a.
   393  	for range mr.a - 1 {
   394  		z.Mul(z, mr.w)
   395  		if z.IsMinusOne(mr.w) == 1 {
   396  			return millerRabinPOSSIBLYPRIME, nil
   397  		}
   398  		if z.IsOne() == 1 {
   399  			// Future squaring will not turn z == 1 into -1.
   400  			break
   401  		}
   402  	}
   403  
   404  	return millerRabinCOMPOSITE, nil
   405  }
   406
View as plain text