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 := []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 := []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