Для безопасного обмена ключами (устойчивой к «человеку посередине») клиенты должны подписывать все свои сообщения. Чтобы подпись можно было проверить, другая сторона должны знать открытый ключ. Чтобы быть уверенным в достоверности открытого ключа, его в свою очередь должен подписать кто-то, кому мы доверяем. Обычно для этого используется сервер открытых ключей, но в вашем случае нужно думать.
В моем блоге (см профиль) есть несколько статей, посвященных p2p и криптографии с открытым ключом. Почитайте, может поможет набрести на правильные мысли. Только помните, что ошибки на уровне протокола очень дорого исправлять. Так что любую свою «гениальную» мысль имеет смысл обсудить хотя бы с парой понимающих людей.