Обычные средства криптографии (с одним ключом для шифровки и дешифровки) предполагают, что стороны, вступающие в переписку по открытым каналам связи, перед началом обмена передают друг другу секретный ключ, (пароль), однако чтобы передать секретный ключ, нужен секретный канал, ещё не образованный в виду отсутствия у абонентов ключа шифрования. Такой способ шифрования называется симметричным.
Программа PGP (Pretty Good Privacy) относится к классу систем с двумя ключами, открытым и закрытым. Сообщения, предназначенные для владельца ключа, зашифрованные на основе открытого ключа, никто, кроме владельца, (имеющего второй, секретный ключ) расшифровать не сможет. Такое шифрование называется асимметричным.
Связано это с тем, что в дальнейшем в системе защиты будет предложен и использован механизм построенный по принципу асимметричных криптосистем.
Асимметричные или двухключевые системы являются одним из обширным классом криптографических систем. Эти системы характеризуются тем, что для шифрования и для расшифрования используются разные ключи, связанные между собой некоторой зависимостью. При этом данная зависимость такова, что установить один ключ, зная другой, с вычислительной точки зрения очень трудно.
Один из ключей (например, ключ шифрования) может быть сделан общедоступным, и в этом случае проблема получения общего секретного ключа для связи отпадает. Если сделать общедоступным ключ расшифрования, то на базе полученной системы можно построить систему аутентификации передаваемых сообщений. Поскольку в большинстве случаев один ключ из пары делается общедоступным, такие системы получили также название криптосистем с открытым ключом.
Криптосистема с открытым ключом определяется тремя алгоритмами: генерации ключей, шифрования и расшифрования. Алгоритм генерации ключей открыт, всякий может подать ему на вход случайную строку r надлежащей длины и получить пару ключей (k1, k2). Один из ключей (например, k1) публикуется, он называется открытым, а второй, называемый секретным, хранится в тайне. Алгоритмы шифрования и расшифрования таковы, что для любого открытого текста m Dk2(Ek1(m))=m.
Рассмотрим теперь гипотетическую атаку злоумышленника на эту систему. Противнику известен открытый ключ k1, но неизвестен соответствующий секретный ключ k2. Противник перехватил криптограмму d и пытается найти сообщение m, где d=Ek1(m). Поскольку алгоритм шифрования открыт, противник может просто последовательно перебрать все возможные сообщения длины n, вычислить для каждого такого сообщения mi криптограмму di=Eki(mi) и сравнить di с d. То сообщение, для которого di = d и будет искомым открытым текстом. Если повезет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2nT(n), где T(n) – время, требуемое для шифрования сообщения длины п. Если сообщения имеют длину порядка 1000 битов, то такой перебор неосуществим на практике ни на каких самых мощных компьютерах.
Мы рассмотрели лишь один из возможных способов атаки на криптосистему и простейший алгоритм поиска открытого текста, называемый обычно алгоритмом полного перебора. Используется также и другое название: «метод грубой силы». Другой простейший алгоритм поиска открытого текста – угадывание. Этот очевидный алгоритм требует небольших вычислений, но срабатывает с пренебрежимо малой вероятностью (при больших длинах текстов). На самом деле противник может пытаться атаковать криптосистему различными способами и использовать различные, более изощренные алгоритмы поиска открытого текста.