2.2.6. Примеры шифрования

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

Свой след в истории криптографии оставили многие хорошо известные исторические личности. Пер­вые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра (шифр «Сцитала»). Цезарь использовал в переписке шифр, который вошел в историю как «шифр Цезаря». В древней Греции был изобретен вид шифра, который в дальнейшем стал называться «квадрат Полития». Одну из первых книг по криптографии написал аббат И. Трителий (1462 – 1516), живший в Германии. В 1566 году известный мате­матик Д. Кардано опубликовал работу с описанием изобретенной им системы шифрования («решетка Кардано»). Франция XVI века оставила в истории криптографии шифры короля Генриха IV и Ришелье. 

Рассмотрим более подробно примеры, отражающие логику развития представляемой предметной области.

Шифр «Сцитала». Этот шифр известен со времен войны Спарты против Афин в V веке до н. э. [7] Для его реализации использовалась сцитала – жезл, имеющий форму цилиндра. На сциталу виток к витку наматывалась узкая па­пирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль оси сциталы записывался открытый текст. Лента разматывалась и получалось (для непосвященных), что поперек ленты в беспорядке написаны какие-то буквы. Затем лента отправлялась адресату. Адресат брал такую же сциталу, таким же образом наматывал на нее полученную ленту и читал сообщение вдоль оси сциталы.

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

Поэтому класс шифров, к которым относится и шифр «Сцитала», называет­ся шифрами перестановки.

Шифр подобного класса можно получить иным путем. Пусть необходимо зашифровать фразу: «Это слово будет зашифровано». В такой простой фразе просматривается закономерность относительно частости повторения отдельных букв языка (см. таблицу 2.5).

                                                                              Таблица 2.5

Простой перестановочный шифр

Передадим в канал связи криптограмму, разбив ее для удобства представления на пятизначные группы:

ЭВТРТ   ОЗООБ   АВСУШ   АЛДИН   ОЕФОФ.

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

Другим простым типом шифра является шифр замены (трансформационный шифр). Каждый сим­вол в сообщении заменяется  в зашифрованном тексте другим символом. Символы для зашифрованного текста обычно берутся из того же алфавита, что и для сообщения, но это не обязательно. Система называется моноалфавитной  из-за того, что каждый символ сообщения всегда преобразует­ся в один и тот же символ зашифрованного текста (статистика языка сохраняется) [17].

Рассмотрим шифр Цезаря. Этот шифр реализует следующее преобразование откры­того текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т. е. после бу­квы «я» следует буква «а». Отметим, что Цезарь заменял букву третьей после нее буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига. Класс шифров, к которым относится и шифр Цезаря, называется шифрами замены.

Для иллюстрации такого шифра создадим таблицу замены, получившей название таблицы Веженера. Таблица приведена в Приложении. Поступим по правилу Цезаря и зашифруем ранее приведенную фразу. Для этого в первом столбце будем брать буквы открытого текста, а в качестве ключа возьмем букву «Г».  Получим  криптограмму вида

АХСФО  СЕСДЦ  ЗИХЛГ  ЬМЧУС  ЕГРСД.

В этой криптограмме подозрительно часто употребляется буква «С», т. е. сохраняется признак открытого текста, исходя из частости повторения букв. Вскрыть такой шифр способен даже не опытный в вопросах  криптоанализа человек. Покажем это на примере. Выпишем в одну строку криптограмму и разворачивая  столбцы вниз под каждой буквой напишем продолжение алфавита таким образом, чтобы в столбце оказались буквы всего алфавита с некоторым циклическим сдвигом.

В выделенной строке таблицы криптоанализа появляется сообщение, которое среди других строк таблицы имеет выраженную семантику.  Более безопасной (но лишь незначительно) является произвольная подста­новка, когда изменяется порядок подстановочных символов. Однако, хотя такая система имеет больше возможных ключей (30! вместо 30 возможных в системе Цезаря, один из которых тривиален), проблема со всеми  шифрами замены состоит в том, что их очень просто атаковать с использованием частотного анализа.

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

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

Рис. 2.6. Пример взлома  шифра Цезаря без знания ключа

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

Важнейшим для развития криптографии был вывод К. Шен­нона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так на­зываемой «ленты однократного использования», в которой открытый текст «объединяется» с полностью случайным ключом такой же дли­ны. Этот результат был доказан    К. Шенноном с помощью разработанно­го им теоретико-информационного метода исследования шифров.

Подчеркнем, что для абсолютной стойкости существенным является каждое из следующих требований к «ленте однократного использования»:

1)   полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);

2)   равенство длины ключа и длины открытого текста;

3)   однократность использования ключа.

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

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

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

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

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

Поэтому у пользователя остается единственный путь – получение практических оценок стойкости. Этот путь состоит из следующих эта­пов:

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

-        мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т. е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить модели­рование сил, средств и возможностей противника;

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

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

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