Шифр Цезаря

     Историческим  примером шифра замены является шифр Цезаря (I век до н.э.), описанный историком  Древнего Рима Светонием. Гай Юлий Цезарь в своей переписке использовал  шифр собственного изобретения. Применительно к русскому языку он состоял в следующем: каждая буква алфавита заменялась другой буквой, из этого алфавита, идущей за первой через некоторый интервал.

     Пример  – выпишем алфавит

     А Б В Г Д Е Ж З И Й  К Л М Н О П Р С Т  У Ф Х Ц Ч Ш Щ Ю Я,

     И запишем под ним тот же алфавит, но с циклическим сдвигом

     Г Д Е Ж З И Й К Л М  Н О П Р С Т У Ф Х Ц Ч Ш Щ Ю Я А Б В

     При шифровании буква А заменялась буквой Г, Б заменялась на Д, и так далее. Так, например, слово «Империя» превращалось в слово «Лптзулв». Получатель сообщения  искал буквы, из которых написано послание, и заменял их буквами из верхней строки – в этом заключался способ декодирования.

     Естественное  развитие шифра Цезаря очевидно: нижняя строка двустрочной записи букв алфавита может быть произвольным расположением этих букв. Если в алфавитном расположении букв существует всего 32 варианта (для русского языка, без буквы «ё»), то при произвольном расположении число ключей становиться 33!≈10^35.

Основные  алгоритмы шифрования

     Метод шифровки/дешифровки называют шифром (cipher). Некоторые алгоритмы шифрования основаны на том, что сам метод шифрования (алгоритм) является секретным. Ныне такие методы представляют лишь исторический интерес и не имеют практического значения. Все современные алгоритмы используют ключ для управления шифровкой и дешифровкой; сообщение может быть успешно дешифровано, только если известен ключ. Ключ, используемый для дешифровки, может не совпадать с ключом, используемым для шифрования, однако в большинстве алгоритмов ключи совпадают.

     Алгоритмы с использованием ключа делятся  на два класса: симметричные (или алгоритмы секретным ключом) и асимметричные (или алгоритмы с открытым ключом). Разница в том, что симметричные алгоритмы используют один и тот же ключ для шифрования и для дешифрования (или же ключ для дешифровки просто вычисляется по ключу шифровки). В то время как асимметричные алгоритмы используют разные ключи, и ключ для дешифровки не может быть вычислен по ключу шифровки.

     Симметричные алгоритмы подразделяют на потоковые шифры и блочные шифры. Потоковые алгоритмы позволяют шифровать информацию по битам, в то время как блочные работают с некоторым набором бит данных (обычно размер блока составляет 64 бита) и шифруют этот набор как единое целое.

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

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

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

     Многие  качественные криптографические алгоритмы  доступны широко – в книжном магазине, библиотеке, патентном бюро или в Интернете. К широко известным симметричным алгоритмам относятся DES и IDEA, Наверное, самым лучшим асимметричным алгоритмом является RSA.

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

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

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

     Цифровые  подписи также можно использовать для удостоверения (сертификации – to certify) того, что документ принадлежит определенному лицу. Это делается так: открытый ключ и информация о том, кому он принадлежит подписываются стороной, которой доверяем. При этом доверять подписывающей стороне мы можем на основании того, что ее ключ был подписан третьей стороной. Таким образом, возникает иерархия доверия. Очевидно, что некоторый ключ должен быть корнем иерархии (то есть ему мы доверяем не потому, что он кем-то подписан, а потому, что мы верим a-priori, что ему можно доверять). В централизованной инфраструктуре ключей имеется очень небольшое количество корневых ключей сети (например, облеченные полномочиями государственные агентства; их также называют сертификационными агентствами – certification authorities). В распределенной инфраструктуре нет необходимости иметь универсальные для всех корневые ключи, и каждая из сторон может доверять своему набору корневых ключей (скажем своему собственному ключу и ключам, ею подписанным). Эта концепция носит название сети доверия (web of trust) и реализована, например, в PGP.

     Цифровая  подпись документа обычно создается  так: из документа генерируется так называемый дайджест (message digest) и к нему добавляется информация о том, кто подписывает документ, штамп времени и прочее. Получившаяся строка далее зашифровывается секретным ключом подписывающего с использованием того или иного алгоритма. Получившийся зашифрованный набор бит и представляет собой подпись. К подписи обычно прикладывается открытый ключ подписывающего. Получатель сначала решает для себя доверяет ли он тому, что открытый ключ принадлежит именно тому, кому должен принадлежать (с помощью сети доверия или априорного знания), и затем дешифрует подпись с помощью открытого ключа. Если подпись нормально дешифровалась, и ее содержимое соответствует документу (дайджест и др.), то сообщение считается подтвержденным.

     Свободно  доступны несколько методов создания и проверки цифровых подписей. Наиболее известным является алгоритм RSA.

