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 "bytes"
9 "crypto/internal/fips140"
10 "crypto/internal/fips140/bigmod"
11 "errors"
12 )
13 14 type PublicKey struct {
15 N *bigmod.Modulus
16 E int
17 }
18 19 // Size returns the modulus size in bytes. Raw signatures and ciphertexts
20 // for or by this public key will have the same size.
21 func (pub *PublicKey) Size() int {
22 return (pub.N.BitLen() + 7) / 8
23 }
24 25 type PrivateKey struct {
26 // pub has already been checked with checkPublicKey.
27 pub PublicKey
28 d *bigmod.Nat
29 // The following values are not set for deprecated multi-prime keys.
30 //
31 // Since they are always set for keys in FIPS mode, for SP 800-56B Rev. 2
32 // purposes we always use the Chinese Remainder Theorem (CRT) format.
33 p, q *bigmod.Modulus // p × q = n
34 // dP and dQ are used as exponents, so we store them as big-endian byte
35 // slices to be passed to [bigmod.Nat.Exp].
36 dP []byte // d mod (p - 1)
37 dQ []byte // d mod (q - 1)
38 qInv *bigmod.Nat // qInv = q⁻¹ mod p
39 // fipsApproved is false if this key does not comply with FIPS 186-5 or
40 // SP 800-56B Rev. 2.
41 fipsApproved bool
42 }
43 44 func (priv *PrivateKey) PublicKey() *PublicKey {
45 return &priv.pub
46 }
47 48 // NewPrivateKey creates a new RSA private key from the given parameters.
49 //
50 // All values are in big-endian byte slice format, and may have leading zeros
51 // or be shorter if leading zeroes were trimmed.
52 func NewPrivateKey(N []byte, e int, d, P, Q []byte) (*PrivateKey, error) {
53 n, err := bigmod.NewModulus(N)
54 if err != nil {
55 return nil, err
56 }
57 p, err := bigmod.NewModulus(P)
58 if err != nil {
59 return nil, err
60 }
61 q, err := bigmod.NewModulus(Q)
62 if err != nil {
63 return nil, err
64 }
65 dN, err := bigmod.NewNat().SetBytes(d, n)
66 if err != nil {
67 return nil, err
68 }
69 return newPrivateKey(n, e, dN, p, q)
70 }
71 72 func newPrivateKey(n *bigmod.Modulus, e int, d *bigmod.Nat, p, q *bigmod.Modulus) (*PrivateKey, error) {
73 pMinusOne := p.Nat().SubOne(p)
74 pMinusOneMod, err := bigmod.NewModulus(pMinusOne.Bytes(p))
75 if err != nil {
76 return nil, err
77 }
78 dP := bigmod.NewNat().Mod(d, pMinusOneMod).Bytes(pMinusOneMod)
79 80 qMinusOne := q.Nat().SubOne(q)
81 qMinusOneMod, err := bigmod.NewModulus(qMinusOne.Bytes(q))
82 if err != nil {
83 return nil, err
84 }
85 dQ := bigmod.NewNat().Mod(d, qMinusOneMod).Bytes(qMinusOneMod)
86 87 // Constant-time modular inversion with prime modulus by Fermat's Little
88 // Theorem: qInv = q⁻¹ mod p = q^(p-2) mod p.
89 if p.Nat().IsOdd() == 0 {
90 // [bigmod.Nat.Exp] requires an odd modulus.
91 return nil, errors.New("crypto/rsa: p is even")
92 }
93 pMinusTwo := p.Nat().SubOne(p).SubOne(p).Bytes(p)
94 qInv := bigmod.NewNat().Mod(q.Nat(), p)
95 qInv.Exp(qInv, pMinusTwo, p)
96 97 pk := &PrivateKey{
98 pub: PublicKey{
99 N: n, E: e,
100 },
101 d: d, p: p, q: q,
102 dP: dP, dQ: dQ, qInv: qInv,
103 }
104 if err := checkPrivateKey(pk); err != nil {
105 return nil, err
106 }
107 return pk, nil
108 }
109 110 // NewPrivateKeyWithPrecomputation creates a new RSA private key from the given
111 // parameters, which include precomputed CRT values.
112 func NewPrivateKeyWithPrecomputation(N []byte, e int, d, P, Q, dP, dQ, qInv []byte) (*PrivateKey, error) {
113 n, err := bigmod.NewModulus(N)
114 if err != nil {
115 return nil, err
116 }
117 p, err := bigmod.NewModulus(P)
118 if err != nil {
119 return nil, err
120 }
121 q, err := bigmod.NewModulus(Q)
122 if err != nil {
123 return nil, err
124 }
125 dN, err := bigmod.NewNat().SetBytes(d, n)
126 if err != nil {
127 return nil, err
128 }
129 qInvNat, err := bigmod.NewNat().SetBytes(qInv, p)
130 if err != nil {
131 return nil, err
132 }
133 134 pk := &PrivateKey{
135 pub: PublicKey{
136 N: n, E: e,
137 },
138 d: dN, p: p, q: q,
139 dP: dP, dQ: dQ, qInv: qInvNat,
140 }
141 if err := checkPrivateKey(pk); err != nil {
142 return nil, err
143 }
144 return pk, nil
145 }
146 147 // NewPrivateKeyWithoutCRT creates a new RSA private key from the given parameters.
148 //
149 // This is meant for deprecated multi-prime keys, and is not FIPS 140 compliant.
150 func NewPrivateKeyWithoutCRT(N []byte, e int, d []byte) (*PrivateKey, error) {
151 n, err := bigmod.NewModulus(N)
152 if err != nil {
153 return nil, err
154 }
155 dN, err := bigmod.NewNat().SetBytes(d, n)
156 if err != nil {
157 return nil, err
158 }
159 pk := &PrivateKey{
160 pub: PublicKey{
161 N: n, E: e,
162 },
163 d: dN,
164 }
165 if err := checkPrivateKey(pk); err != nil {
166 return nil, err
167 }
168 return pk, nil
169 }
170 171 // Export returns the key parameters in big-endian byte slice format.
172 //
173 // P, Q, dP, dQ, and qInv may be nil if the key was created with
174 // NewPrivateKeyWithoutCRT.
175 func (priv *PrivateKey) Export() (N []byte, e int, d, P, Q, dP, dQ, qInv []byte) {
176 N = priv.pub.N.Nat().Bytes(priv.pub.N)
177 e = priv.pub.E
178 d = priv.d.Bytes(priv.pub.N)
179 if priv.dP == nil {
180 return
181 }
182 P = priv.p.Nat().Bytes(priv.p)
183 Q = priv.q.Nat().Bytes(priv.q)
184 dP = bytes.Clone(priv.dP)
185 dQ = bytes.Clone(priv.dQ)
186 qInv = priv.qInv.Bytes(priv.p)
187 return
188 }
189 190 // checkPrivateKey is called by the NewPrivateKey and GenerateKey functions, and
191 // is allowed to modify priv.fipsApproved.
192 func checkPrivateKey(priv *PrivateKey) error {
193 priv.fipsApproved = true
194 195 if fipsApproved, err := checkPublicKey(&priv.pub); err != nil {
196 return err
197 } else if !fipsApproved {
198 priv.fipsApproved = false
199 }
200 201 if priv.dP == nil {
202 // Legacy and deprecated multi-prime keys.
203 priv.fipsApproved = false
204 return nil
205 }
206 207 N := priv.pub.N
208 p := priv.p
209 q := priv.q
210 211 // FIPS 186-5, Section 5.1 requires "that p and q be of the same bit length."
212 if p.BitLen() != q.BitLen() {
213 priv.fipsApproved = false
214 }
215 216 // Check that pq ≡ 1 mod N (and that p < N and q < N).
217 pN := bigmod.NewNat().ExpandFor(N)
218 if _, err := pN.SetBytes(p.Nat().Bytes(p), N); err != nil {
219 return errors.New("crypto/rsa: invalid prime")
220 }
221 qN := bigmod.NewNat().ExpandFor(N)
222 if _, err := qN.SetBytes(q.Nat().Bytes(q), N); err != nil {
223 return errors.New("crypto/rsa: invalid prime")
224 }
225 if pN.Mul(qN, N).IsZero() != 1 {
226 return errors.New("crypto/rsa: p * q != n")
227 }
228 229 // Check that de ≡ 1 mod p-1, and de ≡ 1 mod q-1.
230 //
231 // This implies that e is coprime to each p-1 as e has a multiplicative
232 // inverse. Therefore e is coprime to lcm(p-1,q-1) = λ(N).
233 // It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1 mod p. Thus a^de ≡ a
234 // mod n for all a coprime to n, as required.
235 //
236 // This checks dP, dQ, and e. We don't check d because it is not actually
237 // used in the RSA private key operation.
238 pMinus1, err := bigmod.NewModulus(p.Nat().SubOne(p).Bytes(p))
239 if err != nil {
240 return errors.New("crypto/rsa: invalid prime")
241 }
242 dP, err := bigmod.NewNat().SetBytes(priv.dP, pMinus1)
243 if err != nil {
244 return errors.New("crypto/rsa: invalid CRT exponent")
245 }
246 de := bigmod.NewNat()
247 de.SetUint(uint(priv.pub.E)).ExpandFor(pMinus1)
248 de.Mul(dP, pMinus1)
249 if de.IsOne() != 1 {
250 return errors.New("crypto/rsa: invalid CRT exponent")
251 }
252 253 qMinus1, err := bigmod.NewModulus(q.Nat().SubOne(q).Bytes(q))
254 if err != nil {
255 return errors.New("crypto/rsa: invalid prime")
256 }
257 dQ, err := bigmod.NewNat().SetBytes(priv.dQ, qMinus1)
258 if err != nil {
259 return errors.New("crypto/rsa: invalid CRT exponent")
260 }
261 de.SetUint(uint(priv.pub.E)).ExpandFor(qMinus1)
262 de.Mul(dQ, qMinus1)
263 if de.IsOne() != 1 {
264 return errors.New("crypto/rsa: invalid CRT exponent")
265 }
266 267 // Check that qInv * q ≡ 1 mod p.
268 qP, err := bigmod.NewNat().SetOverflowingBytes(q.Nat().Bytes(q), p)
269 if err != nil {
270 // q >= 2^⌈log2(p)⌉
271 qP = bigmod.NewNat().Mod(q.Nat(), p)
272 }
273 if qP.Mul(priv.qInv, p).IsOne() != 1 {
274 return errors.New("crypto/rsa: invalid CRT coefficient")
275 }
276 277 // Check that |p - q| > 2^(nlen/2 - 100).
278 //
279 // If p and q are very close to each other, then N=pq can be trivially
280 // factored using Fermat's factorization method. Broken RSA implementations
281 // do generate such keys. See Hanno Böck, Fermat Factorization in the Wild,
282 // https://eprint.iacr.org/2023/026.pdf.
283 diff := bigmod.NewNat()
284 if qP, err := bigmod.NewNat().SetBytes(q.Nat().Bytes(q), p); err != nil {
285 // q > p
286 pQ, err := bigmod.NewNat().SetBytes(p.Nat().Bytes(p), q)
287 if err != nil {
288 return errors.New("crypto/rsa: p == q")
289 }
290 // diff = 0 - p mod q = q - p
291 diff.ExpandFor(q).Sub(pQ, q)
292 } else {
293 // p > q
294 // diff = 0 - q mod p = p - q
295 diff.ExpandFor(p).Sub(qP, p)
296 }
297 // A tiny bit of leakage is acceptable because it's not adaptive, an
298 // attacker only learns the magnitude of p - q.
299 if diff.BitLenVarTime() <= N.BitLen()/2-100 {
300 return errors.New("crypto/rsa: |p - q| too small")
301 }
302 303 // Check that d > 2^(nlen/2).
304 //
305 // See section 3 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
306 // for more details about attacks on small d values.
307 //
308 // Likewise, the leakage of the magnitude of d is not adaptive.
309 if priv.d.BitLenVarTime() <= N.BitLen()/2 {
310 return errors.New("crypto/rsa: d too small")
311 }
312 313 return nil
314 }
315 316 func checkPublicKey(pub *PublicKey) (fipsApproved bool, err error) {
317 fipsApproved = true
318 if pub.N == nil {
319 return false, errors.New("crypto/rsa: missing public modulus")
320 }
321 if pub.N.Nat().IsOdd() == 0 {
322 return false, errors.New("crypto/rsa: public modulus is even")
323 }
324 // FIPS 186-5, Section 5.1: "This standard specifies the use of a modulus
325 // whose bit length is an even integer and greater than or equal to 2048
326 // bits."
327 if pub.N.BitLen() < 2048 {
328 fipsApproved = false
329 }
330 if pub.N.BitLen()%2 == 1 {
331 fipsApproved = false
332 }
333 if pub.E < 2 {
334 return false, errors.New("crypto/rsa: public exponent too small or negative")
335 }
336 // e needs to be coprime with p-1 and q-1, since it must be invertible
337 // modulo λ(pq). Since p and q are prime, this means e needs to be odd.
338 if pub.E&1 == 0 {
339 return false, errors.New("crypto/rsa: public exponent is even")
340 }
341 // FIPS 186-5, Section 5.5(e): "The exponent e shall be an odd, positive
342 // integer such that 2¹⁶ < e < 2²⁵⁶."
343 if pub.E <= 1<<16 {
344 fipsApproved = false
345 }
346 // We require pub.E to fit into a 32-bit integer so that we
347 // do not have different behavior depending on whether
348 // int is 32 or 64 bits. See also
349 // https://www.imperialviolet.org/2012/03/16/rsae.html.
350 if pub.E > 1<<31-1 {
351 return false, errors.New("crypto/rsa: public exponent too large")
352 }
353 return fipsApproved, nil
354 }
355 356 // Encrypt performs the RSA public key operation.
357 func Encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
358 fips140.RecordNonApproved()
359 if _, err := checkPublicKey(pub); err != nil {
360 return nil, err
361 }
362 return encrypt(pub, plaintext)
363 }
364 365 func encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
366 m, err := bigmod.NewNat().SetBytes(plaintext, pub.N)
367 if err != nil {
368 return nil, err
369 }
370 return bigmod.NewNat().ExpShortVarTime(m, uint(pub.E), pub.N).Bytes(pub.N), nil
371 }
372 373 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA key size")
374 var ErrDecryption = errors.New("crypto/rsa: decryption error")
375 var ErrVerification = errors.New("crypto/rsa: verification error")
376 377 const withCheck = true
378 const noCheck = false
379 380 // DecryptWithoutCheck performs the RSA private key operation.
381 func DecryptWithoutCheck(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
382 fips140.RecordNonApproved()
383 return decrypt(priv, ciphertext, noCheck)
384 }
385 386 // DecryptWithCheck performs the RSA private key operation and checks the
387 // result to defend against errors in the CRT computation.
388 func DecryptWithCheck(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
389 fips140.RecordNonApproved()
390 return decrypt(priv, ciphertext, withCheck)
391 }
392 393 // decrypt performs an RSA decryption of ciphertext into out. If check is true,
394 // m^e is calculated and compared with ciphertext, in order to defend against
395 // errors in the CRT computation.
396 func decrypt(priv *PrivateKey, ciphertext []byte, check bool) ([]byte, error) {
397 if !priv.fipsApproved {
398 fips140.RecordNonApproved()
399 }
400 401 var m *bigmod.Nat
402 N, E := priv.pub.N, priv.pub.E
403 404 c, err := bigmod.NewNat().SetBytes(ciphertext, N)
405 if err != nil {
406 return nil, ErrDecryption
407 }
408 409 if priv.dP == nil {
410 // Legacy codepath for deprecated multi-prime keys.
411 fips140.RecordNonApproved()
412 m = bigmod.NewNat().Exp(c, priv.d.Bytes(N), N)
413 414 } else {
415 P, Q := priv.p, priv.q
416 t0 := bigmod.NewNat()
417 // m = c ^ Dp mod p
418 m = bigmod.NewNat().Exp(t0.Mod(c, P), priv.dP, P)
419 // m2 = c ^ Dq mod q
420 m2 := bigmod.NewNat().Exp(t0.Mod(c, Q), priv.dQ, Q)
421 // m = m - m2 mod p
422 m.Sub(t0.Mod(m2, P), P)
423 // m = m * Qinv mod p
424 m.Mul(priv.qInv, P)
425 // m = m * q mod N
426 m.ExpandFor(N).Mul(t0.Mod(Q.Nat(), N), N)
427 // m = m + m2 mod N
428 m.Add(m2.ExpandFor(N), N)
429 }
430 431 if check {
432 c1 := bigmod.NewNat().ExpShortVarTime(m, uint(E), N)
433 if c1.Equal(c) != 1 {
434 return nil, ErrDecryption
435 }
436 }
437 438 return m.Bytes(N), nil
439 }
440