keygen.go

     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  //
    18  // It follows the process described at c2sp.org/det-keygen, which is compliant
    19  // with FIPS 186-5, Appendix A.1, IFC Key Pair Generation and FIPS 186-5,
    20  // Appendix A.1.3, Generation of Random Primes that are Probably Prime.
    21  // The prime candidates are drawn from rand, which in production will be the
    22  // global DRBG, while in tests can be an HMAC_DRBG as specified in
    23  // c2sp.org/det-keygen, to allow using its tests vectors.
    24  func GenerateKey(rand io.Reader, bits int) (*PrivateKey, error) {
    25  	if bits < 32 {
    26  		return nil, errors.New("rsa: key too small")
    27  	}
    28  	fipsSelfTest()
    29  	fips140.RecordApproved()
    30  	if bits < 2048 || bits%2 == 1 {
    31  		fips140.RecordNonApproved()
    32  	}
    33  
    34  	for {
    35  		p, err := randomPrime(rand, (bits+1)/2)
    36  		if err != nil {
    37  			return nil, err
    38  		}
    39  		q, err := randomPrime(rand, bits/2)
    40  		if err != nil {
    41  			return nil, err
    42  		}
    43  
    44  		P, err := bigmod.NewModulus(p)
    45  		if err != nil {
    46  			return nil, err
    47  		}
    48  		Q, err := bigmod.NewModulus(q)
    49  		if err != nil {
    50  			return nil, err
    51  		}
    52  
    53  		if Q.Nat().ExpandFor(P).Equal(P.Nat()) == 1 {
    54  			return nil, errors.New("rsa: generated p == q, random source is broken")
    55  		}
    56  
    57  		N, err := bigmod.NewModulusProduct(p, q)
    58  		if err != nil {
    59  			return nil, err
    60  		}
    61  		if N.BitLen() != bits {
    62  			return nil, errors.New("rsa: internal error: modulus size incorrect")
    63  		}
    64  
    65  		// d can be safely computed as e⁻¹ mod φ(N) where φ(N) = (p-1)(q-1), and
    66  		// indeed that's what both the original RSA paper and the pre-FIPS
    67  		// crypto/rsa implementation did.
    68  		//
    69  		// However, FIPS 186-5, A.1.1(3) requires computing it as e⁻¹ mod λ(N)
    70  		// where λ(N) = lcm(p-1, q-1).
    71  		//
    72  		// This makes d smaller by 1.82 bits on average, which is irrelevant both
    73  		// because we exclusively use the CRT for private operations and because
    74  		// we use constant time windowed exponentiation. On the other hand, it
    75  		// requires computing a GCD of two even numbers, and then a division,
    76  		// both complex variable-time operations.
    77  		λ, err := totient(P, Q)
    78  		if err == errDivisorTooLarge {
    79  			// The divisor is too large, try again with different primes.
    80  			continue
    81  		}
    82  		if err != nil {
    83  			return nil, err
    84  		}
    85  
    86  		e := bigmod.NewNat().SetUint(65537)
    87  		d, ok := bigmod.NewNat().InverseVarTime(e, λ)
    88  		if !ok {
    89  			// This checks that GCD(e, lcm(p-1, q-1)) = 1, which is equivalent
    90  			// to checking GCD(e, p-1) = 1 and GCD(e, q-1) = 1 separately in
    91  			// FIPS 186-5, Appendix A.1.3, steps 4.5 and 5.6.
    92  			//
    93  			// We waste a prime by retrying the whole process, since 65537 is
    94  			// probably only a factor of one of p-1 or q-1, but the probability
    95  			// of this check failing is ≈ 2⁻¹⁵, so it doesn't matter.
    96  			continue
    97  		}
    98  
    99  		if e.ExpandFor(λ).Mul(d, λ).IsOne() == 0 {
   100  			return nil, errors.New("rsa: internal error: e*d != 1 mod λ(N)")
   101  		}
   102  
   103  		// FIPS 186-5, A.1.1(3) requires checking that d > 2^(nlen / 2).
   104  		//
   105  		// The probability of this check failing when d is derived from
   106  		// (e, p, q) is roughly
   107  		//
   108  		//   2^(nlen/2) / λ(N) ≈ 2^(-nlen/2 + 1.82)
   109  		//
   110  		// so less than 2⁻¹²⁶ for keys larger than 256 bits.
   111  		//
   112  		// We still need to check to comply with FIPS 186-5, but knowing it has
   113  		// negligible chance of failure we can defer the check to the end of key
   114  		// generation and return an error if it fails. See [checkPrivateKey].
   115  
   116  		k, err := newPrivateKey(N, 65537, d, P, Q)
   117  		if err != nil {
   118  			return nil, err
   119  		}
   120  
   121  		if k.fipsApproved {
   122  			fips140.PCT("RSA sign and verify PCT", func() error {
   123  				hash := []byte{
   124  					0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
   125  					0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10,
   126  					0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
   127  					0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
   128  				}
   129  				sig, err := signPKCS1v15(k, "SHA-256", hash)
   130  				if err != nil {
   131  					return err
   132  				}
   133  				return verifyPKCS1v15(k.PublicKey(), "SHA-256", hash, sig)
   134  			})
   135  		}
   136  
   137  		return k, nil
   138  	}
   139  }
   140  
   141  // errDivisorTooLarge is returned by [totient] when gcd(p-1, q-1) is too large.
   142  var errDivisorTooLarge = errors.New("divisor too large")
   143  
   144  // totient computes the Carmichael totient function λ(N) = lcm(p-1, q-1).
   145  //
   146  // p and q must be primes congruent to 7 mod 8, so that p-1 and q-1 are both
   147  // even but not divisible by 4.
   148  //
   149  // totient returns errDivisorTooLarge if GCD(p-1, q-1) is larger than 2³²-1.
   150  func totient(p, q *bigmod.Modulus) (*bigmod.Modulus, error) {
   151  	a, b := p.Nat().SubOne(p), q.Nat().SubOne(q)
   152  	if a.IsOdd() == 1 || b.IsOdd() == 1 {
   153  		return nil, errors.New("rsa: internal error: p and q must be 7 mod 8")
   154  	}
   155  
   156  	// lcm(a, b) = a×b / gcd(a, b) = a × (b / gcd(a, b))
   157  
   158  	// Our GCD requires at least one of the numbers to be odd.
   159  	// We know that a / 2 and b / 2 are odd because p and q are 7 mod 8.
   160  	// For LCM we only need to preserve the larger prime power of each
   161  	// prime factor, so we can shift out 2 from either of them.
   162  	// For odd x, y and m >= n, lcm(x×2, y×2) = lcm(x×2, y).
   163  	b = b.ShiftRightByOne()
   164  	if b.IsOdd() == 0 {
   165  		return nil, errors.New("rsa: internal error: p and q must be 7 mod 8")
   166  	}
   167  
   168  	gcd, err := bigmod.NewNat().GCDVarTime(a, b)
   169  	if err != nil {
   170  		return nil, err
   171  	}
   172  	if gcd.IsOdd() == 0 {
   173  		return nil, errors.New("rsa: internal error: gcd(a, b) is even")
   174  	}
   175  
   176  	// To avoid implementing multiple-precision division, we just try again if
   177  	// the divisor doesn't fit in a single word. This would have a chance of
   178  	// ~2⁻⁶⁴ on 64-bit platforms, and ~2⁻³² on 32-bit platforms, but testing
   179  	// 2⁻⁶⁴ edge cases is impractical, and we'd rather not behave differently on
   180  	// different platforms, so we reject divisors above 2³²-1. Note that we also
   181  	// add back the factor of 2 we shifted out above.
   182  	if gcd.BitLenVarTime()+1 > 32 {
   183  		return nil, errDivisorTooLarge
   184  	}
   185  	if gcd.IsZero() == 1 || gcd.Bits()[0] == 0 {
   186  		return nil, errors.New("rsa: internal error: gcd(a, b) is zero")
   187  	}
   188  	if rem := b.DivShortVarTime(gcd.Bits()[0]); rem != 0 {
   189  		return nil, errors.New("rsa: internal error: b is not divisible by gcd(a, b)")
   190  	}
   191  
   192  	return bigmod.NewModulusProduct(a.Bytes(p), b.Bytes(q))
   193  }
   194  
   195  // randomPrime returns a random prime number of the given bit size following
   196  // the process in FIPS 186-5, Appendix A.1.3.
   197  func randomPrime(rand io.Reader, bits int) ([]byte, error) {
   198  	if bits < 16 {
   199  		return nil, errors.New("rsa: prime size must be at least 16 bits")
   200  	}
   201  
   202  	b := make([]byte, (bits+7)/8)
   203  	for {
   204  		if err := drbg.ReadWithReader(rand, b); err != nil {
   205  			return nil, err
   206  		}
   207  		// Clear the most significant bits to reach the desired size. We use a
   208  		// mask rather than right-shifting b[0] to make it easier to inject test
   209  		// candidates, which can be represented as simple big-endian integers.
   210  		excess := len(b)*8 - bits
   211  		b[0] &= 0b1111_1111 >> excess
   212  
   213  		// Don't let the value be too small: set the most significant two bits.
   214  		// Setting the top two bits, rather than just the top bit, means that
   215  		// when two of these values are multiplied together, the result isn't
   216  		// ever one bit short.
   217  		if excess < 7 {
   218  			b[0] |= 0b1100_0000 >> excess
   219  		} else {
   220  			b[0] |= 0b0000_0001
   221  			b[1] |= 0b1000_0000
   222  		}
   223  
   224  		// Set the three least significant bits, which makes the value 7 mod 8
   225  		// (steps 4.3 and 5.3). Even numbers are not prime, and an odd
   226  		// (p - 1) / 2 simplifies [millerRabinIteration] and the GCD in [totient].
   227  		b[len(b)-1] |= 0b0000_0111
   228  
   229  		// We don't need to check for p >= √2 × 2^(bits-1) (steps 4.4 and 5.4)
   230  		// because we set the top two bits above, so
   231  		//
   232  		//   p > 2^(bits-1) + 2^(bits-2) = 3⁄2 × 2^(bits-1) > √2 × 2^(bits-1)
   233  		//
   234  
   235  		// Step 5.5 requires checking that |p - q| > 2^(nlen/2 - 100).
   236  		//
   237  		// The probability of |p - q| ≤ k where p and q are uniformly random in
   238  		// the range (a, b) is 1 - (b-a-k)^2 / (b-a)^2, so the probability of
   239  		// this check failing during key generation is 2⁻⁹⁷.
   240  		//
   241  		// We still need to check to comply with FIPS 186-5, but knowing it has
   242  		// negligible chance of failure we can defer the check to the end of key
   243  		// generation and return an error if it fails. See [checkPrivateKey].
   244  
   245  		if isPrime(b) {
   246  			return b, nil
   247  		}
   248  	}
   249  }
   250  
   251  // isPrime runs the Miller-Rabin Probabilistic Primality Test from
   252  // FIPS 186-5, Appendix B.3.1.
   253  //
   254  // w must be a random integer equal to 3 mod 4 in big-endian order.
   255  // isPrime might return false positives for adversarially chosen values.
   256  //
   257  // isPrime is not constant-time.
   258  func isPrime(w []byte) bool {
   259  	mr, err := millerRabinSetup(w)
   260  	if err != nil {
   261  		// w is zero, one, or even.
   262  		return false
   263  	}
   264  
   265  	// Before Miller-Rabin, rule out most composites with trial divisions.
   266  	for i := 0; i < len(primes); i += 3 {
   267  		p1, p2, p3 := primes[i], primes[i+1], primes[i+2]
   268  		r := mr.w.Nat().DivShortVarTime(p1 * p2 * p3)
   269  		if r%p1 == 0 || r%p2 == 0 || r%p3 == 0 {
   270  			return false
   271  		}
   272  	}
   273  
   274  	// iterations is the number of Miller-Rabin rounds, each with a
   275  	// randomly-selected base.
   276  	//
   277  	// The worst case false positive rate for a single iteration is 1/4 per
   278  	// https://eprint.iacr.org/2018/749, so if w were selected adversarially, we
   279  	// would need up to 64 iterations to get to a negligible (2⁻¹²⁸) chance of
   280  	// false positive.
   281  	//
   282  	// However, since this function is only used for randomly-selected w in the
   283  	// context of RSA key generation, we can use a smaller number of iterations.
   284  	// The exact number depends on the size of the prime (and the implied
   285  	// security level). See BoringSSL for the full formula.
   286  	// https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/prime.c.inc;l=208-283;drc=3a138e43
   287  	bits := mr.w.BitLen()
   288  	var iterations int
   289  	switch {
   290  	case bits >= 3747:
   291  		iterations = 3
   292  	case bits >= 1345:
   293  		iterations = 4
   294  	case bits >= 476:
   295  		iterations = 5
   296  	case bits >= 400:
   297  		iterations = 6
   298  	case bits >= 347:
   299  		iterations = 7
   300  	case bits >= 308:
   301  		iterations = 8
   302  	case bits >= 55:
   303  		iterations = 27
   304  	default:
   305  		iterations = 34
   306  	}
   307  
   308  	b := make([]byte, (bits+7)/8)
   309  	for {
   310  		drbg.Read(b)
   311  		excess := len(b)*8 - bits
   312  		b[0] &= 0b1111_1111 >> excess
   313  		result, err := millerRabinIteration(mr, b)
   314  		if err != nil {
   315  			// b was rejected.
   316  			continue
   317  		}
   318  		if result == millerRabinCOMPOSITE {
   319  			return false
   320  		}
   321  		iterations--
   322  		if iterations == 0 {
   323  			return true
   324  		}
   325  	}
   326  }
   327  
   328  // primes are the first prime numbers (except 2), such that the product of any
   329  // three primes fits in a uint32.
   330  //
   331  // More primes cause fewer Miller-Rabin tests of composites (nothing can help
   332  // with the final test on the actual prime) but have diminishing returns: these
   333  // 255 primes catch 84.9% of composites, the next 255 would catch 1.5% more.
   334  // Adding primes can still be marginally useful since they only compete with the
   335  // (much more expensive) first Miller-Rabin round for candidates that were not
   336  // rejected by the previous primes.
   337  var primes = []uint{
   338  	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
   339  	59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
   340  	131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
   341  	211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
   342  	293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
   343  	389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
   344  	479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
   345  	587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
   346  	673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
   347  	773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877,
   348  	881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
   349  	991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
   350  	1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181,
   351  	1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
   352  	1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
   353  	1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487,
   354  	1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
   355  	1597, 1601, 1607, 1609, 1613, 1619,
   356  }
   357  
   358  type millerRabin struct {
   359  	w *bigmod.Modulus
   360  	m []byte
   361  }
   362  
   363  // millerRabinSetup prepares state that's reused across multiple iterations of
   364  // the Miller-Rabin test.
   365  //
   366  // w must be a random integer equal to 3 mod 4 in big-endian order.
   367  func millerRabinSetup(w []byte) (*millerRabin, error) {
   368  	mr := &millerRabin{}
   369  
   370  	// Check that w is 3 mod 4, and precompute Montgomery parameters.
   371  	if len(w) == 0 || w[len(w)-1]&0b11 != 0b11 {
   372  		return nil, errors.New("candidate is not 3 mod 4")
   373  	}
   374  	wm, err := bigmod.NewModulus(w)
   375  	if err != nil {
   376  		return nil, err
   377  	}
   378  	mr.w = wm
   379  
   380  	// Compute m = (w-1)/2^a, where m is odd.
   381  	// Since w is 3 mod 4, a is always 1, so m = (w-1)/2.
   382  	m := mr.w.Nat().SubOne(mr.w).ShiftRightByOne()
   383  
   384  	// Store mr.m as a big-endian byte slice with leading zero bytes removed,
   385  	// for use with [bigmod.Nat.Exp].
   386  	mr.m = m.Bytes(mr.w)
   387  	for mr.m[0] == 0 {
   388  		mr.m = mr.m[1:]
   389  	}
   390  
   391  	return mr, nil
   392  }
   393  
   394  const millerRabinCOMPOSITE = false
   395  const millerRabinPOSSIBLYPRIME = true
   396  
   397  func millerRabinIteration(mr *millerRabin, bb []byte) (bool, error) {
   398  	// Reject b ≤ 1 or b ≥ w − 1.
   399  	if len(bb) != (mr.w.BitLen()+7)/8 {
   400  		return false, errors.New("incorrect length")
   401  	}
   402  	b := bigmod.NewNat()
   403  	if _, err := b.SetBytes(bb, mr.w); err != nil {
   404  		return false, err
   405  	}
   406  	if b.IsZero() == 1 || b.IsOne() == 1 || b.IsMinusOne(mr.w) == 1 {
   407  		return false, errors.New("out-of-range candidate")
   408  	}
   409  
   410  	// Compute b^(m*2^i) mod w for successive i.
   411  	// If b^m mod w = 1, b is a possible prime.
   412  	// If b^(m*2^i) mod w = -1 for some 0 <= i < a, b is a possible prime.
   413  	// Otherwise b is composite.
   414  
   415  	// Since a = 1 for our w, we only need to check b^m mod w = +/-1.
   416  	z := bigmod.NewNat().Exp(b, mr.m, mr.w)
   417  	if z.IsOne() == 1 || z.IsMinusOne(mr.w) == 1 {
   418  		return millerRabinPOSSIBLYPRIME, nil
   419  	}
   420  
   421  	return millerRabinCOMPOSITE, nil
   422  }
   423
View as plain text