Партыка Т.Л., Попов И.И. Информационная безопасность

Подождите немного. Документ загружается.

подстановка) или нескольких (много- или полиалфавитная подстановка)

алфавитов.

Самой простой разновидностью является прямая (простая) замена, когда

буквы шифруемого сообщения заменяются другими буквами того же самого

или некоторого другого алфавита. Таблица замены может иметь следующий

вид (табл. 3.1).

Таблица 3.1. Таблица простой замены

Исходные

символы

шифруемог

о текста

А В С D Е F G Н I J К L М N 0 Р Q R S T U V W Х Y Z

Заменяющи

е символы

S Р Х L R Z I M А Y Е D W Т В G V N J O C F Н Q U К

Используя эту таблицу, зашифруем текст: In this book the reader will

find a comprehensive survey... Получим следующее зашифрованное

сообщение: At omiy pbbe omr nrsirn fadd zail s xbwgnrmrtjafr

jcnfru... Однако такой шифр имеет низкую стойкость, так как

зашифрованный текст имеет те же статистические характеристики, что и

исходный. Например, текст на английском языке содержит символы со

следующими частотами появления (в порядке убывания): Е — 0,13, Т —

0,105, А — 0,081, О — 0,079 и т. д. В зашифрованном тексте наибольшие

частоты появления в порядке убывания имеют буквы R — 0,12, О-0,09, А

и N по 0,07.

Естественно предположить, что символом R зашифрована буква Е,

символом О — буква T и т. д. Это действительно соответствует таблице

замены. Дальнейшая расшифровка не составляет труда. Эти методы

дешифровки хорошо известны из классической литературы (см., например,

Артур Конан Дойль, «Пляшущие человечки», или Алан Эдгар По, «Золотой

жук»).

Если бы объем зашифрованного текста был намного больше, чем в

рассмотренном примере, то частоты появления букв в зашифрованном

тексте были бы еще ближе к частотам появления букв в английском

алфавите и расшифровка была бы еще проще. Поэтому простую замену

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

Для повышения стойкости шифра используют полиалфавитные подстановки,

в которых для замены символов исходного текста используются символы

нескольких алфавитов. Известно несколько разновидностей

полиалфавитной подстановки, наиболее известными из которых являются

одно- (обыкновенная и монофоническая) и многоконтурная.

При полиалфавитной одноконтурной обыкновенной подстановке для замены

символов исходного текста используется несколько алфавитов, причем

смена алфавитов осуществляется последовательно

и циклически, т. е. первый символ заменяется соответствующим символом

первого алфавита, второй — символом второго алфавита и т. д. до тех

пор, пока не будут использованы все выбранные алфавиты. После этого

использование алфавитов повторяется.

Схема шифрования Вижинера. Таблица Вижинера представляет собой

квадратную матрицу с n

элементами, где n — число символов

используемого алфавита. На рис. 3.2 показана таблица Вижинера для

кириллицы. Каждая строка получена циклическим сдвигом алфавита на

символ. Для шифрования выбирается буквенный ключ, в соответствии с

которым формируется рабочая матрица шифрования.

Осуществляется это следующим образом. Из полной таблицы выбирается

первая строка и те строки, первые буквы которых соответствуют буквам

ключа. Первой размешается первая строка, а под нею — строки,

соответствующие буквам ключа в порядке следования этих букв в ключе.

Пример такой рабочей матрицы для ключа САЛЬЕРИ приведен в средней

части рис. 3.3.

Процесс шифрования осуществляется следующим образом:

1) под каждой буквой шифруемого текста записываются буквы ключа. Ключ

при этом повторяется необходимое число раз; 2) каждая буква

шифруемого текста заменяется по подматрице буквами, находящимися на

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

строке подматрицы и находящихся под ними букв ключа; 3) полученный

текст может разбиваться на группы по несколько знаков. Пусть,

например, Требуется зашифровать сообщение: МАКСИМАЛЬНО ДОПУСТИМОЙ

ЦЕНОЙ ЯВЛЯЕТСЯ ПЯТЬСОТ РУБ. ЗА ШТУКУ. В соответствии с первым

правилом записываем под буквами шифруемого текста буквы ключа.

Получаем:

максимально допустимой ценой является пятьсот руб. за штуку

сальерисаль ерисальери салье рисальер исальер иса ль ериса

Дальше осуществляется непосредственное шифрование в соответствии со

вторым правилом, а именно: берем первую букву шифруемого текста (М) и

соответствующую ей букву ключа (С); по букве шифруемого текста (М)

входим в рабочую матрицу шифрования и выбираем под ней букву,

