<< ПредыдущаяОглавлениеСледующая >>


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 лет и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем – они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач.

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

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

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

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

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

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



<< ПредыдущаяОглавлениеСледующая >>