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

Основная проблема симметричных шифров - обмен ключами. Отправитель и получатель должны обменяться ключами, которые будут использоваться для защищенного обмена информацией, но каким защищенным каналом они могут воспользоваться для обмена самими ключами? В частности, взломщику может быть легче перехватить ключ, нежели его подбирать. Другая проблема - количество необходимых ключей. Если n человек хотят обмениваться между собой сообщениями, то необходимо n(n-1)/2 ключей, по одному для каждой пары, учавствующей в переписке. Это может быть приемлемо для небольшой группы людей, но станет неудобным при ее увеличении.

Шифры с открытым ключом были придуманы, чтобы решить проблему с обменом ключами. Шифр с открытым ключом использует пару ключей для отправки сообщений. Два ключа относятся к лицу принимающему сообщение. Один ключ открытый (public key) и может быть передан любому. Другой ключ секретный (private key) и хранится только у владельца. Отправитель зашифровывает сообщение открытым ключом получателя, и ,будучи зашифровано, сообщение может быть расшифровано только закрытым ключом получателя.

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

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

Как и в случае симметричных шифров, вся защита хорошего шифра с открытым ключом заключена в ключе. Надежность зависит от размера ключа, но нельзя сравнивать длины ключей симметричных шифров и шифров с открытым ключом как меру их относительной надежности. При грубом взломе симметричного шифра с ключом длиной 80 бит, взломщик должен перебрать до 2⁸¹-1 ключей для нахождения правильного. При взломе шифра с открытым ключом с длиной ключа 512 бит, взломщик должен разложить на множители число закодированное в 512 битах (до 155 десятичных знаков). Действия взломщика сильно различаются в зависимости от шифра. Если для симметричных шифров, на сегодняшний день, достаточна длина ключа 128 бит, то для открытых ключей рекомендуется длина 1024 бита.