расположенную в строке, соответствующей букве ключа (С), — в нашем

примере такой буквой является Э; выбранную таким образом букву

помещаем в шифрованный текст. Эта процедура циклически повторяется до

зашифрования всего текста.

На рис. 3.3 представлена схема шифрования. Эксперименты показали, что

при использовании такого метода статистические характеристики

исходного текста практически не проявляются в зашифрованном

сообщении. Нетрудно видеть, что замена по таблице Вижинера

эквивалентна простой замене с циклическим изменением алфавита, т. е.

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

алфавитов определяется числом букв в слове ключа. Поэтому стойкость

такой замены определяется произведением стойкости прямой замены на

число используемых алфавитов, т. е. на число букв в ключе.

Расшифровка текста производится в следующей последовательности: 1)

над буквами зашифрованного текста последовательно надписываются буквы

ключа, причем ключ повторяется необходимое

число раз; 2) в строке подматрицы Вижинера, соответствующей букве

ключа, отыскивается буква, соответствующая знаку зашифрованного

текста. Находящаяся под ней буква первой строки подматрицы и будет

буквой исходного текста; 3) полученный текст группируется в слова по

смыслу.

На рис. 3.4 данная процедура представлена в наглядном виде. Нетрудно

видеть, что процедуры как прямого, так и обратного преобразований

являются строго формальными, что позволяет реализовать их

алгоритмически. Более того, обе процедуры легко реализуются по одному

и тому же алгоритму.

Одним из недостатков шифрования по таблице Вижинера является то, что

при небольшой длине ключа надежность шифрования остается невысокой, а

формирование длинных ключей сопряжено с трудностями.

Нецелесообразно выбирать ключ с повторяющимися буквами, так как при

этом стойкость шифра не возрастает. В то же время ключ должен легко

запоминаться, чтобы его можно было не записывать. Последовательность

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

С целью повышения стойкости шифрования можно использовать

усовершенствованные варианты таблицы Вижинера. Приведем некоторые из

них: 1) во всех (кроме первой) строках таблицы буквы располагаются в

произвольном порядке; 2) в качестве ключа используются случайные

последовательности чисел. Из таблицы Вижинера выбираются десять

произвольных строк, которые кодируются натуральными числами от 0 до

10. Эти строки используются в соответствии с чередованием цифр в

выбранном ключе. Известны и другие модификации метода.

Вариант системы подстановок Вижинера при т = 2 называется системой

Вернама (1917 год). В то время ключ k = (k

, k

, ... , k

- 1)

записывался на бумажной ленте. Каждая буква исходного текста

переводилась с использованием кода Бодо в пятибитовый символ. К

исходному тексту Бодо добавлялся ключ (по модулю 2). Старинный

телетайп фирмы AT&T со считывающим устройством Вернама и

оборудованием для шифрования использовался корпусом связи армии США.

Монофоническая замена

Частным случаем рассмотренной полиалфавитной замены является так

называемая монофоническая замена. Особенность этого метода состоит в

том, что количество и состав алфавитов выбираются таким образом,

чтобы частоты появления всех символов в зашифрованном тексте были

одинаковыми. При таком положении затрудняется криптоанализ

зашифрованного текста с помощью его статистической обработки.

Выравнивание частот появления символов достигается за счет того, что

для часто встречающихся символов исходного текста предусматривается

использование большего числа заменяющих элементов, чем для редко

встречающихся. Пример монофонического шифра для английского алфавита

показан на рис. 3.5. Шифрование осуществляется так же, как и при

простой замене (т. е. по шифрующему алфавиту № 1), с той лишь

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

столбец алфавитов циклически сдвигается вверх на одну позицию. Таким

образом, столбцы алфавита как бы образуют независимые друг от друга

кольца, поворачиваемые вверх на один знак каждый раз после шифрования

соответствующего знака. В качества примера зашиф

руем монофоническим шифром тот же текст, который шифровался простой

заменой:

In this book the reader will find a comprehensive survey...

Шифрованный текст имеет вид:

А(-,) VNG/LjpGZ+F.=hg...

Если подсчитать частоты появления символов, то легко видеть, что даже

на таком коротком образце текста они в значительной мере выровнены.

При увеличении объема текста частоты появления символов будут еще

более выравниваться.

Полиалфавитная многоконтурная замена заключается в том, что для

шифрования используется циклически несколько наборов (контуров)

алфавитов, причем каждый контур в общем случае имеет свой

индивидуальный период применения. Этот период исчисляется, как

правило, количеством знаков, после зашифровки которых меняется контур

