Proving identity in asymmetrically encrypted communication

Let's assume such a scenario. Person A will broadcast his public key and person B will broadcast his public key. They can now communicate. But let's say that suddenly another person C will write to person A impersonation person B. How can a person B prove their identity. We can implement a signature system. Person A will genereate a certain signature and gives it to person B, to always join it to the message, targeted to person A and prove the identity in such way, but the same problem will still appear. How a person B knows that the signature received is from a person A. Is there a way to prove the identity in such a system.

It sounds like the primitive you're looking for is Authenticated Key Exchange.

There are a lot of AKEs out there, only some of which require signatures. See chapter 5 of the key exchange book for an overview. Some of the more popular ones are X3DH, the more general Noise framework, and HMQV.

I came to the conclusion that I replied myself with my own question. If persion A will generate a signature for persion B and send it using persons B public key to encrypt it, only these two people will know the secret. So now it is crucial that the person B always joins his signature which has been received from a person A. In order to identify the recipient of the message, we use a public key and to identify the person from which we received messages we use a generated signature. In this way, we can map the public key with the generated signature one-to-one. Thanks to the comment of mikero, I looked at my question from a different angle. Also, I will take into account the algorithms suggested by p-rathje when creating a key-exchange system.

When you assume that C acts as an adversary, is eavesdropping and capable of constructing messages based on the acquired information, you have to design your protocol with care. This stems from the fact that C could potentially relay, replay, and construct messages. Therefore, you need to prevent replay and man-in-the-middle attacks, furthermore handling for multiple, (simultaneous) protocol sessions. You already realized that a static signature might not be enough. Essentially, your problem is the motivation for authentication protocols and their design is not trivial: if you take a look at the Needham–Schroeder protocol 1 or the Woo-Lam protocol 2 you will see that unforeseen attack vectors could break your protocol as both examples are insecure in their original versions.

Basically, some best practices for secure protocol design are:

• Make maximally pessimistic assumption
• Put the sender and receiver in messages (i.e., their public keys)
• Use encryption to ensure that only the correct receiver can read the content
• Use nonces / timestamps to get freshness
• Generate nonces yourself to prevent replay attacks
• Always sign and encrypt components together

But still: there are protocols considered secure that do not follow all points and insecure protocols that do. In any case, you would want to analyze your protocol (semi-)automatically using for example model checking or theorem proving.