Симметричные шифры

Симметричный шифр это шифр использующий один ключ для зашифрования и расшифрования. Стороны, общающиеся при помощи симметричного шифра, должны договориться о ключе до начала обмена сообщениями. После того как они договорились, отправитель зашифровывает сообщение, используя ключ, отправляет получателю, и получатель расшифровываетет сообщение, используя тот же самый ключ. Например, немецкая Enigma - симметричный шифр, ежедневные ключи распространялись как книги кодов. Каждый день посылающий или принимающий радист должен был найти в своей копии книги кодов ключ на текущий день. Радиограммы в этот день зашифровывались и расшифровывались этим ключом. Современные примеры симметричных шифров: 3DES, Blowfish, IDEA и ГОСТ.

Хороший шифр заключает всю защиту в ключе, но не в алгоритме. Другими словами, знание используемого алгоритма не должно помочь взломщику. Знание алгоритма понадобится ему, только когда он получит ключ. Шифры, используемые в GnuPG, обладают этим свойством.

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

Британия использовала машины для подбора ключей, во время Второй Мировой войны. Немецкая Enigma имела очень большое пространство ключей, но Англичане построили специальные вычислительные механизмы, "Bombes", которые перебирали ключи пока на находили нужный. Иногда они находили ключ на текущий день через несколько часов после начала его использования, а иногда не находили совсем. "Bombes" не являлись компьютерами, но были их предшественниками.

Современные компьютеры могут перебирать ключи с огромной скоростью, поэтому размер ключа так важен в современных криптосистемах. Шифр DES использует ключ длиной 56 бит, т.е. существует 2⁵⁶ возможных ключей. 2⁵⁶ это 72,057,594,037,927,936 ключей. Много, но обычный компьютер может перебрать их за считаные дни, а специализированный за часы. С другой стороны, более поздние алгоритмы - 3DES, Blowfish и IDEA используют ключи длиной 128 бит, что означает 2¹²⁸ возможных ключей. Это намного больше, и, даже, если все компьютеры на нашей планете объединить, им потребуется времени больше, чем возраст вселенной, для нахождения ключа.

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

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

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

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

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

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

Смешанные шифры

Шифры с открытым ключом не панацея. Многие симметричные шифры более устойчивы против взлома, и, кроме того зашифрование/расшифрование открытым ключом требует больших затрат, чем аналогичные операции в симметричных системах. Шифры с открытым ключом, тем не менее, эффективны при распространении ключей симметричных шифров и именно так они используются в системах со смешанным шифром.

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

И PGP и GnuPG используют гибридные шифры. Сеансовый ключ, зашифрованный шифром с открытым ключом, и сообщение, зашифрованное симметричным шифром, автоматически объединяются вместе. Получатель использует свой секретный ключ для расшифровки сеансового ключа и, затем, использует полученный сеансовый ключ для расшифровки сообщения.

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

Цифровые подписи

Хеширующая функция это функция "многие-к-одному", отображающая свои аргументы на ограниченное множество значений. Обычно это множество - диапазон натуральных чисел. Простая хеширующая функция - f(x) = 0 для всех целых x. Более интересна функция f(x) = x mod 37, которая отображает x в остаток от деления x на 37.

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

Некоторые шифры с открытым ключом [1] могут быть использованы для подписи документов. Подписывающий зашифровывает документ своим секретным ключом. Желающий проверить подпись и увидеть документ, просто использует открытый ключ подписавшего для расшифровки документа. Этот алгоритм удовлетворяет двум условиям, налагаемым на хорошую хеширующую функцию, но на практике он слишком медленен.

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

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

Алгоритм, который действительно работает, использует метод с открытым ключом для шифрования только значения хеширующей функции. Подписанный документ может быть отправлен с использованием любого другого алгоритма шифрования, либо в чистом виде, если документ не содержит конфиденциальных сведений. Если документ изменен проверка подписи потерпит неудачу. Стандарт цифровой подписи DSA работает так, как было описано. DSA - основной алгоритм цифровой подписи, используемый в GnuPG.