Криптографические хэш-функции

     Криптографические хэш-функции используются обычно для генерации дайджеста сообщения при создании цифровой подписи. Хэш-функции отображают сообщение в имеющее фиксированный размер хэш-значение (hash value) таким образом, что все множество возможных сообщений распределяется равномерно по множеству хэш-значений. При этом криптографическая хэш-функция делает это таким образом, что практически невозможно подогнать документ к заданному хэш-значению.

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

     Много хороших криптографических хэш-функций  доступно бесплатно. Широко известные включают MD5 и SHA.

Криптографические генераторы случайных  чисел

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

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

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

     Криптографические генераторы псевдослучайных чисел обычно используют большой пул (seed-значение), содержащий случайную информацию. Биты генерируется путем выборки из пула с возможным прогоном через криптографическую хэш-функцию, чтобы спрятать содержимое пула от внешнего наблюдателя. Когда требуется новая порция бит, пул перемешивается путем шифровки со случайным ключом (его можно взять из неиспользованной пока части пула) так, чтобы каждый бит пула зависел от каждого другого бита. Новый шум окружения должен добавляться к пулу перед перемешиваниям, дабы сделать предсказание новых значений пула еще более сложным.

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

Типы  шифров

     Криптосистемы разделяются на симметричные (с секретным  ключом) и с открытым ключом.

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

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

Обеспечиваемая  шифром степень защиты

     Хорошие криптографические системы создаются  таким образом, чтобы сделать  их вскрытие как можно более трудным  делом. Можно построить системы, которые на практике невозможно вскрыть (хотя доказать сей факт обычно нельзя). При этом не требуется очень больших усилий для реализации. Единственное, что требуется – это аккуратность и базовые знания. Нет прощения разработчику, если он оставил возможность для вскрытия системы. Все механизмы, которые могут использоваться для взлома системы надо задокументировать и довести до сведения конечных пользователей.

     Теоретически, любой шифровальный алгоритм с использованием ключа может быть вскрыт методом перебора всех значений ключа. Если ключ подбирается методом грубой силы (brute force), требуемая мощность компьютера растет экспоненциально с увеличением длины ключа. Ключ длиной в 32 бита требует 2^32 (около 10^9) шагов. Такая задача под силу любому дилетанту и решается на домашнем компьютере. Системы с 40-битным ключом (например, экспортный американский вариант алгоритма RC4) требуют 2^40 шагов - такие компьютерные мощности имеются в большинстве университетов и даже в небольших компаниях. Системы с 56-битными ключами (DES) требуют для вскрытия заметных усилий, однако могут быть легко вскрыты с помощью специальной аппаратуры. Стоимость такой аппаратуры значительна, но доступна для мафии, крупных компаний и правительств. Ключи длиной 64 бита в настоящий момент, возможно, могут быть вскрыты крупными государствами и уже в ближайшие несколько лет будут доступны для вскрытия преступными организациями, крупными компаниями и небольшими государствами. Ключи длиной 80 бит могут в будущем стать уязвимыми. Ключи длиной 128 бит, вероятно, останутся недоступными для вскрытия методом грубой силы в обозримом будущем. Можно использовать и более длинные ключи. В пределе нетрудно добиться того, чтобы энергия, требуемая для вскрытия (считая, что на один шаг затрачивается минимальный квантовомеханический квант энергии) превзойдет массу солнца или вселенной.