Схемы шифрования с открытым ключом и цифровой подписи. Основные принципы

Криптосистемы с открытым ключом используются непосредственно для передачи исключительно важных сообщений. Во многом подобные криптосистемам с секретным ключом криптосистемы с открытым ключом состоят из: пространства ключей K, а для каждого k из K, из пространств открытых сообщений M_K, пространств шифртекстов C_K и пар функций , таких что для любого открытого текста m из . Как и в криптосистемах с секретным ключом, эффективные алгоритмы для вычисления как E_K, так и D_K, должны легко получаться для каждого ключа k. Будем называть алгоритмы, полученные таким образом, естественными алгоритмами. Важной новой отличительной особенностью является то, что E_K должна быть однонаправленной функцией с секретом: необходимо, чтобы было практически невозможно построить никакого эффективного алгоритма для вычисления D_K (но только естественного алгоритма), зная описание естественного алгоритма для вычисления E_K.

В частности, это означает, что k не должно появляться в явном виде в естественном алгоритме шифрования.

Криптографические системы с открытым ключом используются следующим образом. Каждый пользователь раз и навсегда выбирает некоторый случайный ключ k из K. Он использует этот ключ для получения обоих естественных алгоритмов E_K и D_K. Затем он делает публично доступным свой алгоритм шифрования E_K, возможно посредством использования при этом некоторого справочника, но хранит в тайне свой алгоритм расшифрования D_K.

В том случае если другой пользователь захочет послать ему некоторое сообщение, то он найдет в справочнике его открытый алгоритм шифрования и использует его для того чтобы зашифровать свое сообщение. Тогда, используя собственный секретный ключ, только законный получатель сможет расшифровать это сообщение.

В противоположность криптосистемам с секретным ключом, заметим, что если пользователь А, закодировав некоторое сообщение m для пользователя В, сохранил шифртекст С, но потерял открытый текст (или забыл все, что в нем содержалось), то он не будет иметь никаких преимуществ перед нарушителем в раскрытии m из С.

Также в противоположность криптосхемам с секретным ключом, если нарушитель перехватывает шифртекст и знает для кого он был зашифрован, то он может использовать открытый алгоритм шифрования для проверки любого конкретного предположения о том, каким может быть соответствующий открытый текст. Возможность формировать шифртексты из открытых текстовых сообщений по своему выбору является причиной сокращения числа классических уровней атаки, которые обсуждались в связи с криптосистемами с секретным ключом.