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  	primes, err := bigmod.NewNat().SetBytes(productOfPrimes, mr.w)
   227  	// If w is too small for productOfPrimes, key generation is
   228  	// going to be fast enough anyway.
   229  	if err == nil {
   230  		_, hasInverse := primes.InverseVarTime(primes, mr.w)
   231  		if !hasInverse {
   232  			// productOfPrimes doesn't have an inverse mod w,
   233  			// so w is divisible by at least one of the primes.
   234  			return false
   235  		}
   236  	}
   237  
   238  	// iterations is the number of Miller-Rabin rounds, each with a
   239  	// randomly-selected base.
   240  	//
   241  	// The worst case false positive rate for a single iteration is 1/4 per
   242  	// https://eprint.iacr.org/2018/749, so if w were selected adversarially, we
   243  	// would need up to 64 iterations to get to a negligible (2⁻¹²⁸) chance of
   244  	// false positive.
   245  	//
   246  	// However, since this function is only used for randomly-selected w in the
   247  	// context of RSA key generation, we can use a smaller number of iterations.
   248  	// The exact number depends on the size of the prime (and the implied
   249  	// security level). See BoringSSL for the full formula.
   250  	// https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/prime.c.inc;l=208-283;drc=3a138e43
   251  	bits := mr.w.BitLen()
   252  	var iterations int
   253  	switch {
   254  	case bits >= 3747:
   255  		iterations = 3
   256  	case bits >= 1345:
   257  		iterations = 4
   258  	case bits >= 476:
   259  		iterations = 5
   260  	case bits >= 400:
   261  		iterations = 6
   262  	case bits >= 347:
   263  		iterations = 7
   264  	case bits >= 308:
   265  		iterations = 8
   266  	case bits >= 55:
   267  		iterations = 27
   268  	default:
   269  		iterations = 34
   270  	}
   271  
   272  	b := make([]byte, (bits+7)/8)
   273  	for {
   274  		drbg.Read(b)
   275  		excess := len(b)*8 - bits
   276  		b[0] &= 0b1111_1111 >> excess
   277  		result, err := millerRabinIteration(mr, b)
   278  		if err != nil {
   279  			// b was rejected.
   280  			continue
   281  		}
   282  		if result == millerRabinCOMPOSITE {
   283  			return false
   284  		}
   285  		iterations--
   286  		if iterations == 0 {
   287  			return true
   288  		}
   289  	}
   290  }
   291  
   292  // productOfPrimes is the product of the first 74 primes higher than 2.
   293  //
   294  // The number of primes was selected to be the highest such that the product fit
   295  // in 512 bits, so to be usable for 1024 bit RSA keys.
   296  //
   297  // Higher values cause fewer Miller-Rabin tests of composites (nothing can help
   298  // with the final test on the actual prime) but make InverseVarTime take longer.
   299  // There are diminishing returns: including the 75th prime would increase the
   300  // success rate of trial division by 0.05%.
   301  var productOfPrimes = []byte{
   302  	0x10, 0x6a, 0xa9, 0xfb, 0x76, 0x46, 0xfa, 0x6e, 0xb0, 0x81, 0x3c, 0x28, 0xc5, 0xd5, 0xf0, 0x9f,
   303  	0x07, 0x7e, 0xc3, 0xba, 0x23, 0x8b, 0xfb, 0x99, 0xc1, 0xb6, 0x31, 0xa2, 0x03, 0xe8, 0x11, 0x87,
   304  	0x23, 0x3d, 0xb1, 0x17, 0xcb, 0xc3, 0x84, 0x05, 0x6e, 0xf0, 0x46, 0x59, 0xa4, 0xa1, 0x1d, 0xe4,
   305  	0x9f, 0x7e, 0xcb, 0x29, 0xba, 0xda, 0x8f, 0x98, 0x0d, 0xec, 0xec, 0xe9, 0x2e, 0x30, 0xc4, 0x8f,
   306  }
   307  
   308  type millerRabin struct {
   309  	w *bigmod.Modulus
   310  	a uint
   311  	m []byte
   312  }
   313  
   314  // millerRabinSetup prepares state that's reused across multiple iterations of
   315  // the Miller-Rabin test.
   316  func millerRabinSetup(w []byte) (*millerRabin, error) {
   317  	mr := &millerRabin{}
   318  
   319  	// Check that w is odd, and precompute Montgomery parameters.
   320  	wm, err := bigmod.NewModulus(w)
   321  	if err != nil {
   322  		return nil, err
   323  	}
   324  	if wm.Nat().IsOdd() == 0 {
   325  		return nil, errors.New("candidate is even")
   326  	}
   327  	mr.w = wm
   328  
   329  	// Compute m = (w-1)/2^a, where m is odd.
   330  	wMinus1 := mr.w.Nat().SubOne(mr.w)
   331  	if wMinus1.IsZero() == 1 {
   332  		return nil, errors.New("candidate is one")
   333  	}
   334  	mr.a = wMinus1.TrailingZeroBitsVarTime()
   335  
   336  	// Store mr.m as a big-endian byte slice with leading zero bytes removed,
   337  	// for use with [bigmod.Nat.Exp].
   338  	m := wMinus1.ShiftRightVarTime(mr.a)
   339  	mr.m = m.Bytes(mr.w)
   340  	for mr.m[0] == 0 {
   341  		mr.m = mr.m[1:]
   342  	}
   343  
   344  	return mr, nil
   345  }
   346  
   347  const millerRabinCOMPOSITE = false
   348  const millerRabinPOSSIBLYPRIME = true
   349  
   350  func millerRabinIteration(mr *millerRabin, bb []byte) (bool, error) {
   351  	// Reject b ≤ 1 or b ≥ w − 1.
   352  	if len(bb) != (mr.w.BitLen()+7)/8 {
   353  		return false, errors.New("incorrect length")
   354  	}
   355  	b := bigmod.NewNat()
   356  	if _, err := b.SetBytes(bb, mr.w); err != nil {
   357  		return false, err
   358  	}
   359  	if b.IsZero() == 1 || b.IsOne() == 1 || b.IsMinusOne(mr.w) == 1 {
   360  		return false, errors.New("out-of-range candidate")
   361  	}
   362  
   363  	// Compute b^(m*2^i) mod w for successive i.
   364  	// If b^m mod w = 1, b is a possible prime.
   365  	// If b^(m*2^i) mod w = -1 for some 0 <= i < a, b is a possible prime.
   366  	// Otherwise b is composite.
   367  
   368  	// Start by computing and checking b^m mod w (also the i = 0 case).
   369  	z := bigmod.NewNat().Exp(b, mr.m, mr.w)
   370  	if z.IsOne() == 1 || z.IsMinusOne(mr.w) == 1 {
   371  		return millerRabinPOSSIBLYPRIME, nil
   372  	}
   373  
   374  	// Check b^(m*2^i) mod w = -1 for 0 < i < a.
   375  	for range mr.a - 1 {
   376  		z.Mul(z, mr.w)
   377  		if z.IsMinusOne(mr.w) == 1 {
   378  			return millerRabinPOSSIBLYPRIME, nil
   379  		}
   380  		if z.IsOne() == 1 {
   381  			// Future squaring will not turn z == 1 into -1.
   382  			break
   383  		}
   384  	}
   385  
   386  	return millerRabinCOMPOSITE, nil
   387  }
   388
View as plain text