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  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  		// Clear the most significant bits to reach the desired size. We use a
   192  		// mask rather than right-shifting b[0] to make it easier to inject test
   193  		// candidates, which can be represented as simple big-endian integers.
   194  		excess := len(b)*8 - bits
   195  		b[0] &= 0b1111_1111 >> excess
   196  
   197  		// Don't let the value be too small: set the most significant two bits.
   198  		// Setting the top two bits, rather than just the top bit, means that
   199  		// when two of these values are multiplied together, the result isn't
   200  		// ever one bit short.
   201  		if excess < 7 {
   202  			b[0] |= 0b1100_0000 >> excess
   203  		} else {
   204  			b[0] |= 0b0000_0001
   205  			b[1] |= 0b1000_0000
   206  		}
   207  
   208  		// Make the value odd since an even number certainly isn't prime.
   209  		b[len(b)-1] |= 1
   210  
   211  		// We don't need to check for p >= √2 × 2^(bits-1) (steps 4.4 and 5.4)
   212  		// because we set the top two bits above, so
   213  		//
   214  		//   p > 2^(bits-1) + 2^(bits-2) = 3⁄2 × 2^(bits-1) > √2 × 2^(bits-1)
   215  		//
   216  
   217  		// Step 5.5 requires checking that |p - q| > 2^(nlen/2 - 100).
   218  		//
   219  		// The probability of |p - q| ≤ k where p and q are uniformly random in
   220  		// the range (a, b) is 1 - (b-a-k)^2 / (b-a)^2, so the probability of
   221  		// this check failing during key generation is 2⁻⁹⁷.
   222  		//
   223  		// We still need to check to comply with FIPS 186-5, but knowing it has
   224  		// negligible chance of failure we can defer the check to the end of key
   225  		// generation and return an error if it fails. See [checkPrivateKey].
   226  
   227  		if isPrime(b) {
   228  			return b, nil
   229  		}
   230  	}
   231  }
   232  
   233  // isPrime runs the Miller-Rabin Probabilistic Primality Test from
   234  // FIPS 186-5, Appendix B.3.1.
   235  //
   236  // w must be a random odd integer greater than three in big-endian order.
   237  // isPrime might return false positives for adversarially chosen values.
   238  //
   239  // isPrime is not constant-time.
   240  func isPrime(w []byte) bool {
   241  	mr, err := millerRabinSetup(w)
   242  	if err != nil {
   243  		// w is zero, one, or even.
   244  		return false
   245  	}
   246  
   247  	// Before Miller-Rabin, rule out most composites with trial divisions.
   248  	for i := 0; i < len(primes); i += 3 {
   249  		p1, p2, p3 := primes[i], primes[i+1], primes[i+2]
   250  		r := mr.w.Nat().DivShortVarTime(p1 * p2 * p3)
   251  		if r%p1 == 0 || r%p2 == 0 || r%p3 == 0 {
   252  			return false
   253  		}
   254  	}
   255  
   256  	// iterations is the number of Miller-Rabin rounds, each with a
   257  	// randomly-selected base.
   258  	//
   259  	// The worst case false positive rate for a single iteration is 1/4 per
   260  	// https://eprint.iacr.org/2018/749, so if w were selected adversarially, we
   261  	// would need up to 64 iterations to get to a negligible (2⁻¹²⁸) chance of
   262  	// false positive.
   263  	//
   264  	// However, since this function is only used for randomly-selected w in the
   265  	// context of RSA key generation, we can use a smaller number of iterations.
   266  	// The exact number depends on the size of the prime (and the implied
   267  	// security level). See BoringSSL for the full formula.
   268  	// https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/prime.c.inc;l=208-283;drc=3a138e43
   269  	bits := mr.w.BitLen()
   270  	var iterations int
   271  	switch {
   272  	case bits >= 3747:
   273  		iterations = 3
   274  	case bits >= 1345:
   275  		iterations = 4
   276  	case bits >= 476:
   277  		iterations = 5
   278  	case bits >= 400:
   279  		iterations = 6
   280  	case bits >= 347:
   281  		iterations = 7
   282  	case bits >= 308:
   283  		iterations = 8
   284  	case bits >= 55:
   285  		iterations = 27
   286  	default:
   287  		iterations = 34
   288  	}
   289  
   290  	b := make([]byte, (bits+7)/8)
   291  	for {
   292  		drbg.Read(b)
   293  		excess := len(b)*8 - bits
   294  		b[0] &= 0b1111_1111 >> excess
   295  		result, err := millerRabinIteration(mr, b)
   296  		if err != nil {
   297  			// b was rejected.
   298  			continue
   299  		}
   300  		if result == millerRabinCOMPOSITE {
   301  			return false
   302  		}
   303  		iterations--
   304  		if iterations == 0 {
   305  			return true
   306  		}
   307  	}
   308  }
   309  
   310  // primes are the first prime numbers (except 2), such that the product of any
   311  // three primes fits in a uint32.
   312  //
   313  // More primes cause fewer Miller-Rabin tests of composites (nothing can help
   314  // with the final test on the actual prime) but have diminishing returns: these
   315  // 255 primes catch 84.9% of composites, the next 255 would catch 1.5% more.
   316  // Adding primes can still be marginally useful since they only compete with the
   317  // (much more expensive) first Miller-Rabin round for candidates that were not
   318  // rejected by the previous primes.
   319  var primes = []uint{
   320  	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
   321  	59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
   322  	131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
   323  	211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
   324  	293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
   325  	389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
   326  	479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
   327  	587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
   328  	673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
   329  	773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877,
   330  	881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
   331  	991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
   332  	1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181,
   333  	1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
   334  	1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
   335  	1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487,
   336  	1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
   337  	1597, 1601, 1607, 1609, 1613, 1619,
   338  }
   339  
   340  type millerRabin struct {
   341  	w *bigmod.Modulus
   342  	a uint
   343  	m []byte
   344  }
   345  
   346  // millerRabinSetup prepares state that's reused across multiple iterations of
   347  // the Miller-Rabin test.
   348  func millerRabinSetup(w []byte) (*millerRabin, error) {
   349  	mr := &millerRabin{}
   350  
   351  	// Check that w is odd, and precompute Montgomery parameters.
   352  	wm, err := bigmod.NewModulus(w)
   353  	if err != nil {
   354  		return nil, err
   355  	}
   356  	if wm.Nat().IsOdd() == 0 {
   357  		return nil, errors.New("candidate is even")
   358  	}
   359  	mr.w = wm
   360  
   361  	// Compute m = (w-1)/2^a, where m is odd.
   362  	wMinus1 := mr.w.Nat().SubOne(mr.w)
   363  	if wMinus1.IsZero() == 1 {
   364  		return nil, errors.New("candidate is one")
   365  	}
   366  	mr.a = wMinus1.TrailingZeroBitsVarTime()
   367  
   368  	// Store mr.m as a big-endian byte slice with leading zero bytes removed,
   369  	// for use with [bigmod.Nat.Exp].
   370  	m := wMinus1.ShiftRightVarTime(mr.a)
   371  	mr.m = m.Bytes(mr.w)
   372  	for mr.m[0] == 0 {
   373  		mr.m = mr.m[1:]
   374  	}
   375  
   376  	return mr, nil
   377  }
   378  
   379  const millerRabinCOMPOSITE = false
   380  const millerRabinPOSSIBLYPRIME = true
   381  
   382  func millerRabinIteration(mr *millerRabin, bb []byte) (bool, error) {
   383  	// Reject b ≤ 1 or b ≥ w − 1.
   384  	if len(bb) != (mr.w.BitLen()+7)/8 {
   385  		return false, errors.New("incorrect length")
   386  	}
   387  	b := bigmod.NewNat()
   388  	if _, err := b.SetBytes(bb, mr.w); err != nil {
   389  		return false, err
   390  	}
   391  	if b.IsZero() == 1 || b.IsOne() == 1 || b.IsMinusOne(mr.w) == 1 {
   392  		return false, errors.New("out-of-range candidate")
   393  	}
   394  
   395  	// Compute b^(m*2^i) mod w for successive i.
   396  	// If b^m mod w = 1, b is a possible prime.
   397  	// If b^(m*2^i) mod w = -1 for some 0 <= i < a, b is a possible prime.
   398  	// Otherwise b is composite.
   399  
   400  	// Start by computing and checking b^m mod w (also the i = 0 case).
   401  	z := bigmod.NewNat().Exp(b, mr.m, mr.w)
   402  	if z.IsOne() == 1 || z.IsMinusOne(mr.w) == 1 {
   403  		return millerRabinPOSSIBLYPRIME, nil
   404  	}
   405  
   406  	// Check b^(m*2^i) mod w = -1 for 0 < i < a.
   407  	for range mr.a - 1 {
   408  		z.Mul(z, mr.w)
   409  		if z.IsMinusOne(mr.w) == 1 {
   410  			return millerRabinPOSSIBLYPRIME, nil
   411  		}
   412  		if z.IsOne() == 1 {
   413  			// Future squaring will not turn z == 1 into -1.
   414  			break
   415  		}
   416  	}
   417  
   418  	return millerRabinCOMPOSITE, nil
   419  }
   420
View as plain text