How can you bind a public key to a certificate if the public key depends on the choice of algorithms?
Can the same public key be used with RSA, Elliptic Curve, or other asymmetric encryptions algorithms?
No. The algorithm is inherent in the key.
If not, how is a public key bound to a X.509 Certificate?
It is not bound to the certificate, but it is part of the certificate.
Presumably, you'd have to know the algorithmic choice before determine a public key, and the choice of algorithms is only settled during the handshake.
If the client only offers ciphers1 which require RSA based authentication and the server only has a ECC certificate then the handshake will simply fail, since there are no shared ciphers supported by both sides.
Typically the client shows support for both RSA and ECC certificates in the ciphers though, so that a shared cipher can be found no matter what kind of certificate the server has. And in some cases servers have also both types of certificates.
1 This is a bit simplified. With TLS 1.3 the algorithm for the certificate is no longer in the cipher suite. But there is a signature_algorithms_cert extension. And even this statement is still simplified since there is also a signature_algorithms extension. See RFC 8446 section 4.2.3 for more.
Public keys vs signature algorithms
RSA
For simplicity, let's start with RSA. According to RFC 8017:
3.1. RSA Public Key
For the purposes of this document, an RSA public key consists of two components:
n the RSA modulus, a positive integer e the RSA public exponent, a positive integer
Typical values will be like this:
modulus = 0xfb1199ff0733f6e805a4fd3b36ca68...837a63
exponent = 65,537
So an RSA public key is simply a single very large integer. Now, when you actually go to use that public key, for example to generate a digital signature, you need to choose which algorithm to use. For example, that same RSA key could be used with any of the following signature algorithms:
- sha256WithRSAEncryption (defined in RFC 5754)
- sha512WithRSAEncryption (defined in RFC 5754)
- id-RSASSA-PSS-SHAKE256 (defined in RFC 8692)
Elliptic Curve
Elliptic curve keys have a different structure from RSA, it's defined in RFC 5480 and involves:
ECPoint ::= OCTET STRING
ECParameters ::= CHOICE {
namedCurve OBJECT IDENTIFIER
-- implicitCurve NULL
-- specifiedCurve SpecifiedECDomain
}
So an EC key is not compatible with signature algorithms designed for an RSA. And similarly to RSA, an Elliptic curve public key may be compatible with one or more different signature algorithms.
TLS cipher suite negotiation
The point here is that even if you know that your public key is RSA, you still need to choose what other crypto algorithms to combine it with to produce the signature; choose a padding scheme (PKCS#1_v1.5 or PSS), and choose a hash function (SHA-256, SHA-512, SHAKE-256, etc). This concept is referred to as a cipher suite, which the TLS client and server will negotiate before the certificate is used.
For example, if the client and server agree that any of the following list of TLS 1.2 cipher suites are acceptable:
ECDHE-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=ECDH Au=RSA Enc=AESGCM(128) Mac=AEAD
ECDHE-ECDSA-AES256-GCM-SHA384 TLSv1.2 Kx=ECDH Au=ECDSA Enc=AESGCM(256) Mac=AEAD
ECDHE-RSA-AES256-GCM-SHA384 TLSv1.2 Kx=ECDH Au=RSA Enc=AESGCM(256) Mac=AEAD
then the server would be free to use either an RSA or elliptic curve based certificate (note the "RSA" or "ECDSA" in the second position) using the specified hash function.
However if the client and server only agree on these, then the server had better have an RSA based certificate:
ECDHE-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=ECDH Au=RSA Enc=AESGCM(128) Mac=AEAD
ECDHE-RSA-AES256-GCM-SHA384 TLSv1.2 Kx=ECDH Au=RSA Enc=AESGCM(256) Mac=AEAD
Note that in TLS 1.3, the signature algorithm is no longer negotiated as part of the cipher suite and I believe the client can either accept or reject the certificate at a separate step of the handshake.
TLS_AES_128_GCM_SHA256 TLSv1.3 Kx=any Au=any Enc=AESGCM(128) Mac=AEAD
TLS_AES_256_GCM_SHA384 TLSv1.3 Kx=any Au=any Enc=AESGCM(256) Mac=AEAD