алфавитов. Частным случаем многоконтурной полиалфавитной подстановки

является замена по таблице Вижинера, если для шифрования используется

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

Общий принцип шифрования подстановкой может быть представлен

следующей формулой:

Ri=Si+w mod(k-1),

где R, — символ зашифрованного текста; S, — символ исходного текста;

w — целое число в диапазоне 0—(k- I); k — число символов

используемого алфавита.

Если w фиксировано, то формула описывает моноалфавитную ,

подстановку, если w выбирается из последовательности w^, w-^, ... w,„

^ то получается полиадфавитная подстановка с периодом п.

Если в полиалфавитной подстановке п > т (где т — число знаков

шифруемого текста) и любая последовательность w,, w;, ...

w„ используется только один раз, то такой шифр является теоретически

нераскрываемым, если, конечно, злоумышленник не имеет доступа к

исходному тексту. Такой шифр получил название шифра Вермэна.

Шифрование методом перестановки

Этот метод заключается в том, что символы шифруемого текста

переставляются по определенным правилам внутри шифруемого блока

символов. Рассмотрим некоторые наиболее часто встречающиеся

разновидности этого метода, которые могут быть использованы в

автоматизированных системах.

Самая простая перестановка — написать исходный текст задом наперед и

одновременно разбить шифрограмму на пятерки букв. Например, из фразы

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ. получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП

В последней группе (пятерке) не хватает одной буквы. Значит, прежде

чем шифровать исходное выражение, следует его дополнить незначащей

буквой (например, О) до числа, кратного пяти:

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительное изменение, будет

выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

Кажется, ничего сложного, но при расшифровке Проявятся серьезные

неудобства.

Во время Гражданской войны в США в ходу был такой шифр:

исходную фразу писали в несколько строк. Например, по пятнадцать букв

в каждой (с заполнением последней строки незначащими буквами).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

П У С Т Ь Б У Д Е Т т А К К А

К М ы х 0 Т Е •Л И к л М н 0 П

После этого вертикальные столбцы по порядку писали в строку с

разбивкой на пятерки букв:

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП

Вариант этого шифра: сначала исходную фразу записать в столбики:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

П С ь У Е Т К А М х т Л А В Д

У Т Б д Т А К К Ы 0 Е И Б Г Е

Потом разбить строки на пятерки букв:

ПСЬУЕ ТКАМХ ТЛАВД УТБДТ АККЫО ЕИБГЕ

Если строки укоротить, а количество строк увеличить, то получится

прямоугольник-решетка, в который можно записывать исходный текст. Но

тут уже требуются предварительные договоренности между адресатом и

отправителем посланий, поскольку сама решетка может быть различной

длины-высоты, записывать в нее можно по строкам, по столбцам, по

спирали туда или по спирали обратно, можно писать и по диагоналям, а

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

масса вариантов.

Для примера возьмем решетку 6х6 (причем количество строк может

увеличиваться или уменьшаться в зависимости от длины исходного

сообщения) и заполним ее по строкам:

Если шифровать по стрелкам (диагоналям) сверху вниз с левого верхнего

угла, то в итоге получится такая шифрограмма:

П УУ СДК ТЕКХ ЬТАОА БТКТБМ АМЕВЛ ЫЛГК ИДИ ЕЗ Ж

Для окончательного оформления шифротекст может быть разбит на группы

по 6 символов:

ПУУСДК ТЕКХЬТ АОАБТК ТБМАМЕ ВЛЫЛГК ИДИЕЗЖ

Весьма часто используют перестановки с ключом. Тогда правила

заполнения решетки и шифрования из нее упрощаются, становятся

стандартными. Единственное, что надо помнить и знать, ч*-; это ключ,

которым может быть любое слово, например РАДИАТОР. В соответствии с

расположением букв в алфавите буква А получает номер 1, вторая буква

А — 2, следующая по алфавиту буква Д — 3, потом И — 4, О — 5, первая

буква Р — 6, вторая Р.— 7 и буква Т — 8. Заполняем решетку:

Р А д и А т 0 Р

6 1 3 4, 2 8 5 7

П У с Т Ь Б У Д •

Е Т т А К К А к

М Ы х 0

Т Е Л'

Записываем столбики в соответствии с номерами букв ключа:

УТЫ ЬКТ СТХ ТАО УАЛ ПЕМО ДКИ БКЕ ; . Затем последовательность опять

разбивается Hd пятерки:

" УТЫЬК ТСТХТ АОУАЛ ПЕМОД КИБКЕ .•

Таким шифром простой перестановки колонок пользовались немецкие

