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