largeexponent.go

     1  // Copyright 2026 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/constanttime"
    10  	"crypto/internal/fips140"
    11  	"crypto/internal/fips140/bigmod"
    12  	"crypto/internal/fips140/drbg"
    13  	"crypto/internal/fips140/subtle"
    14  	"errors"
    15  	"hash"
    16  	"io"
    17  )
    18  
    19  // TestingOnlyLargeExponentPublicKey is a variant of [PublicKey] that supports
    20  // large public exponents. It is only meant for supporting the full ACVP test
    21  // suite, which unfortunately forces us to choose between a fixed exponent and
    22  // the full (2¹⁶, 2²⁵⁶) range. This type must not be used in production code,
    23  // nor for e values < 2³¹, which instead must use [PublicKey].
    24  type TestingOnlyLargeExponentPublicKey struct {
    25  	N *bigmod.Modulus
    26  	// E is the public exponent, represented as a big-endian byte slice.
    27  	E []byte
    28  }
    29  
    30  func (pub *TestingOnlyLargeExponentPublicKey) Size() int {
    31  	return (pub.N.BitLen() + 7) / 8
    32  }
    33  
    34  func checkLargeExponentPublicKey(pub *TestingOnlyLargeExponentPublicKey) error {
    35  	if pub.N == nil {
    36  		return errors.New("crypto/rsa: missing public modulus")
    37  	}
    38  	if pub.N.Nat().IsOdd() == 0 {
    39  		return errors.New("crypto/rsa: public modulus is even")
    40  	}
    41  	if pub.N.BitLen() < 2048 {
    42  		return errors.New("crypto/rsa: public modulus too small")
    43  	}
    44  	if pub.N.BitLen()%2 == 1 {
    45  		return errors.New("crypto/rsa: public modulus bit length not even")
    46  	}
    47  	E := pub.E
    48  	for len(E) > 0 && E[0] == 0 {
    49  		E = E[1:]
    50  	}
    51  	if len(E) < 32/8 || (len(E) == 32/8 && E[0] < 0x80) {
    52  		// Exponents less than 2^31 must use [PublicKey].
    53  		return errors.New("crypto/rsa: public exponent too small")
    54  	}
    55  	if len(E) > 256/8 {
    56  		return errors.New("crypto/rsa: public exponent too large")
    57  	}
    58  	if E[len(E)-1]&1 == 0 {
    59  		return errors.New("crypto/rsa: public exponent is even")
    60  	}
    61  	return nil
    62  }
    63  
    64  func encryptLargeExponent(pub *TestingOnlyLargeExponentPublicKey, plaintext []byte) ([]byte, error) {
    65  	m, err := bigmod.NewNat().SetBytes(plaintext, pub.N)
    66  	if err != nil {
    67  		return nil, err
    68  	}
    69  	return bigmod.NewNat().Exp(m, pub.E, pub.N).Bytes(pub.N), nil
    70  }
    71  
    72  func TestingOnlyLargeExponentVerifyPKCS1v15(pub *TestingOnlyLargeExponentPublicKey, hash string, hashed []byte, sig []byte) error {
    73  	fipsSelfTest()
    74  	fips140.RecordApproved()
    75  	checkApprovedHashName(hash)
    76  	if err := checkLargeExponentPublicKey(pub); err != nil {
    77  		return err
    78  	}
    79  	if pub.Size() != len(sig) {
    80  		return ErrVerification
    81  	}
    82  	em, err := encryptLargeExponent(pub, sig)
    83  	if err != nil {
    84  		return ErrVerification
    85  	}
    86  	expected, err := pkcs1v15ConstructEM(&PublicKey{N: pub.N}, hash, hashed)
    87  	if err != nil {
    88  		return ErrVerification
    89  	}
    90  	if !bytes.Equal(em, expected) {
    91  		return ErrVerification
    92  	}
    93  	return nil
    94  }
    95  
    96  func TestingOnlyLargeExponentVerifyPSS(pub *TestingOnlyLargeExponentPublicKey, hash hash.Hash, digest []byte, sig []byte) error {
    97  	fipsSelfTest()
    98  	fips140.RecordApproved()
    99  	checkApprovedHash(hash)
   100  	if err := checkLargeExponentPublicKey(pub); err != nil {
   101  		return err
   102  	}
   103  	if len(sig) != pub.Size() {
   104  		return ErrVerification
   105  	}
   106  	emBits := pub.N.BitLen() - 1
   107  	emLen := (emBits + 7) / 8
   108  	em, err := encryptLargeExponent(pub, sig)
   109  	if err != nil {
   110  		return ErrVerification
   111  	}
   112  	for len(em) > emLen && len(em) > 0 {
   113  		if em[0] != 0 {
   114  			return ErrVerification
   115  		}
   116  		em = em[1:]
   117  	}
   118  	return emsaPSSVerify(digest, em, emBits, pssSaltLengthAutodetect, hash)
   119  }
   120  
   121  // TestingOnlyLargeExponentPrivateKey is a variant of [PrivateKey] that supports
   122  // large public exponents. It is only meant for supporting the full ACVP test
   123  // suite. This type must not be used in production code.
   124  type TestingOnlyLargeExponentPrivateKey struct {
   125  	n    *bigmod.Modulus
   126  	e    []byte // big-endian public exponent
   127  	d    *bigmod.Nat
   128  	p, q *bigmod.Modulus
   129  	dP   []byte
   130  	dQ   []byte
   131  	qInv *bigmod.Nat
   132  }
   133  
   134  func (priv *TestingOnlyLargeExponentPrivateKey) Size() int {
   135  	return (priv.n.BitLen() + 7) / 8
   136  }
   137  
   138  // TestingOnlyNewLargeExponentPrivateKeyWithPrecomputation creates a new RSA private key
   139  // with a large public exponent from the given parameters. It is only meant for ACVP testing.
   140  func TestingOnlyNewLargeExponentPrivateKeyWithPrecomputation(N []byte, e []byte, d, P, Q, dP, dQ, qInv []byte) (*TestingOnlyLargeExponentPrivateKey, error) {
   141  	n, err := bigmod.NewModulus(N)
   142  	if err != nil {
   143  		return nil, err
   144  	}
   145  	p, err := bigmod.NewModulus(P)
   146  	if err != nil {
   147  		return nil, err
   148  	}
   149  	q, err := bigmod.NewModulus(Q)
   150  	if err != nil {
   151  		return nil, err
   152  	}
   153  	dN, err := bigmod.NewNat().SetBytes(d, n)
   154  	if err != nil {
   155  		return nil, err
   156  	}
   157  	qInvNat, err := bigmod.NewNat().SetBytes(qInv, p)
   158  	if err != nil {
   159  		return nil, err
   160  	}
   161  
   162  	priv := &TestingOnlyLargeExponentPrivateKey{
   163  		n: n, e: e, d: dN, p: p, q: q,
   164  		dP: dP, dQ: dQ, qInv: qInvNat,
   165  	}
   166  	if err := checkLargeExponentPrivateKey(priv); err != nil {
   167  		return nil, err
   168  	}
   169  	return priv, nil
   170  }
   171  
   172  func checkLargeExponentPrivateKey(priv *TestingOnlyLargeExponentPrivateKey) error {
   173  	// Check public key portion.
   174  	pub := &TestingOnlyLargeExponentPublicKey{N: priv.n, E: priv.e}
   175  	if err := checkLargeExponentPublicKey(pub); err != nil {
   176  		return err
   177  	}
   178  
   179  	N := priv.n
   180  	p := priv.p
   181  	q := priv.q
   182  
   183  	// FIPS 186-5, Section 5.1 requires "that p and q be of the same bit length."
   184  	if p.BitLen() != q.BitLen() {
   185  		// We don't enforce this for testing, just note it.
   186  	}
   187  
   188  	// Check that pq ≡ 1 mod N (and that p < N and q < N).
   189  	pN := bigmod.NewNat().ExpandFor(N)
   190  	if _, err := pN.SetBytes(p.Nat().Bytes(p), N); err != nil {
   191  		return errors.New("crypto/rsa: invalid prime")
   192  	}
   193  	qN := bigmod.NewNat().ExpandFor(N)
   194  	if _, err := qN.SetBytes(q.Nat().Bytes(q), N); err != nil {
   195  		return errors.New("crypto/rsa: invalid prime")
   196  	}
   197  	if pN.Mul(qN, N).IsZero() != 1 {
   198  		return errors.New("crypto/rsa: p * q != n")
   199  	}
   200  
   201  	// Check that de ≡ 1 mod p-1, and de ≡ 1 mod q-1.
   202  	// Uses byte-slice exponent for large exponents.
   203  	pMinus1, err := bigmod.NewModulus(p.Nat().SubOne(p).Bytes(p))
   204  	if err != nil {
   205  		return errors.New("crypto/rsa: invalid prime")
   206  	}
   207  	dP, err := bigmod.NewNat().SetBytes(priv.dP, pMinus1)
   208  	if err != nil {
   209  		return errors.New("crypto/rsa: invalid CRT exponent")
   210  	}
   211  	de := bigmod.NewNat()
   212  	if _, err := de.SetBytes(priv.e, pMinus1); err != nil {
   213  		// Exponent might be larger than p-1, reduce it.
   214  		eNat, _ := bigmod.NewNat().SetBytes(priv.e, priv.n)
   215  		de.Mod(eNat, pMinus1)
   216  	}
   217  	de.Mul(dP, pMinus1)
   218  	if de.IsOne() != 1 {
   219  		return errors.New("crypto/rsa: invalid CRT exponent")
   220  	}
   221  
   222  	qMinus1, err := bigmod.NewModulus(q.Nat().SubOne(q).Bytes(q))
   223  	if err != nil {
   224  		return errors.New("crypto/rsa: invalid prime")
   225  	}
   226  	dQ, err := bigmod.NewNat().SetBytes(priv.dQ, qMinus1)
   227  	if err != nil {
   228  		return errors.New("crypto/rsa: invalid CRT exponent")
   229  	}
   230  	if _, err := de.SetBytes(priv.e, qMinus1); err != nil {
   231  		// Exponent might be larger than q-1, reduce it.
   232  		eNat, _ := bigmod.NewNat().SetBytes(priv.e, priv.n)
   233  		de.Mod(eNat, qMinus1)
   234  	}
   235  	de.Mul(dQ, qMinus1)
   236  	if de.IsOne() != 1 {
   237  		return errors.New("crypto/rsa: invalid CRT exponent")
   238  	}
   239  
   240  	// Check that qInv * q ≡ 1 mod p.
   241  	qP, err := bigmod.NewNat().SetOverflowingBytes(q.Nat().Bytes(q), p)
   242  	if err != nil {
   243  		// q >= 2^⌈log2(p)⌉
   244  		qP = bigmod.NewNat().Mod(q.Nat(), p)
   245  	}
   246  	if qP.Mul(priv.qInv, p).IsOne() != 1 {
   247  		return errors.New("crypto/rsa: invalid CRT coefficient")
   248  	}
   249  
   250  	return nil
   251  }
   252  
   253  func decryptLargeExponent(priv *TestingOnlyLargeExponentPrivateKey, ciphertext []byte) ([]byte, error) {
   254  	N := priv.n
   255  	c, err := bigmod.NewNat().SetBytes(ciphertext, N)
   256  	if err != nil {
   257  		return nil, ErrDecryption
   258  	}
   259  
   260  	// CRT-based decryption (same as regular decrypt, doesn't use E).
   261  	P, Q := priv.p, priv.q
   262  	t0 := bigmod.NewNat()
   263  	// m = c ^ Dp mod p
   264  	m := bigmod.NewNat().Exp(t0.Mod(c, P), priv.dP, P)
   265  	// m2 = c ^ Dq mod q
   266  	m2 := bigmod.NewNat().Exp(t0.Mod(c, Q), priv.dQ, Q)
   267  	// m = m - m2 mod p
   268  	m.Sub(t0.Mod(m2, P), P)
   269  	// m = m * Qinv mod p
   270  	m.Mul(priv.qInv, P)
   271  	// m = m * q mod N
   272  	m.ExpandFor(N).Mul(t0.Mod(Q.Nat(), N), N)
   273  	// m = m + m2 mod N
   274  	m.Add(m2.ExpandFor(N), N)
   275  
   276  	return m.Bytes(N), nil
   277  }
   278  
   279  // TestingOnlyLargeExponentDecryptOAEP decrypts ciphertext using RSAES-OAEP with
   280  // a private key that has a large public exponent. It is only meant for ACVP testing.
   281  func TestingOnlyLargeExponentDecryptOAEP(hash, mgfHash hash.Hash, priv *TestingOnlyLargeExponentPrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
   282  	fipsSelfTest()
   283  	fips140.RecordApproved()
   284  	checkApprovedHash(hash)
   285  
   286  	k := priv.Size()
   287  	if len(ciphertext) > k || k < hash.Size()*2+2 {
   288  		return nil, ErrDecryption
   289  	}
   290  
   291  	em, err := decryptLargeExponent(priv, ciphertext)
   292  	if err != nil {
   293  		return nil, err
   294  	}
   295  
   296  	hash.Reset()
   297  	hash.Write(label)
   298  	lHash := hash.Sum(nil)
   299  
   300  	firstByteIsZero := constanttime.ByteEq(em[0], 0)
   301  
   302  	seed := em[1 : hash.Size()+1]
   303  	db := em[hash.Size()+1:]
   304  
   305  	mgf1XOR(seed, mgfHash, db)
   306  	mgf1XOR(db, mgfHash, seed)
   307  
   308  	lHash2 := db[0:hash.Size()]
   309  
   310  	lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
   311  
   312  	var lookingForIndex, index, invalid int
   313  	lookingForIndex = 1
   314  	rest := db[hash.Size():]
   315  
   316  	for i := 0; i < len(rest); i++ {
   317  		equals0 := constanttime.ByteEq(rest[i], 0)
   318  		equals1 := constanttime.ByteEq(rest[i], 1)
   319  		index = constanttime.Select(lookingForIndex&equals1, i, index)
   320  		lookingForIndex = constanttime.Select(equals1, 0, lookingForIndex)
   321  		invalid = constanttime.Select(lookingForIndex&^equals0, 1, invalid)
   322  	}
   323  
   324  	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
   325  		return nil, ErrDecryption
   326  	}
   327  
   328  	return rest[index+1:], nil
   329  }
   330  
   331  // TestingOnlyLargeExponentEncryptOAEP encrypts the given message with RSAES-OAEP
   332  // using a public key with a large exponent. It is only meant for ACVP testing.
   333  func TestingOnlyLargeExponentEncryptOAEP(hash, mgfHash hash.Hash, random io.Reader, pub *TestingOnlyLargeExponentPublicKey, msg []byte, label []byte) ([]byte, error) {
   334  	fipsSelfTest()
   335  	fips140.RecordApproved()
   336  	checkApprovedHash(hash)
   337  	if err := checkLargeExponentPublicKey(pub); err != nil {
   338  		return nil, err
   339  	}
   340  	k := pub.Size()
   341  	if len(msg) > k-2*hash.Size()-2 {
   342  		return nil, ErrMessageTooLong
   343  	}
   344  
   345  	hash.Reset()
   346  	hash.Write(label)
   347  	lHash := hash.Sum(nil)
   348  
   349  	em := make([]byte, k)
   350  	seed := em[1 : 1+hash.Size()]
   351  	db := em[1+hash.Size():]
   352  
   353  	copy(db[0:hash.Size()], lHash)
   354  	db[len(db)-len(msg)-1] = 1
   355  	copy(db[len(db)-len(msg):], msg)
   356  
   357  	if err := drbg.ReadWithReader(random, seed); err != nil {
   358  		return nil, err
   359  	}
   360  
   361  	mgf1XOR(db, mgfHash, seed)
   362  	mgf1XOR(seed, mgfHash, db)
   363  
   364  	return encryptLargeExponent(pub, em)
   365  }
   366
View as plain text