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