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