Key exchange
In principle, then, the only remaining problem was to be sure that a public key actually belonged to its claimed owner, this is not a problem easy to solve; specially when the two users involved have never met and know nothing about each other.