For a long time the specter of two strangers communicating securely over an insecure channel was regarded as inherently illogical and impossible.
The breakthrough came about when cryptographers downgraded their goal. They left out the issue of cross identification of the strangers, and focused instead on continuity . Insuring that the stranger with whom one started a conversation is the same person with whom it ended.
This appeared a much easier goal. Ralph Merkle achieved it through asymmetry between Alice and Bob. Alice pre-computed a list of difficult computational tasks, which she presented to Bob to choose from. Bob picked on task randomly, computed it and communicated to Alice the result. This communication created a shared secret between Alice and Bob -- the identity of the computed task. For some time (enough!) the hackers were clueless.