rsa.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  	"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,r-1,...) = exponent(ℤ/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  	// If the key is still in scope for FIPS mode, perform a Pairwise
   314  	// Consistency Test.
   315  	if priv.fipsApproved {
   316  		if err := fips140.PCT("RSA sign and verify PCT", func() error {
   317  			hash := []byte{
   318  				0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
   319  				0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10,
   320  				0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
   321  				0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
   322  			}
   323  			sig, err := signPKCS1v15(priv, "SHA-256", hash)
   324  			if err != nil {
   325  				return err
   326  			}
   327  			return verifyPKCS1v15(priv.PublicKey(), "SHA-256", hash, sig)
   328  		}); err != nil {
   329  			return err
   330  		}
   331  	}
   332  
   333  	return nil
   334  }
   335  
   336  func checkPublicKey(pub *PublicKey) (fipsApproved bool, err error) {
   337  	fipsApproved = true
   338  	if pub.N == nil {
   339  		return false, errors.New("crypto/rsa: missing public modulus")
   340  	}
   341  	if pub.N.Nat().IsOdd() == 0 {
   342  		return false, errors.New("crypto/rsa: public modulus is even")
   343  	}
   344  	// FIPS 186-5, Section 5.1: "This standard specifies the use of a modulus
   345  	// whose bit length is an even integer and greater than or equal to 2048
   346  	// bits."
   347  	if pub.N.BitLen() < 2048 {
   348  		fipsApproved = false
   349  	}
   350  	if pub.N.BitLen()%2 == 1 {
   351  		fipsApproved = false
   352  	}
   353  	if pub.E < 2 {
   354  		return false, errors.New("crypto/rsa: public exponent too small or negative")
   355  	}
   356  	// e needs to be coprime with p-1 and q-1, since it must be invertible
   357  	// modulo λ(pq). Since p and q are prime, this means e needs to be odd.
   358  	if pub.E&1 == 0 {
   359  		return false, errors.New("crypto/rsa: public exponent is even")
   360  	}
   361  	// FIPS 186-5, Section 5.5(e): "The exponent e shall be an odd, positive
   362  	// integer such that 2¹⁶ < e < 2²⁵⁶."
   363  	if pub.E <= 1<<16 {
   364  		fipsApproved = false
   365  	}
   366  	// We require pub.E to fit into a 32-bit integer so that we
   367  	// do not have different behavior depending on whether
   368  	// int is 32 or 64 bits. See also
   369  	// https://www.imperialviolet.org/2012/03/16/rsae.html.
   370  	if pub.E > 1<<31-1 {
   371  		return false, errors.New("crypto/rsa: public exponent too large")
   372  	}
   373  	return fipsApproved, nil
   374  }
   375  
   376  // Encrypt performs the RSA public key operation.
   377  func Encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
   378  	fips140.RecordNonApproved()
   379  	if _, err := checkPublicKey(pub); err != nil {
   380  		return nil, err
   381  	}
   382  	return encrypt(pub, plaintext)
   383  }
   384  
   385  func encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
   386  	m, err := bigmod.NewNat().SetBytes(plaintext, pub.N)
   387  	if err != nil {
   388  		return nil, err
   389  	}
   390  	return bigmod.NewNat().ExpShortVarTime(m, uint(pub.E), pub.N).Bytes(pub.N), nil
   391  }
   392  
   393  var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA key size")
   394  var ErrDecryption = errors.New("crypto/rsa: decryption error")
   395  var ErrVerification = errors.New("crypto/rsa: verification error")
   396  
   397  const withCheck = true
   398  const noCheck = false
   399  
   400  // DecryptWithoutCheck performs the RSA private key operation.
   401  func DecryptWithoutCheck(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
   402  	fips140.RecordNonApproved()
   403  	return decrypt(priv, ciphertext, noCheck)
   404  }
   405  
   406  // DecryptWithCheck performs the RSA private key operation and checks the
   407  // result to defend against errors in the CRT computation.
   408  func DecryptWithCheck(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
   409  	fips140.RecordNonApproved()
   410  	return decrypt(priv, ciphertext, withCheck)
   411  }
   412  
   413  // decrypt performs an RSA decryption of ciphertext into out. If check is true,
   414  // m^e is calculated and compared with ciphertext, in order to defend against
   415  // errors in the CRT computation.
   416  func decrypt(priv *PrivateKey, ciphertext []byte, check bool) ([]byte, error) {
   417  	if !priv.fipsApproved {
   418  		fips140.RecordNonApproved()
   419  	}
   420  
   421  	var m *bigmod.Nat
   422  	N, E := priv.pub.N, priv.pub.E
   423  
   424  	c, err := bigmod.NewNat().SetBytes(ciphertext, N)
   425  	if err != nil {
   426  		return nil, ErrDecryption
   427  	}
   428  
   429  	if priv.dP == nil {
   430  		// Legacy codepath for deprecated multi-prime keys.
   431  		fips140.RecordNonApproved()
   432  		m = bigmod.NewNat().Exp(c, priv.d.Bytes(N), N)
   433  
   434  	} else {
   435  		P, Q := priv.p, priv.q
   436  		t0 := bigmod.NewNat()
   437  		// m = c ^ Dp mod p
   438  		m = bigmod.NewNat().Exp(t0.Mod(c, P), priv.dP, P)
   439  		// m2 = c ^ Dq mod q
   440  		m2 := bigmod.NewNat().Exp(t0.Mod(c, Q), priv.dQ, Q)
   441  		// m = m - m2 mod p
   442  		m.Sub(t0.Mod(m2, P), P)
   443  		// m = m * Qinv mod p
   444  		m.Mul(priv.qInv, P)
   445  		// m = m * q mod N
   446  		m.ExpandFor(N).Mul(t0.Mod(Q.Nat(), N), N)
   447  		// m = m + m2 mod N
   448  		m.Add(m2.ExpandFor(N), N)
   449  	}
   450  
   451  	if check {
   452  		c1 := bigmod.NewNat().ExpShortVarTime(m, uint(E), N)
   453  		if c1.Equal(c) != 1 {
   454  			return nil, ErrDecryption
   455  		}
   456  	}
   457  
   458  	return m.Bytes(N), nil
   459  }
   460
View as plain text