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