Шифры с открытым ключом

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

Этот метод решает проблему обмена ключами, присущую симметричным шифрам. Отпадает необходимость договоренности о ключе между отправителем и получателем. Все что требуется, это чтобы отправитель до начала секретного обмена информацией взял копию открытого ключа получателя.[3] Кроме того, один открытый ключ может использоваться всеми корреспондентами получателя. Таким образом, только n пар ключей необходимо для n человек, переписывающихся друг с другом. Ещё одним достоинством шифров с открытым ключом является возможность их использования для цифровой подписи.

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

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



[3] На самом деле здесь тоже имеются определённые сложности. Подробности описаны в главе "Управление ключами"