This is usually done after the keys have been shared among the two sides over some secure channel. However, some algorithms share the keys at the time of authentication.
The simplest solution for this kind of problem is for the two concerned users to communicate and exchange keys. However, for systems in which there are a large number of users or in which the users do not personally know each other (e.g., Internet shopping), this is not practical. There are various algorithms for both symmetric keys and asymmetric public key cryptography to solve this problem.
For key authentication using the traditional symmetric key cryptography, this is the problem of assuring that there is no man-in-the-middle attacker who is trying to read or spoof the communication. There are various algorithms used now-a-days to prevent such attacks. The most common among the algorithms are Diffie–Hellman key exchange, authentication using Key distribution center, kerberos and Needham–Schroeder protocol. Other methods that can be used include Password-authenticated key agreement protocols etc.[1]
Crypto systems using asymmetric key algorithms do not evade the problem either. That a public key can be known by all without compromising the security of an encryption algorithm (for some such algorithms, though not for all) is certainly useful, but does not prevent some kinds of attacks. For example, a spoofing attack in which public key A is claimed publicly to be that of user Alice, but is in fact a public key belonging to man-in-the-middle attacker Mallet, is easily possible. No public key is inherently bound to any particular user, and any user relying on a defective binding (including Alice herself when she sends herself protected messages) will have trouble.
The most common solution to this problem is the use of public key certificates and certificate authorities (CAs) for them in a public-key infrastructure (PKI) system. The certificate authority (CA) acts as a 'trusted third party' for the communicating users and, using cryptographic binding methods (e.g., digital signatures) represents to both parties involved that the public keys each holds which allegedly belong to the other, actually do so. A digital notary service, if you will. Such CAs can be private organizations providing such assurances, or government agencies, or some combination of the two. However, in a significant sense, this merely moves the key authentication problem back one level for any CA may make a good faith certification of some key but, through error or malice, be mistaken. Any reliance on a defective key certificate 'authenticating' a public key will cause problems. As a result, many people find all PKI designs unacceptably insecure.
Accordingly, key authentication methods are being actively researched.