How can we use digital signatures for mutual authentication between two computers?

Question

I get the fact that we can use digital signatures for authenticating the signer (since they are using their private key to create the signature, and this is known only to the signer ). But how can the verifier also be authenticated using digital signature? I have a feeling that we could use digital certificates for this but I am confused about how such a protocol would work.

Answer 1

Preface

Digital signatures and signing is not a one way street. A public private keypair is actually just a mathematically linked keypair, with one key designated as the private key and the other designated as the public key.

When you sign a message with the private key, the public key can be used to check the message and thus validate the sender. Additionally, when you encrypt a message with the public key only the private key can decrypt it. This can be used to ensure only one receiver can read the message. What some people don't realize though, is that this process is actually mathematically reversible. You could sign a message with your public key (making it only verifiable to yourself), or encrypt a message with your private key (making it readable to the world). Mathematically, keypairs are interchangeable and can both perform the same operations. However, it is worth noting that when it comes to practical applications, these keys should not be interchanged. You can read more about why a private key is chosen to be private in this StackOverflow answer. In short, both keys are derived by an exponent. In real world cryptographic applications like RSA, the exponent for the private key is made extremely large, thus causing the public key exponent to be extremely small. This makes guessing the private key WAY harder, while making the task of guessing the public key WAY easier (which is fine because everyone already knows the public key). So, if you gave out your private key and kept your public key secret, it would be easy for an attacker to derive your privately held public key when compared to the proper method of doing things.

Also, something to touch on: Mathematically, signing and encrypting is the same process. Signing a message is simply taking a hash of the message and then encrypting the hash using your private key. This encrypted hash is sent along with the message. Other users will verify this signature by decrypting it using your public key. They will then hash the message and compare the hash they computed with the hash from your signature. If they match you are verified because they only you could have used your private key to encrypt the correct hash of the message.

Note: You mention digital certificates as being used to solve your problem as if it is a separate thing from public-private key cryptography. It is not. These are both examples of asymmetric cryptography. Digital certificates contain a public key along with other metadata, all of which is usually signed by another authority (using asymmetric cryptography)

To answer your question

There are multiple ways you can do this with asymmetric cryptography. In my following examples we will have Alice and Bob who both want to authenticate the other user.

Example 1
Oddly enough, in the same SO thread I linked to explain digital certificates there is one answer to your question. Similarly, to achieve mutual authentication between two entities we can sign an encrypted message. Suppose Alice initiates a conversation with Bob. Alice encrypts the message "respond with the codeword potato" using Bob's public key. Alice then signs this encrypted message with her private key. When Bob receives the message, he can verify that Alice sent it by checking the signature against Alice's public key. Bob can then decrypt the message with his private key and respond to Alice with the codeword "potato" (encrypting his response with Alice's public key). When Alice receives the message from Bob and reads the codeword, she can validate it is Bob on the other end.

**Alternatively, Bob could just sign his response message and Alice could verify him that way (a more secure method) but this scenario has the downfall of not involving the word "potato".

Example 2 Because a public-private keypair is simply a mathematically linked keypair, we could conceivably have two private keys. In this implementation, the size of the exponent would not be chosen to be overly small or large for either key. This would prevent one key from being "weaker"/"stronger" than the other. If we give Alice the first private key, and Bob the second private key, they would be able to sign their messages with their own private key, thus making it verifiable to the other user's private key. AKA, Alice sends a "hello" message to bob, and signs it with her private key. When Bob receives the message, he can validate it using his own private key (which is the partner key to Alice's) and then respond with a "hello", signing this message with his private key. Both parties would know that the other is who they say they are. Additionally, because both of these keys are private, Alice and Bob could encrypt their messages using their own private keys, ensuring that they are only readable to the other person.

**Disclaimer: This second example came straight out of my head. There are probably implications to signing/encrypting messages back and forth like this which I am unaware of, but this is a simple to digest example.