Литвиненко А.В. Методы и средства защиты информации

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

Анализ основных криптографических методов ЗИ 361

Если в полиалфавитной подстановке n > m (где m — количество знаков шифруемо-

го текста) и любая последовательность

, ω

, …, ω

используется только один раз, то

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

к исходному тексту. Этот шифр называют шифром Вермана.

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

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

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

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

по таблице и усложненный по маршрутам перестановки.

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

Шифрование простой перестановкой осуществляется следующим образом:

• выбирается ключевое слово с неповторяющимися символами;

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

чевого слова;

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

располагаются в алфавите буквы ключа (или в порядке следования цифр в натураль-

ном ряду, если он цифровой).

Рассмотрим следующий пример:

открытый текст: БУДЬТЕ ОСТОРОЖНЫ

ключ: 5 8 1 3 7 4 6 2

схема шифрования:

5 8 1 3 7 4 6 2

Б У Д Ь Т Е α O

С Т О Р О Ж Н Ы

(α — пробел)

Группируем по 2 символа и получаем зашифрованный текст:

1 2 3 4 5 6 7 8

ДООЫЬРЕЖБСαНТОУТ

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

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

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

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

шифрования можно существенно повысить. При этом, однако, усложняется организация

процесса шифрования и дешифрования

Усложненный метод перестановки по таблицам

362 Глава 18. Криптографическая защита

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

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

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

рой могут быть выбраны произвольно (например 10 × 10). В нее, как и в случае простой

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

в том, что

определенное число клеток таблицы не используется. Количество и расположение неис-

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

текст блоками по

m × n – S элементов записывается в таблицу (m × n — размеры таб-

лицы,

S — количество неиспользуемых элементов). Далее процедура шифрования ана-

логична простой перестановке.

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

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

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

Усложненный метод перестановок по маршрутам

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

метод перестановок по маршрутам типа гамильтоновских. При этом для записи символов

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

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

личных маршрутов (рис. 18.5).

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

пере-

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

алгоритмически.

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

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

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

ды алгебры матриц, например, умножение матрицы на вектор по правилу

||a

|| b

= C

Анализ основных криптографических методов ЗИ 363

Рис. 18.5. Схема шифрования перестановкой по маршрутам Гамильтона.

Открытый текст "КРИПТОГР", зашифрованный текст —

"ТОРКИПРГ" (вверху) и "ТКИПРОРГ" (внизу)

Если матрицу

||a

|| использовать в качестве ключа, а вместо компонента вектора b

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

будут представлять

собой символы зашифрованного текста.

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

которая будет играть роль ключа:

⎪

14 8 3

852

321

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

фавите:

А = 0; Б = 1; В = 2 и т.д. Тогда тексту ВАТАЛА (текст произвольный) будет

соответствовать последовательность

3, 0, 19, 0, 12, 0. По принятому алгоритму шифро-

вания выполним необходимые действия:

⎪

14 8 3

852

321

⎪

14 8 3

852

321

⎪

Таким образом, зашифрованный текст будет иметь следующий вид:

99, 62, 28, 96, 60, 24

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

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

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

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

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

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

364 Глава 18. Криптографическая защита

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

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

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

текст, поэтому он получил название “гаммирование”.

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

ми. В первом способе символы

исходного текста и гаммы заменяются цифровыми экви-

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

К, где К — количество символов в

алфавите, т.е.

= (t

+ t

) mod К, где t

, t

— символы соответственно зашифрован-

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

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

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

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

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

логической

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

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

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

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

ствами гаммы — длительностью периода и равномерностью статистических характери-

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

личных символов

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

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

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

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

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

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

вообще не возможно: при наличии неко-

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

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

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

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

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

помощью датчика псев-

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

которые обеспечивают удовлетворительные характеристики.

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

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

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

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

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

скной способности и т.п.).

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

является

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

следовательное шифрование исходного текста с помощью двух или более методов.

Анализ основных криптографических методов ЗИ 365

Стойкость комбинированного шифрования S

не ниже произведения стойкости ис-

пользуемых способов

S: S

≥ П S

Совершенно очевидно, что если какой-либо способ шифрования при независимом

его применении может обеспечить стойкость не ниже

