В этом вся красота и гениальность систем с публичными и приватными ключами.
Если сильно упрости до простого понимания, это выглядит примерно так:
Запускаете  и проверяется есть ли приватный ключ - нет, запускается его создание.
Генерируется пара публичный+приватный ключ (локально).
Отправляется в сеть уведомление о том, что вы создали.
При этом возможность, что кто-то другой создаст точно такой же приватный ключ, считается около нулевой.
Таким образом, ничего не получая с сервера или из распределенной сети можно доверять такому шифрованию при достаточной длине ключа (сейчас это 32 байта).