секретные агенты во время Второй мировой войны. В качестве ключа они

использовали первые буквы строк на определенной странице какой-нибудь

обыкновенной книги.

Развитием этого шифра является шифр перестановки колонок с

пропусками, которые располагаются в решетке тоже в соответствии с

ключом (в нашем случае через 6-1-3-4-2-8-5-7 ... символов):

Р А д и А Т 0 Р

6 1 3 4

2 8 5 7

П У с 'Л

Ь Б = У"

=. д Е т = Т А К

к = Х 0 = Т Е л

и к Л М = 0 П Р

Шифрограмма будет такой:

УДК Ь СЕХЛ ТТОМ АЕП ПК^УКЛР БТТО

Из рассмотренных примеров очевидно, что все процедуры шифрования и

расшифровки по методу перестановок являются в достаточной степени

формальными и могут быть реализованы алгоритмически.

Шифрование методом гаммирования

Суть этого метода состоит в том, что символы шифруемого текста

последовательно складываются с символами некоторой специальной

последовательности, которая называется гаммой. Иногда такой метод

представляют как наложение гаммы на исходный текст, поэтому он

получил название «гаммирование».

Процедуру наложения гаммы на исходный текст можно осуществить двумя

способами.. При первом способе символы исходного текста и гаммы

заменяются цифровыми эквивалентами, которые затем складываются по

модулю k, где k — число символов в алфавите, т. е.

R,=(S,+G)mod(k- 1),

где Л„ S„ G — символы соответственно зашифрованного, исходного текста

и гаммы.

При втором методе символы исходного текста и гаммы представляются в

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

модулю 2. Вместо сложения по модулю 2 при гам-мировании можно

использовать и другие логические операции, например преобразование по

правилу логической эквивалентности (рис. 3.6, а) или логической

неэквивалентности (рис. 3.6, б).

Такая замена равносильна введению еще одного ключа, которым является

выбор правила формирования символов зашифрованного сообщения из

символов исходного текста и гаммы.

Стойкость шифрования методом гаммирования определяется главным

образом свойствами гаммы — длительностью периода и

равномерностью статистических характеристик. Последнее свойство

обеспечивает отсутствие закономерностей в появлении различных

символов в пределах периода.

Обычно разделяют две разновидности гаммирования — с конечной и

бесконечной гаммами. При хороших статистических свойствах гаммы

стойкость шифрования определяется только длиной периода гаммы. При

этом, если длина периода гаммы превышает длину шифруемого текста, то

такой шифр теоретически является абсолютно стойким, т. е. его нельзя

вскрыть при помощи статистической обработки зашифрованного текста.

Это, однако, не означает, что дешифрование такого текста вообще

невозможно: при наличии некоторой дополнительной информации исходный

текст может быть частично или полностью восстановлен даже при

использовании бесконечной гаммы.

В качестве гаммы может быть использована любая последовательность

случайных символов, например последовательность цифр числа л, числа е

(основание натурального логарифма) и т. п. При шифровании с помощью

ЭВМ последовательность гаммы может формироваться с помощью датчика

псевдослучайных чисел (ПСЧ). В настоящее время разработано несколько

алгоритмов работы таких датчиков, которые обеспечивают

удовлетворительные характеристики гаммы.

Шифрование с помощью аналитических преобразований

Достаточно надежное закрытие информации может быть обеспечено при

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

Для этого можно использовать методы алгебры матриц, например

умножение матрицы на вектор по правилу:

Если матрицу А = (д„) использовать в качестве ключа, а вм'есто

компонента вектора В = (йу) подставить символы текста, то компоненты

вектора С=(Су) будут представлять собой символы зашифрованного

текста.

Приведем пример, взяв в качестве 1<люча квадратную матрицу третьего

порядка ; „'

Заменим буквы алфавита цифрами, соответствующими их порядковому

номеру в алфавите: А—0, Б—1, В—2 и т. д. Тогда отрывку текста ВАТАЛА

будет соответствовать последовательность 2, 0, 19, О, 12, 0. По

принятому алгоритму шифрования выполним необходимые действия:

При этом зашифрованный текст будет иметь вид: 85, 54,' 25, 96, 60,

24. •. ' .

''""

;

' •

Дешифрование осуществляется с использованием того же правила

умножения матрицы на вектор, только в качестве ключа берется матрица,

обратная той, с помощью которой осуществляется зшифрование, а в

качестве вектора-сомножителя — соответствующие фрагменты символов

закрытого текста; тогда значениями вектора-результата будут цифровые

эквиваленты знаков открытого текста.

Матрицей, обратной данной А, называется матрица^'', получающая из

