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  		if excess := len(b)*8 - bits; excess != 0 {
   171  			b[0] >>= excess
   172  		}
   173  
   174  		// Don't let the value be too small: set the most significant two bits.
   175  		// Setting the top two bits, rather than just the top bit, means that
   176  		// when two of these values are multiplied together, the result isn't
   177  		// ever one bit short.
   178  		if excess := len(b)*8 - bits; excess < 7 {
   179  			b[0] |= 0b1100_0000 >> excess
   180  		} else {
   181  			b[0] |= 0b0000_0001
   182  			b[1] |= 0b1000_0000
   183  		}
   184  
   185  		// Make the value odd since an even number certainly isn't prime.
   186  		b[len(b)-1] |= 1
   187  
   188  		// We don't need to check for p >= √2 × 2^(bits-1) (steps 4.4 and 5.4)
   189  		// because we set the top two bits above, so
   190  		//
   191  		//   p > 2^(bits-1) + 2^(bits-2) = 3⁄2 × 2^(bits-1) > √2 × 2^(bits-1)
   192  		//
   193  
   194  		// Step 5.5 requires checking that |p - q| > 2^(nlen/2 - 100).
   195  		//
   196  		// The probability of |p - q| ≤ k where p and q are uniformly random in
   197  		// the range (a, b) is 1 - (b-a-k)^2 / (b-a)^2, so the probability of
   198  		// this check failing during key generation is 2⁻⁹⁷.
   199  		//
   200  		// We still need to check to comply with FIPS 186-5, but knowing it has
   201  		// negligible chance of failure we can defer the check to the end of key
   202  		// generation and return an error if it fails. See [checkPrivateKey].
   203  
   204  		if isPrime(b) {
   205  			return b, nil
   206  		}
   207  	}
   208  }
   209  
   210  // isPrime runs the Miller-Rabin Probabilistic Primality Test from
   211  // FIPS 186-5, Appendix B.3.1.
   212  //
   213  // w must be a random odd integer greater than three in big-endian order.
   214  // isPrime might return false positives for adversarially chosen values.
   215  //
   216  // isPrime is not constant-time.
   217  func isPrime(w []byte) bool {
   218  	mr, err := millerRabinSetup(w)
   219  	if err != nil {
   220  		// w is zero, one, or even.
   221  		return false
   222  	}
   223  
   224  	primes, err := bigmod.NewNat().SetBytes(productOfPrimes, mr.w)
   225  	// If w is too small for productOfPrimes, key generation is
   226  	// going to be fast enough anyway.
   227  	if err == nil {
   228  		_, hasInverse := primes.InverseVarTime(primes, mr.w)
   229  		if !hasInverse {
   230  			// productOfPrimes doesn't have an inverse mod w,
   231  			// so w is divisible by at least one of the primes.
   232  			return false
   233  		}
   234  	}
   235  
   236  	// iterations is the number of Miller-Rabin rounds, each with a
   237  	// randomly-selected base.
   238  	//
   239  	// The worst case false positive rate for a single iteration is 1/4 per
   240  	// https://eprint.iacr.org/2018/749, so if w were selected adversarially, we
   241  	// would need up to 64 iterations to get to a negligible (2⁻¹²⁸) chance of
   242  	// false positive.
   243  	//
   244  	// However, since this function is only used for randomly-selected w in the
   245  	// context of RSA key generation, we can use a smaller number of iterations.
   246  	// The exact number depends on the size of the prime (and the implied
   247  	// security level). See BoringSSL for the full formula.
   248  	// https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/prime.c.inc;l=208-283;drc=3a138e43
   249  	bits := mr.w.BitLen()
   250  	var iterations int
   251  	switch {
   252  	case bits >= 3747:
   253  		iterations = 3
   254  	case bits >= 1345:
   255  		iterations = 4
   256  	case bits >= 476:
   257  		iterations = 5
   258  	case bits >= 400:
   259  		iterations = 6
   260  	case bits >= 347:
   261  		iterations = 7
   262  	case bits >= 308:
   263  		iterations = 8
   264  	case bits >= 55:
   265  		iterations = 27
   266  	default:
   267  		iterations = 34
   268  	}
   269  
   270  	b := make([]byte, (bits+7)/8)
   271  	for {
   272  		drbg.Read(b)
   273  		if excess := len(b)*8 - bits; excess != 0 {
   274  			b[0] >>= excess
   275  		}
   276  		result, err := millerRabinIteration(mr, b)
   277  		if err != nil {
   278  			// b was rejected.
   279  			continue
   280  		}
   281  		if result == millerRabinCOMPOSITE {
   282  			return false
   283  		}
   284  		iterations--
   285  		if iterations == 0 {
   286  			return true
   287  		}
   288  	}
   289  }
   290  
   291  // productOfPrimes is the product of the first 74 primes higher than 2.
   292  //
   293  // The number of primes was selected to be the highest such that the product fit
   294  // in 512 bits, so to be usable for 1024 bit RSA keys.
   295  //
   296  // Higher values cause fewer Miller-Rabin tests of composites (nothing can help
   297  // with the final test on the actual prime) but make InverseVarTime take longer.
   298  var productOfPrimes = []byte{
   299  	0x10, 0x6a, 0xa9, 0xfb, 0x76, 0x46, 0xfa, 0x6e, 0xb0, 0x81, 0x3c, 0x28, 0xc5, 0xd5, 0xf0, 0x9f,
   300  	0x07, 0x7e, 0xc3, 0xba, 0x23, 0x8b, 0xfb, 0x99, 0xc1, 0xb6, 0x31, 0xa2, 0x03, 0xe8, 0x11, 0x87,
   301  	0x23, 0x3d, 0xb1, 0x17, 0xcb, 0xc3, 0x84, 0x05, 0x6e, 0xf0, 0x46, 0x59, 0xa4, 0xa1, 0x1d, 0xe4,
   302  	0x9f, 0x7e, 0xcb, 0x29, 0xba, 0xda, 0x8f, 0x98, 0x0d, 0xec, 0xec, 0xe9, 0x2e, 0x30, 0xc4, 0x8f,
   303  }
   304  
   305  type millerRabin struct {
   306  	w *bigmod.Modulus
   307  	a uint
   308  	m []byte
   309  }
   310  
   311  // millerRabinSetup prepares state that's reused across multiple iterations of
   312  // the Miller-Rabin test.
   313  func millerRabinSetup(w []byte) (*millerRabin, error) {
   314  	mr := &millerRabin{}
   315  
   316  	// Check that w is odd, and precompute Montgomery parameters.
   317  	wm, err := bigmod.NewModulus(w)
   318  	if err != nil {
   319  		return nil, err
   320  	}
   321  	if wm.Nat().IsOdd() == 0 {
   322  		return nil, errors.New("candidate is even")
   323  	}
   324  	mr.w = wm
   325  
   326  	// Compute m = (w-1)/2^a, where m is odd.
   327  	wMinus1 := mr.w.Nat().SubOne(mr.w)
   328  	if wMinus1.IsZero() == 1 {
   329  		return nil, errors.New("candidate is one")
   330  	}
   331  	mr.a = wMinus1.TrailingZeroBitsVarTime()
   332  
   333  	// Store mr.m as a big-endian byte slice with leading zero bytes removed,
   334  	// for use with [bigmod.Nat.Exp].
   335  	m := wMinus1.ShiftRightVarTime(mr.a)
   336  	mr.m = m.Bytes(mr.w)
   337  	for mr.m[0] == 0 {
   338  		mr.m = mr.m[1:]
   339  	}
   340  
   341  	return mr, nil
   342  }
   343  
   344  const millerRabinCOMPOSITE = false
   345  const millerRabinPOSSIBLYPRIME = true
   346  
   347  func millerRabinIteration(mr *millerRabin, bb []byte) (bool, error) {
   348  	// Reject b ≤ 1 or b ≥ w − 1.
   349  	if len(bb) != (mr.w.BitLen()+7)/8 {
   350  		return false, errors.New("incorrect length")
   351  	}
   352  	b := bigmod.NewNat()
   353  	if _, err := b.SetBytes(bb, mr.w); err != nil {
   354  		return false, err
   355  	}
   356  	if b.IsZero() == 1 || b.IsOne() == 1 || b.IsMinusOne(mr.w) == 1 {
   357  		return false, errors.New("out-of-range candidate")
   358  	}
   359  
   360  	// Compute b^(m*2^i) mod w for successive i.
   361  	// If b^m mod w = 1, b is a possible prime.
   362  	// If b^(m*2^i) mod w = -1 for some 0 <= i < a, b is a possible prime.
   363  	// Otherwise b is composite.
   364  
   365  	// Start by computing and checking b^m mod w (also the i = 0 case).
   366  	z := bigmod.NewNat().Exp(b, mr.m, mr.w)
   367  	if z.IsOne() == 1 || z.IsMinusOne(mr.w) == 1 {
   368  		return millerRabinPOSSIBLYPRIME, nil
   369  	}
   370  
   371  	// Check b^(m*2^i) mod w = -1 for 0 < i < a.
   372  	for range mr.a - 1 {
   373  		z.Mul(z, mr.w)
   374  		if z.IsMinusOne(mr.w) == 1 {
   375  			return millerRabinPOSSIBLYPRIME, nil
   376  		}
   377  		if z.IsOne() == 1 {
   378  			// Future squaring will not turn z == 1 into -1.
   379  			break
   380  		}
   381  	}
   382  
   383  	return millerRabinCOMPOSITE, nil
   384  }
   385
View as plain text