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) = λ(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.
   237  	pMinus1, err := bigmod.NewModulus(p.Nat().SubOne(p).Bytes(p))
   238  	if err != nil {
   239  		return errors.New("crypto/rsa: invalid prime")
   240  	}
   241  	dP, err := bigmod.NewNat().SetBytes(priv.dP, pMinus1)
   242  	if err != nil {
   243  		return errors.New("crypto/rsa: invalid CRT exponent")
   244  	}
   245  	de := bigmod.NewNat()
   246  	de.SetUint(uint(priv.pub.E)).ExpandFor(pMinus1)
   247  	de.Mul(dP, pMinus1)
   248  	if de.IsOne() != 1 {
   249  		return errors.New("crypto/rsa: invalid CRT exponent")
   250  	}
   251  
   252  	qMinus1, err := bigmod.NewModulus(q.Nat().SubOne(q).Bytes(q))
   253  	if err != nil {
   254  		return errors.New("crypto/rsa: invalid prime")
   255  	}
   256  	dQ, err := bigmod.NewNat().SetBytes(priv.dQ, qMinus1)
   257  	if err != nil {
   258  		return errors.New("crypto/rsa: invalid CRT exponent")
   259  	}
   260  	de.SetUint(uint(priv.pub.E)).ExpandFor(qMinus1)
   261  	de.Mul(dQ, qMinus1)
   262  	if de.IsOne() != 1 {
   263  		return errors.New("crypto/rsa: invalid CRT exponent")
   264  	}
   265  
   266  	// Check that qInv * q ≡ 1 mod p.
   267  	qP, err := bigmod.NewNat().SetOverflowingBytes(q.Nat().Bytes(q), p)
   268  	if err != nil {
   269  		// q >= 2^⌈log2(p)⌉
   270  		qP = bigmod.NewNat().Mod(q.Nat(), p)
   271  	}
   272  	if qP.Mul(priv.qInv, p).IsOne() != 1 {
   273  		return errors.New("crypto/rsa: invalid CRT coefficient")
   274  	}
   275  
   276  	// Check d against dP and dQ, even though we never actually use d,
   277  	// to make sure the key is consistent.
   278  	dP1 := bigmod.NewNat().Mod(priv.d, pMinus1)
   279  	if dP1.Equal(dP) != 1 {
   280  		return errors.New("crypto/rsa: d does not match dP")
   281  	}
   282  	dQ1 := bigmod.NewNat().Mod(priv.d, qMinus1)
   283  	if dQ1.Equal(dQ) != 1 {
   284  		return errors.New("crypto/rsa: d does not match dQ")
   285  	}
   286  
   287  	// Check that |p - q| > 2^(nlen/2 - 100).
   288  	//
   289  	// If p and q are very close to each other, then N=pq can be trivially
   290  	// factored using Fermat's factorization method. Broken RSA implementations
   291  	// do generate such keys. See Hanno Böck, Fermat Factorization in the Wild,
   292  	// https://eprint.iacr.org/2023/026.pdf.
   293  	diff := bigmod.NewNat()
   294  	if qP, err := bigmod.NewNat().SetBytes(q.Nat().Bytes(q), p); err != nil {
   295  		// q > p
   296  		pQ, err := bigmod.NewNat().SetBytes(p.Nat().Bytes(p), q)
   297  		if err != nil {
   298  			return errors.New("crypto/rsa: p == q")
   299  		}
   300  		// diff = 0 - p mod q = q - p
   301  		diff.ExpandFor(q).Sub(pQ, q)
   302  	} else {
   303  		// p > q
   304  		// diff = 0 - q mod p = p - q
   305  		diff.ExpandFor(p).Sub(qP, p)
   306  	}
   307  	// A tiny bit of leakage is acceptable because it's not adaptive, an
   308  	// attacker only learns the magnitude of p - q.
   309  	if diff.BitLenVarTime() <= N.BitLen()/2-100 {
   310  		return errors.New("crypto/rsa: |p - q| too small")
   311  	}
   312  
   313  	// Check that d > 2^(nlen/2).
   314  	//
   315  	// See section 3 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
   316  	// for more details about attacks on small d values.
   317  	//
   318  	// Likewise, the leakage of the magnitude of d is not adaptive.
   319  	if priv.d.BitLenVarTime() <= N.BitLen()/2 {
   320  		return errors.New("crypto/rsa: d too small")
   321  	}
   322  
   323  	// If the key is still in scope for FIPS mode, perform a Pairwise
   324  	// Consistency Test.
   325  	if priv.fipsApproved {
   326  		if err := fips140.PCT("RSA sign and verify PCT", func() error {
   327  			hash := []byte{
   328  				0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
   329  				0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10,
   330  				0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
   331  				0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
   332  			}
   333  			sig, err := signPKCS1v15(priv, "SHA-256", hash)
   334  			if err != nil {
   335  				return err
   336  			}
   337  			return verifyPKCS1v15(priv.PublicKey(), "SHA-256", hash, sig)
   338  		}); err != nil {
   339  			return err
   340  		}
   341  	}
   342  
   343  	return nil
   344  }
   345  
   346  func checkPublicKey(pub *PublicKey) (fipsApproved bool, err error) {
   347  	fipsApproved = true
   348  	if pub.N == nil {
   349  		return false, errors.New("crypto/rsa: missing public modulus")
   350  	}
   351  	if pub.N.Nat().IsOdd() == 0 {
   352  		return false, errors.New("crypto/rsa: public modulus is even")
   353  	}
   354  	// FIPS 186-5, Section 5.1: "This standard specifies the use of a modulus
   355  	// whose bit length is an even integer and greater than or equal to 2048
   356  	// bits."
   357  	if pub.N.BitLen() < 2048 {
   358  		fipsApproved = false
   359  	}
   360  	if pub.N.BitLen()%2 == 1 {
   361  		fipsApproved = false
   362  	}
   363  	if pub.E < 2 {
   364  		return false, errors.New("crypto/rsa: public exponent too small or negative")
   365  	}
   366  	// e needs to be coprime with p-1 and q-1, since it must be invertible
   367  	// modulo λ(pq). Since p and q are prime, this means e needs to be odd.
   368  	if pub.E&1 == 0 {
   369  		return false, errors.New("crypto/rsa: public exponent is even")
   370  	}
   371  	// FIPS 186-5, Section 5.5(e): "The exponent e shall be an odd, positive
   372  	// integer such that 2¹⁶ < e < 2²⁵⁶."
   373  	if pub.E <= 1<<16 {
   374  		fipsApproved = false
   375  	}
   376  	// We require pub.E to fit into a 32-bit integer so that we
   377  	// do not have different behavior depending on whether
   378  	// int is 32 or 64 bits. See also
   379  	// https://www.imperialviolet.org/2012/03/16/rsae.html.
   380  	if pub.E > 1<<31-1 {
   381  		return false, errors.New("crypto/rsa: public exponent too large")
   382  	}
   383  	return fipsApproved, nil
   384  }
   385  
   386  // Encrypt performs the RSA public key operation.
   387  func Encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
   388  	fips140.RecordNonApproved()
   389  	if _, err := checkPublicKey(pub); err != nil {
   390  		return nil, err
   391  	}
   392  	return encrypt(pub, plaintext)
   393  }
   394  
   395  func encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
   396  	m, err := bigmod.NewNat().SetBytes(plaintext, pub.N)
   397  	if err != nil {
   398  		return nil, err
   399  	}
   400  	return bigmod.NewNat().ExpShortVarTime(m, uint(pub.E), pub.N).Bytes(pub.N), nil
   401  }
   402  
   403  var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA key size")
   404  var ErrDecryption = errors.New("crypto/rsa: decryption error")
   405  var ErrVerification = errors.New("crypto/rsa: verification error")
   406  
   407  const withCheck = true
   408  const noCheck = false
   409  
   410  // DecryptWithoutCheck performs the RSA private key operation.
   411  func DecryptWithoutCheck(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
   412  	fips140.RecordNonApproved()
   413  	return decrypt(priv, ciphertext, noCheck)
   414  }
   415  
   416  // DecryptWithCheck performs the RSA private key operation and checks the
   417  // result to defend against errors in the CRT computation.
   418  func DecryptWithCheck(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
   419  	fips140.RecordNonApproved()
   420  	return decrypt(priv, ciphertext, withCheck)
   421  }
   422  
   423  // decrypt performs an RSA decryption of ciphertext into out. If check is true,
   424  // m^e is calculated and compared with ciphertext, in order to defend against
   425  // errors in the CRT computation.
   426  func decrypt(priv *PrivateKey, ciphertext []byte, check bool) ([]byte, error) {
   427  	if !priv.fipsApproved {
   428  		fips140.RecordNonApproved()
   429  	}
   430  
   431  	var m *bigmod.Nat
   432  	N, E := priv.pub.N, priv.pub.E
   433  
   434  	c, err := bigmod.NewNat().SetBytes(ciphertext, N)
   435  	if err != nil {
   436  		return nil, ErrDecryption
   437  	}
   438  
   439  	if priv.dP == nil {
   440  		// Legacy codepath for deprecated multi-prime keys.
   441  		fips140.RecordNonApproved()
   442  		m = bigmod.NewNat().Exp(c, priv.d.Bytes(N), N)
   443  
   444  	} else {
   445  		P, Q := priv.p, priv.q
   446  		t0 := bigmod.NewNat()
   447  		// m = c ^ Dp mod p
   448  		m = bigmod.NewNat().Exp(t0.Mod(c, P), priv.dP, P)
   449  		// m2 = c ^ Dq mod q
   450  		m2 := bigmod.NewNat().Exp(t0.Mod(c, Q), priv.dQ, Q)
   451  		// m = m - m2 mod p
   452  		m.Sub(t0.Mod(m2, P), P)
   453  		// m = m * Qinv mod p
   454  		m.Mul(priv.qInv, P)
   455  		// m = m * q mod N
   456  		m.ExpandFor(N).Mul(t0.Mod(Q.Nat(), N), N)
   457  		// m = m + m2 mod N
   458  		m.Add(m2.ExpandFor(N), N)
   459  	}
   460  
   461  	if check {
   462  		c1 := bigmod.NewNat().ExpShortVarTime(m, uint(E), N)
   463  		if c1.Equal(c) != 1 {
   464  			return nil, ErrDecryption
   465  		}
   466  	}
   467  
   468  	return m.Bytes(N), nil
   469  }
   470
View as plain text