присоединенной матрицы делением всех ее элементов на определитель

данной матрицы. В свою очередь присоединенной называется матрица,

составленная из алгебраических дополнений Ау, к элементам данной

матрицы, которые вычисляются по формуле:

Ау=(-\У^,,

где А,. — определитель матрицы, получаемой вычеркиванием /-и строки и

j-ro столбца исходной матрицы А.

Определителем матрицы называется алгебраическая сумма п! членов (для

определителя п-го порядка), составленная следующим образом: членами

служат всевозможные произведения п элементов матрицы, взятых по

одному в каждой строке и в каждом столбце, причем член суммы берется

со знаком «+», если его индексы составляют четную подстановку, и со

знаком «-» — в противоположном случае. Для матрицы третьего порядка,

например, определитель вычисляется следующим образом:

Д = йца^ЯзЗ + ^^Э] +

•l^

32 - ОцЯ23"32 - ^^ЗЗ - ^З^ЗГ

Тогда процесс раскрытия выглядит так:

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

3, 0, 19, 0, 12, 0, что соответствует исходному тексту. Этот метод

шифрования является формальным, что позволяет легко реализовать его

программными средствами.

Комбинированные методы шифрования

Одним из важнейших требований, предъявляемых к системе шифрования,

является ее высокая стойкость. Однако повышение стойкости любого

метода шифрования приводит, как правило, к существенному усложнению

самого процесса шифрования и увеличению затрат ресурсов (времени,

аппаратных средств, уменьшению пропускной способности и т. п.).

Достаточно эффективным средством повышения стойкости шифрования

является комбинированное использование нескольких различных способов

шифрования, т. е. последовательное шифрование исходного текста с

помощью двух или более методов.

Как показали исследования, стойкость комбинированного шифрования 5^

не ниже произведения стойкостей используемых способов S„ т. е.

Вообще говоря, комбинировать можно любые методы шифрования и в любом

количестве, однако на практике наибольшее распространение получили

следующие комбинации: 1) подстановка + гам-мирование; 2) перестановка

+ гаммирование; 3) гаммирование + + гаммирование; 4) подстановка +

перестановка. Типичным примером комбинированного шифра является

национальный стандарт США криптографического закрытия данных

(DES). ,. '

Кодирование „ •'!•:

Одним из средств криптографического закрытия информации, также

имеющим длительную историю практического использования, является

кодирование, под которым понимается замена эле-

ментов закрываемых данных некоторыми цифровыми, буквенными или

комбинированными сочетаниями — кодами. Нетрудно заметить, что между

кодированием информации и ее шифрованием подстановкой существует

значительная аналогия. Однако между этими методами можно найти и

различия.

При шифровании подстановкой заменяемыми единицами информации являются

символы алфавита, и, следовательно, шифрованию могут подвергаться

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

При кодировании замене подвергаются смысловые элементы информации,

поэтому для каждого специального сообщения в общем случае необходимо

использовать свою систему кодирования. Правда, в последнее время

разработаны специальные коды, имеющие целью сократить объем

информации при записи ее в ЗУ. Специфика этих кодов заключается в

том, что для записи часто встречающихся символов используются

короткие двоичные коды, а для записи редко встречающихся — длинные.

Примером такого кода для английского языка может служить код

Хаффмена, показанный в табл. 3.2.

Такое кодирование имеет криптографическую стойкость на уровне

шифрования простой заменой.

При смысловом кодировании основной кодируемой единицей является

смысловой элемент текста. Для кодирования составляется специальная

таблица кодов, содержащая перечень кодируемых элементов и

соответствующих им кодов. Введем, например, следующую кодовую

таблицу:

Автоматизированные системы управления 001 Автоматизация управления

002 Осуществляет ,415 Позволяет 632

Тогда предложение «Автоматизированные системы управления позволяют

осуществлять автоматизацию управления» после кодирования будет иметь

вид: 001 632 415 002.

Другие виды криптографического закрытия информации К ним относятся

рассечение-разнесение и сжатие данных. Рассечение-разнесение данных

состоит в том, что массив защищаемых данных рассекается на такие

элементы, каждый из которых не позволяет раскрыть содержание

защищаемой информации, и выделенные таким образом элементы

размещаются в различных зонах ЗУ. Обратная процедура называется

сборкой данных. Совершенно очевидно, что алгоритм разнесения и сборки

данных должен тщательно охраняться.

Таблица 3.2. Коды Хаффмека

А 1 г 1 1 -

^•^

0 1 . ,

1..

. 1 0 Ji/

'.:

N 1. t 0

.'-

100