Bob know's Alice's public key, and he wants to make sure he's connecting to the one which has that key. Furthermore, Alice wants to verify when she gets a connection from Bob who'll give his public key that he is indeed the one who has that key. Bob will send Alice half the AES private key and half the initialization vector which he generated randomly, both encrypted using Alice's public key. Alice would reply by sending back what Bob sent + the other half of the AES private key and the initialization vector which she generated randomly as well. Afterwards communication begin using AES crypto stream with a key composed of the two halves both exchanged. If a crypto exception was thrown at either side at any point, the connection will be terminated. No third message will be sent from Bob to Alice to verify that he got her part of the key, the AES stream will begin directly after Alice's message. Note: I thought about using Diffie-Hellman, but what I didn't like what that the private key agreed upon would be the same for every session assuming the two parties will not change their public keys. Is this enough for both to verify that each one is the actual owner of the claimed public key, and to exchange the AES symmetric key safely without creating potential security issues ?