В не симметричных криптосистемах с открытым ключом в алгоритмах шифрования и дешифрования используются разные ключи, каждый из которых не может быть получен из другого (с приемлемыми затратами). Один ключ используется для шифрования, другой — для дешифрования. Основной принцип систем с открытым ключом основывается на применении односторонних или необратимых функций и односторонних функций с лазейкой (потайным ходом).
Вычисление ключей осуществляется получателем сообщений, который оставляет у себя тот ключ, который он будет потом использовать (то есть секретный ключ). Другой ключ он высылает отправителю сообщений — открытый ключ — не опасаясь его огласки. Пользуясь этим открытым ключом, любой абонент может зашифровать текст и послать его получателю, который сгенерировал данный открытый ключ. Все используемые алгоритмы общедоступны. Важно то, что функции шифрования и дешифрования обратимы лишь тогда, когда они обеспечиваются строго взаимосвязанной парой ключей (открытого и секретного), а открытый ключ должен представлять собой необратимую функцию от секретного ключа. Подобным образом шифр текст должен представлять собой необратимую функцию открытого текста, что в корне отличается от шифрования в системах с секретным ключом.
Исследование необратимых функций проводилось в основном по следующим направлениям: дискретное возведение в степень — алгоритм DH (Диффи-Хелман), умножение простых чисел — алгоритм RSA (Райвест, Шамир, Адлеман), использование исправляющих ошибки кодов Гоппы, задачи NP-полноты, в частности криптоалгоритм Меркля и Хелмана на основе «задачи об укладке ранца», раскрытый Шамиром, и ряд других, оказавшихся легко раскрываемыми и бесперспективными.
Первая система (DH) обеспечивает открытое распространение ключей, то есть позволяет отказаться от передачи секретных ключей, и по сегодняшний день считается одной из самых стойких и удобных систем с открытым ключом.
Надежность второго метода (RSA) находится в прямой зависимости от сложности разложения больших чисел на множители. Если множители имеют длину порядка 100 десятичных цифр, то в наилучшем из известных способов разложения на множители необходимо порядка 100 млн. лет машинного времени, шифрование же и дешифрование требует порядка 1-2 с на блок.
Задачи NP-полноты хорошо известны в комбинаторике и считаются в общем случае чрезвычайно сложными; однако построить соответствующий шифр оказывается весьма непросто.