(например, гаммирование с

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

лишь при выполнении условия

< R

, где R

— ресурсоемкость i-го способа, ис-

пользуемого при комбинированном шифровании;

— ресурсоемкость того способа,

который обеспечивает стойкость не ниже

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

практике наибольшее распространение получили следующие комбинации:

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

• перестановка + гаммирование;

• гаммирование + гаммирование;

• подстановка + перестановка.

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

США криптографического закрытия данных (DES).

Кодирование

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

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

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

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

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

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

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

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

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

подвергаются смысловые элементы информации, поэтому для каждого специального со-

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

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

имеющие целью сократить объем

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

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

редко встречающихся — длинные. Примером такого кода может служить код Хоффма-

на.

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

единиц на

маршруте от вершины графа до конца ветви, соответствующего данной букве.

Если граф кодирования сохраняется в тайне, то такое кодирование имеет криптографи-

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

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

элемент текста. Для кодирования составляется специальная таблица кодов, содержащая

перечень кодируемых элементов и соответствующих

им кодов.

366 Глава 18. Криптографическая защита

Иногда код состоит из списка слов и фраз вместе с соответствующими им случайны-

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

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

обеспечивают также и сжатие информации.

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

ческие системы

. Успех их использования объясняется тремя причинами. Наиболее важ-

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

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

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

щий в среднем 90 бит, тогда как кодовая книга хорошего размера может

содержать сот-

ни тысяч и даже миллион бит. Как показал Шеннон, работа криптоаналитика затрудня-

ется, когда из сообщения удаляется избыточность, а коды удаляют избыточность. При-

чем, коды работают с относительно большими блоками открытого текста (словами и

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

случае могла бы дать ценные “зацепки

” для криптоанализа.

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

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

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

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

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

По этим причинам для обеспечения большей на-

дежности коды необходимо чаще менять.

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

сжатие данных. Рассечение/разнесение данных состоит в том, что массив защищаемых

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

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

элементы размеща-

ются в различных зонах памяти. Обратная процедура называется сборкой данных. Со-

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

тайне.

Шифрование с открытым ключом

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

связано с трудностью распространения ключей. Диффи и Хеллман, а также, независимо

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

при этом обеспечить защиту при передаче сообщений по незащищенному каналу без

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

. 18.6, меж-

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

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

хранятся в секрете, системы, допускающие такую работу, называются системами с от-

крытым ключом.

Анализ основных криптографических методов ЗИ 367

Рис. 18.6. Поток информации в криптографической системе с открытым ключом

Для решения этой проблемы предлагаются два подхода. При открытом распростра-

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

обычной криптографической системе. Несмотря на то, что противник слушает все пере-

говоры, он не в состоянии вычислить ключ и не

может понять последующего обмена со-

общениями. Второй подход реализует криптографические системы с открытыми ключа-

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

Причина, по которой ключи в обычных криптографических системах должны столь

тщательно защищаться, состоит в том, что функции шифрования и дешифрования в

ней неразделимы. Любое лицо, получившее ключ для

шифрования сообщений, может

также дешифровать сообщения. Если средства шифрования разделены, то секретность

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

зовать для расшифровывания.

Взаимодействуя по открытым каналам связи, абоненты А и В решают следующие за-

дачи:

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

такая общая секретная информация (общий ключ) у А и В появляется, т.е. вырабаты-

вается;

• противник, который перехватывает все передачи и знает, что хочет получить А и В,

тем не менее не может восстановить выработанный общий ключ А и В.

Предложено решать эти задачи с помощью функции

F(x) = α

(mod p), где р —

большое простое число,

x — произвольное натуральное число, α — некоторый прими-

тивный элемент поля

G F(p).

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

α из G F(p), что каждый элемент поля,

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

α. Доказывается, что примитивный элемент все-

гда существует.

Общепризнанно, что инвертирование функции

(mod p), т.е. дискретное логариф-

мирование, является трудной математической задачей.

Саму же процедуру или, как принято говорить, протокол выработки общего ключа,

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

Числа

р и α считаются общедоступными.

368 Глава 18. Криптографическая защита

Абоненты А и В независимо друг от друга случайно выбирают по одному натураль-

ному числу — скажем

и x

и. Эти элементы они держат в секрете. Далее каждый из

них вычисляет новый элемент:

= α

(mod p), у

= α

(mod p)

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

получив

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

, вычисляет новый элемент:

= (α

)

(mod p)

Аналогично поступает абонент В:

= (α

)

(mod p)

Из свойств поля следует, что тем самым у А и В появится общий элемент, который и

является общим ключом А и В.

Из описания протокола видно, что противник знает

p, α, α

, α

, не знает x

, x

хочет узнать

. В настоящее время нет алгоритмов действий противника, более эф-

фективных, чем дискретное логарифмирование, а это — труднейшая математическая за-

дача.

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

случайных пар инверсных ключей

Е для шифрования и Д для дешифрования и работу с

этими ключами, но чтобы вычисления

Д по Е было вычислительно нереализуемым.

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

алгоритмов

}

K∈{K}

и {Д

}

K∈{K}

, определяющих обратимые преобразования

EK:{M}→{m}

ДK:{M}→{m}

на конечном пространстве сообщений {M} со следующими свойствами.

1. Для каждого K∈{K} Д

обратно к E

K ,

т.е. при любых К и М справедливо Д

(М)

= М

2. Для каждого K∈{K} и M∈{M} нетрудно вычислить величины Е

(М) и Д

(М).

3. Для почти каждого K∈{K} невозможно в вычислительном отношении вывести из Е

какой-либо легко выполнимый алгоритм, эквивалентный Д

4. По каждому заданному K∈{K} можно получить инверсную пару Е

и Д

Свойство 3 позволяет не засекречивать ключи шифрования пользователя

и при

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

. Следовательно,

криптогафические системы распадаются на две части (семейство преобразований шиф-

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

члену одного семейства невозможно определить соответствующий член другого.

Свойство 4 гарантирует наличие реализуемого пути вычисления соответствующих

пар обратных преобразований, когда не наложено никаких ограничений на то, каким

должно быть преобразование шифрования

или дешифрования. На практике криптогра-

Цифровая подпись 369

фическое оборудование должно содержать генератор истинных случайных чисел для ге-

нерации

К, а также генерирующий пару E

по заданному K.

Система такого рода упрощает проблему распределения ключей. Каждый пользова-

тель генерирует пару взаимно обратных преобразований

Е и Д. Он держит преобразова-

ние дешифрования

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

справочнике наподобие технического справочника. Теперь любой желающий может

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

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

Если вместо приведенных условий 1–4 множество преобразований обеспечивает, что

для каждого

K∈{K} E

является обратным Д

, т.е. при любых К и М справедливо ут-

верждение

(М) = М, то возможно, а часто и желательно осуществлять шифрова-

ние с помощью ключа

Д, а дешифрование — с помощью ключа Е. По этой причине час-

то называют

открытым ключом, а Д

— личным ключом.

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

сколько путей ее реализации.

Цифровая подпись

Идея цифровой подписи (ее еще называют электронной подписью) была предложе-

на Диффи и Хеллманом. Суть ее заключается в использовании односторонней функции с

секретом

. В настоящее время эта идея реализована в большом количестве систем пе-

редачи данных. Сообщение, подписанное цифровой подписью, можно представить в ви-

де пары

(x,y), где x — сообщение, F

: x → y —односторонняя функция, известная всем

взаимодействующим абонентам,

y — решение уравнения F

(y) = x. Из определения

функции

очевидны следующие достоинства цифровой подписи.

1. Подписать сообщение x, т.е. решить уравнение F

(y) = x, может только абонент, яв-

ляющийся обладателем данного секрета

К; другими словами, подделать подпись не-

возможно.

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

т.е. саму функцию

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

ваемости.

5. Подписанные сообщения (x,y) можно, не опасаясь ущерба, пересылать по любым ка-

налам связи.

Именно перечисленные достоинства и обусловили широкой применение и распро-

странение систем цифровой подписи.

Как практически выглядит использование цифровой подписи? Рассмотрим, как осу-

ществляется работа банка с платежными поручениями своих клиентов. Все абоненты

этой сети знают одностороннюю функцию

, и каждый клиент имеет собственный, ни-

кому неизвестный секрет

К. Клиент подписывает платежное поручение x с помощью

функции

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

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

370 Глава 18. Криптографическая защита

подписи клиента и только после этого выполняет его платежное поручение. В силу от-

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

пострадают.

Широкое развитие систем электронных платежей, электронной почты и других сис-

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

привело к развитию теории протоколов

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

составляет большой раздел теоретической криптографии. В рамках этой теории система-

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

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

подписи. Удалось также доказать эквивалентность существования двух гипотетических

объектов: односторонней функции и стойкой схемы

цифровой подписи.

Криптографическая система RSA

Как бы ни были сложны и надежны классические криптографические системы, их

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

Для того чтобы был возможен обмен конфиденциальной информацией между двумя

абонентами, ключ должен быть сгенерирован одним из них, а затем каким-либо образом

передан другому в конфиденциальном порядке. В общем случае

для передачи ключа по

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

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

Для решения этой и ряда других проблем были предложены криптосистемы с

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

Перед отправкой сообщения адресату исходный текст шифруется открытым (обще-

доступным) ключом адресата

. Алгоритм шифрования построен таким образом, что рас-

шифровывание сообщения возможно только с использованием личного (секретного)

ключа адресата.

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

Диффи и Хеллманом в 1976 году.

Суть этой модели состоит в том, что ключ известен полностью только получателю

сообщения и представляет собой тройку чисел

k = (е, d, n), где подключ e служит клю-

чом шифрования, а ключ

d — ключом расшифровывания. При этом только d является

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

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

роннюю функцию с лазейкой. Вычисление значения такой функции (от открытого текста

и параметра

e) должно быть несложным, в то же время ее обращение должно быть вы-

числительно нереализуемым без знания секретной информации, “лазейки”, связанной с

секретным ключом

В криптосистеме с открытым ключом сообщение, предназначенное абоненту, за-

шифровывается отправителем с помощью ключа

e и расшифровывается получателем с

помощью ключа

d. Если шифрпреобразование действительно является односторонней

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

тограмму.