Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In protocols/systems which use ECDSA, is it common for the message to contain the public key of the message signer?
If not, how do recipients know that the message has been signed by the correct private key, and how do they know which public key to use to verify the signature?
I'd say that most of the time the signature is accompanied by the certificate of the signer. This certificate contains the public key. Most container formats such as CMS (used in S/MIME, also known as PKCS#7) or XML digsig contain specific fields that may contain certificates - and usually do.
When the certificate is received the Public Key Infrastructure (PKI) can be used to verify the certificate. In case of X.509 PKI that would for instance include verifying the chain of certificates leading to a trusted certificate (probably published by a Certificate Authority and included in a browser or system key store). Of course additional validation/verification should be performed, such as testing validity of the certificate and the revocation status. As you already noted, the other way is to validate the certificate or public key through a web of trust, such as used for (open) PGP.
The PKI is indeed a trust framework, although I would not directly call it a "trusted channel".
For specific protocols it may be that the public key is simply looked up in a trust store based upon a user name or key id. This is for instance the case in SSH, where the public keys are stored in a file containing trusted public keys and bound to the specific user.
You are probably aware of the existence of public key certificates. A certificate proves the authenticity of a public key, basically by signing the value of that public key (plus some data on the owner of that key) with a private key of some third party. This third party often is a central Certificate Authority (CA) that is trusted by both the sender and the receiver of the message; in that case, we're talking about a Public Key Infrastructure. An example are the CAs that your web browser trusts: any server certificate signed by these CAs will be trusted by your browser. CAs are also used in (chip) payment cards, identity cards etcetera. (The Web of Trust mentioned above is another option, if there is no central CA that is trusted by both parties.)
So the recipient of the message knows that a message has been signed with the correct private key by means of a 2-step process:
First, validate the certificate belonging to the public key, by means of the public key of the CA that is indicated in the certificate and that is trusted by the recipient.
Then, verify the message itself by checking the signature using the public key in the certificate.
Now finally coming to your question: how does the recipient of the message get to know the public key certificate that allows him to verify the signature over the message? Obviously, the sender of the message should somehow tell the receiver about his identity during the exchange. This can be done by simply sending some identifier as part of the protocol. Next, there are at least three possibilities:
What solution is used depends totally on the system. For example, if the communication parties not always online (e.g. for an offline payment terminal), then these parties will always contain their certificates and will exchange these as part of the communication. If all communicating parties in the system are known upfront, it's probably easier to have a central certificate repository.
Typically, a message will contain some sort of identifying information of the sender, such as the From header of an e-mail. In any case, if the sender of the message is unknown, what's the point of using signatures at all? The purpose of a signature is to ascertain that the message was written and sent by its purported sender.
The only way to be 100% certain that a given public key belongs to a given person is to have been told so by that person over a secure channel. If one is willing to accept some degree of uncertainty, one can look-up that person's key on a public keyserver, possibly using the web of trust (i.e., requiring that the public key have been signed by other, trusted persons).
