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  		φ, err := bigmod.NewModulusProduct(P.Nat().SubOne(P).Bytes(P),
    58  			Q.Nat().SubOne(Q).Bytes(Q))
    59  		if err != nil {
    60  			return nil, err
    61  		}
    62  
    63  		e := bigmod.NewNat().SetUint(65537)
    64  		d, ok := bigmod.NewNat().InverseVarTime(e, φ)
    65  		if !ok {
    66  			// This checks that GCD(e, (p-1)(q-1)) = 1, which is equivalent
    67  			// to checking GCD(e, p-1) = 1 and GCD(e, q-1) = 1 separately in
    68  			// FIPS 186-5, Appendix A.1.3, steps 4.5 and 5.6.
    69  			continue
    70  		}
    71  
    72  		if e.ExpandFor(φ).Mul(d, φ).IsOne() == 0 {
    73  			return nil, errors.New("rsa: internal error: e*d != 1 mod φ(N)")
    74  		}
    75  
    76  		// FIPS 186-5, A.1.1(3) requires checking that d > 2^(nlen / 2).
    77  		//
    78  		// The probability of this check failing when d is derived from
    79  		// (e, p, q) is roughly
    80  		//
    81  		//   2^(nlen/2) / 2^nlen = 2^(-nlen/2)
    82  		//
    83  		// so less than 2⁻¹²⁸ for keys larger than 256 bits.
    84  		//
    85  		// We still need to check to comply with FIPS 186-5, but knowing it has
    86  		// negligible chance of failure we can defer the check to the end of key
    87  		// generation and return an error if it fails. See [checkPrivateKey].
    88  
    89  		return newPrivateKey(N, 65537, d, P, Q)
    90  	}
    91  }
    92  
    93  // randomPrime returns a random prime number of the given bit size following
    94  // the process in FIPS 186-5, Appendix A.1.3.
    95  func randomPrime(rand io.Reader, bits int) ([]byte, error) {
    96  	if bits < 16 {
    97  		return nil, errors.New("rsa: prime size must be at least 16 bits")
    98  	}
    99  
   100  	b := make([]byte, (bits+7)/8)
   101  	for {
   102  		if err := drbg.ReadWithReader(rand, b); err != nil {
   103  			return nil, err
   104  		}
   105  		if excess := len(b)*8 - bits; excess != 0 {
   106  			b[0] >>= excess
   107  		}
   108  
   109  		// Don't let the value be too small: set the most significant two bits.
   110  		// Setting the top two bits, rather than just the top bit, means that
   111  		// when two of these values are multiplied together, the result isn't
   112  		// ever one bit short.
   113  		if excess := len(b)*8 - bits; excess < 7 {
   114  			b[0] |= 0b1100_0000 >> excess
   115  		} else {
   116  			b[0] |= 0b0000_0001
   117  			b[1] |= 0b1000_0000
   118  		}
   119  
   120  		// Make the value odd since an even number certainly isn't prime.
   121  		b[len(b)-1] |= 1
   122  
   123  		// We don't need to check for p >= √2 × 2^(bits-1) (steps 4.4 and 5.4)
   124  		// because we set the top two bits above, so
   125  		//
   126  		//   p > 2^(bits-1) + 2^(bits-2) = 3⁄2 × 2^(bits-1) > √2 × 2^(bits-1)
   127  		//
   128  
   129  		// Step 5.5 requires checking that |p - q| > 2^(nlen/2 - 100).
   130  		//
   131  		// The probability of |p - q| ≤ k where p and q are uniformly random in
   132  		// the range (a, b) is 1 - (b-a-k)^2 / (b-a)^2, so the probability of
   133  		// this check failing during key generation is 2⁻⁹⁷.
   134  		//
   135  		// We still need to check to comply with FIPS 186-5, but knowing it has
   136  		// negligible chance of failure we can defer the check to the end of key
   137  		// generation and return an error if it fails. See [checkPrivateKey].
   138  
   139  		if isPrime(b) {
   140  			return b, nil
   141  		}
   142  	}
   143  }
   144  
   145  // isPrime runs the Miller-Rabin Probabilistic Primality Test from
   146  // FIPS 186-5, Appendix B.3.1.
   147  //
   148  // w must be a random odd integer greater than three in big-endian order.
   149  // isPrime might return false positives for adversarially chosen values.
   150  //
   151  // isPrime is not constant-time.
   152  func isPrime(w []byte) bool {
   153  	mr, err := millerRabinSetup(w)
   154  	if err != nil {
   155  		// w is zero, one, or even.
   156  		return false
   157  	}
   158  
   159  	primes, err := bigmod.NewNat().SetBytes(productOfPrimes, mr.w)
   160  	// If w is too small for productOfPrimes, key generation is
   161  	// going to be fast enough anyway.
   162  	if err == nil {
   163  		_, hasInverse := primes.InverseVarTime(primes, mr.w)
   164  		if !hasInverse {
   165  			// productOfPrimes doesn't have an inverse mod w,
   166  			// so w is divisible by at least one of the primes.
   167  			return false
   168  		}
   169  	}
   170  
   171  	// iterations is the number of Miller-Rabin rounds, each with a
   172  	// randomly-selected base.
   173  	//
   174  	// The worst case false positive rate for a single iteration is 1/4 per
   175  	// https://eprint.iacr.org/2018/749, so if w were selected adversarially, we
   176  	// would need up to 64 iterations to get to a negligible (2⁻¹²⁸) chance of
   177  	// false positive.
   178  	//
   179  	// However, since this function is only used for randomly-selected w in the
   180  	// context of RSA key generation, we can use a smaller number of iterations.
   181  	// The exact number depends on the size of the prime (and the implied
   182  	// security level). See BoringSSL for the full formula.
   183  	// https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/prime.c.inc;l=208-283;drc=3a138e43
   184  	bits := mr.w.BitLen()
   185  	var iterations int
   186  	switch {
   187  	case bits >= 3747:
   188  		iterations = 3
   189  	case bits >= 1345:
   190  		iterations = 4
   191  	case bits >= 476:
   192  		iterations = 5
   193  	case bits >= 400:
   194  		iterations = 6
   195  	case bits >= 347:
   196  		iterations = 7
   197  	case bits >= 308:
   198  		iterations = 8
   199  	case bits >= 55:
   200  		iterations = 27
   201  	default:
   202  		iterations = 34
   203  	}
   204  
   205  	b := make([]byte, (bits+7)/8)
   206  	for {
   207  		drbg.Read(b)
   208  		if excess := len(b)*8 - bits; excess != 0 {
   209  			b[0] >>= excess
   210  		}
   211  		result, err := millerRabinIteration(mr, b)
   212  		if err != nil {
   213  			// b was rejected.
   214  			continue
   215  		}
   216  		if result == millerRabinCOMPOSITE {
   217  			return false
   218  		}
   219  		iterations--
   220  		if iterations == 0 {
   221  			return true
   222  		}
   223  	}
   224  }
   225  
   226  // productOfPrimes is the product of the first 74 primes higher than 2.
   227  //
   228  // The number of primes was selected to be the highest such that the product fit
   229  // in 512 bits, so to be usable for 1024 bit RSA keys.
   230  //
   231  // Higher values cause fewer Miller-Rabin tests of composites (nothing can help
   232  // with the final test on the actual prime) but make InverseVarTime take longer.
   233  var productOfPrimes = []byte{
   234  	0x10, 0x6a, 0xa9, 0xfb, 0x76, 0x46, 0xfa, 0x6e, 0xb0, 0x81, 0x3c, 0x28, 0xc5, 0xd5, 0xf0, 0x9f,
   235  	0x07, 0x7e, 0xc3, 0xba, 0x23, 0x8b, 0xfb, 0x99, 0xc1, 0xb6, 0x31, 0xa2, 0x03, 0xe8, 0x11, 0x87,
   236  	0x23, 0x3d, 0xb1, 0x17, 0xcb, 0xc3, 0x84, 0x05, 0x6e, 0xf0, 0x46, 0x59, 0xa4, 0xa1, 0x1d, 0xe4,
   237  	0x9f, 0x7e, 0xcb, 0x29, 0xba, 0xda, 0x8f, 0x98, 0x0d, 0xec, 0xec, 0xe9, 0x2e, 0x30, 0xc4, 0x8f,
   238  }
   239  
   240  type millerRabin struct {
   241  	w *bigmod.Modulus
   242  	a uint
   243  	m []byte
   244  }
   245  
   246  // millerRabinSetup prepares state that's reused across multiple iterations of
   247  // the Miller-Rabin test.
   248  func millerRabinSetup(w []byte) (*millerRabin, error) {
   249  	mr := &millerRabin{}
   250  
   251  	// Check that w is odd, and precompute Montgomery parameters.
   252  	wm, err := bigmod.NewModulus(w)
   253  	if err != nil {
   254  		return nil, err
   255  	}
   256  	if wm.Nat().IsOdd() == 0 {
   257  		return nil, errors.New("candidate is even")
   258  	}
   259  	mr.w = wm
   260  
   261  	// Compute m = (w-1)/2^a, where m is odd.
   262  	wMinus1 := mr.w.Nat().SubOne(mr.w)
   263  	if wMinus1.IsZero() == 1 {
   264  		return nil, errors.New("candidate is one")
   265  	}
   266  	mr.a = wMinus1.TrailingZeroBitsVarTime()
   267  
   268  	// Store mr.m as a big-endian byte slice with leading zero bytes removed,
   269  	// for use with [bigmod.Nat.Exp].
   270  	m := wMinus1.ShiftRightVarTime(mr.a)
   271  	mr.m = m.Bytes(mr.w)
   272  	for mr.m[0] == 0 {
   273  		mr.m = mr.m[1:]
   274  	}
   275  
   276  	return mr, nil
   277  }
   278  
   279  const millerRabinCOMPOSITE = false
   280  const millerRabinPOSSIBLYPRIME = true
   281  
   282  func millerRabinIteration(mr *millerRabin, bb []byte) (bool, error) {
   283  	// Reject b ≤ 1 or b ≥ w − 1.
   284  	if len(bb) != (mr.w.BitLen()+7)/8 {
   285  		return false, errors.New("incorrect length")
   286  	}
   287  	b := bigmod.NewNat()
   288  	if _, err := b.SetBytes(bb, mr.w); err != nil {
   289  		return false, err
   290  	}
   291  	if b.IsZero() == 1 || b.IsOne() == 1 || b.IsMinusOne(mr.w) == 1 {
   292  		return false, errors.New("out-of-range candidate")
   293  	}
   294  
   295  	// Compute b^(m*2^i) mod w for successive i.
   296  	// If b^m mod w = 1, b is a possible prime.
   297  	// If b^(m*2^i) mod w = -1 for some 0 <= i < a, b is a possible prime.
   298  	// Otherwise b is composite.
   299  
   300  	// Start by computing and checking b^m mod w (also the i = 0 case).
   301  	z := bigmod.NewNat().Exp(b, mr.m, mr.w)
   302  	if z.IsOne() == 1 || z.IsMinusOne(mr.w) == 1 {
   303  		return millerRabinPOSSIBLYPRIME, nil
   304  	}
   305  
   306  	// Check b^(m*2^i) mod w = -1 for 0 < i < a.
   307  	for range mr.a - 1 {
   308  		z.Mul(z, mr.w)
   309  		if z.IsMinusOne(mr.w) == 1 {
   310  			return millerRabinPOSSIBLYPRIME, nil
   311  		}
   312  		if z.IsOne() == 1 {
   313  			// Future squaring will not turn z == 1 into -1.
   314  			break
   315  		}
   316  	}
   317  
   318  	return millerRabinCOMPOSITE, nil
   319  }
   320
View as plain text