Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Институт гуманитарного образования и информационных технологий

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Информационная безопасность / Общий_лекция

.pdf

Скачиваний:

Добавлен:

05.02.2016

Размер:

7.84 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 4713 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

121

Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около

50 г. до н.э.).

При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К= 3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифртекста. Совокупность возможных подстановок для К= 3 показана в табл. 2.3.

Например, послание Цезаря

VENI VIDI VICI

(в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию после победы над понтийским царем Фарнаком, выглядело бы в зашифрованном виде так:

YHQL YLGL YLFL

Таблица 2.3 Одноалфавитные подстановки (К = 3, m = 26)

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

Определение. Подмножество Cm={Ck: 0 k<m} симметрической группы SYM(Zm), содержащее m подстановок

Ck: j (j+k) (mod m), 0 k < m,

называется подстановкой Цезаря.

Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1 ,..,xn-1) в n-грамму шифрованного текста (y0 ,y1 ,...,yn-1) в соответствии с правилом

yi=Ck(xi), 0 i<n.

Система Цезаря с ключевым словом

Система шифрования Цезаря с ключевым словом является одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки [79].

Выберем некоторое число к, 0<к<25, и слово или короткую фразу в качестве

122

ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число к = 5.

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

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

Теперь мы имеем подстановку для каждой буквы произвольного сообщения. Исходное сообщение SEND MORE MONEY

шифруется как HZBY TCGZ TCBZS

Следует отметить, что требование о различии всех букв ключевого слова не обязательно. Можно просто записать ключевое слово (или фразу) без повторения одинаковых букв. Например, ключевая фраза

КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН

и число к = 3 порождают следующую таблицу подстановок:

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

123

3.2. Многоалфавитные подстановки.

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

При r-алфавитной подстановке символ х0 исходного сообщения заменяется символом у0 из алфавита В0, символ Xi-символом у, из алфавита В,, и так далее, символ хг_, заменяется символом уг_, из алфавита Вг_ь символ хг заменяется символом уг снова из алфавита В0, и т.д.

Общая схема многоалфавитной подстановки для случая г = 4 показана на рис.

2.7.

Рис. 2.7. Схема r-алфавитной подстановки для случая г = 4

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

Многоалфавитные шифры замены предложил и ввел в практику, криптографии Леон Батист Альберти, который также был известным архитектором и теоретиком искусства. Его книга "Трактат о шифре", написанная в 1566 г., представляла собой первый в Европе научный труд по криптологии. Кроме шифра многоалфавитной замены, Альберти также подробно описал устройства из вращающихся колес для его реализации. Криптологи всего мира почитают Л.Альберти основоположником криптологии [32].

3.1. Система шифрования Вижинера

Система Вижинера впервые была опубликована в 1586 г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени французского дипломата XVI века Блеза Вижинера, который развивал и совершенствовал криптографические системы.

124

Система Вижинера подобна такой системе шифрования Цезаря, у которой ключ подстановки меняется от буквы к букве. Этот Шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. На рис. 2.8 и 2.9 показаны таблицы Вижинера для русского и английского алфавитов соответственно.

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

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

•крайний левый столбец ключа.

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

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

Рассмотрим пример получения шифртекста с помощью таблицы Вижинера. Пусть выбрано ключевое слово АМБРОЗИЯ. Необходимо зашифровать сообщение ПРИЛЕТАЮ СЕДЬМОГО.

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

Сообщение	ПРИЛЕТАЮ	СЕДЬМОГО
Ключ	АМБРОЗИЯ	АМБРОЗИЯ
Шифртекст	ПЪЙЫУЩИЭ	ССЕКЬХЛН

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

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

125

126

Пример шифрования с помощью таблицы Вижинера

127

«Таблица Виженера» устроена следующим образом: в первой строке выписывается весь алфавит, в каждой следующей осуществляется циклический сдвиг на одну букву. Так получается квадратная таблица, число строк которой равно числу столбцов и равно числу букв в алфавите. «Таблица Виженера» (табл. 2.8.), составлена из 31 буквы русского алфавита (без буквы Ё).

Чтобы зашифровать какое-нибудь сообщение, поступают следующим образом. Выбирается ключевое слово – лозунг (например, «монастырь») и подписывается с повторением над буквами сообщения (рис. 2).


М О Н А С	Т Ы Р			Ь	М О Н А		С Т Ы	Р Ь М О Н

Р А С К И	Н	У	Л	О С Ь		М О	Р Е Ш	И Р О К О

Э О Я К Щ А		П	Ы Й		Ю Й	Щ О В Ч Ф Ш Л Ь Ш Ы

Рис. 2. Пояснение процесса шифрования с помощью таблицы Виженера

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

горизонтальном алфавите таблицы. В данном примере сначала находим столбец, отвечающий букве «М» лозунга, а затем строку, соответствующую букве «Р» открытого текста. На пересечении выделенных столбца и строки находим букву «Э» Так продолжая дальше, находим шифрованный текст полностью (см. рис. 2).

Чтобы расшифровать шифрованный текст необходимо иметь ключевое слово

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

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

128

М О Н А С Т Ы Р Ь М О Н А С Т Ы Р Ь М О Н

Э О Я К Щ А П Ы Й Ю Й Щ О В Ч Ф Ш Л Ь Ш Ы

Рис. 3. Пояснение процесса расшифровывания с помощью таблицы Виженера

Таблица 3 (Таблица Виженера)

129

4. Гаммирование (Потоковое шифрование)

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

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

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

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

Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок ПСП и по нему восстанавливается вся последовательность. Злоумышленники может сделать это на основе догадок о содержании исходного текста. Так, если большинство посылаемых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается. Это следует учитывать при создании реальных систем информационной безопасности.

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

Датчики ПСЧ

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

Конгруэнтные датчики

В настоящее время наиболее доступными и эффективными являются конгруэнтные генераторы ПСП. Для этого класса генераторов можно сделать мате-

130

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

T(i+1) = (A*T(i)+C) mod m,

где А и С - константы, Т(0) - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик ПСЧ генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n , где n - длина машинного слова в битах. Датчик имеет максимальный период М до того, как генерируемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период М был максимальным. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечетное, и А mod 4 = 1.

Для шифрования данных с помощью датчика ПСЧ может быть выбран ключ любого размера. Например, пусть ключ состоит из набора чисел x(j) размерностью b, где j=1, 2, ..., n. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств H(j).

Датчики М-последовательностей

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

М-последовательности представляют собой линейные рекуррентные последовательности максимального периода, формируемые k-разрядными генераторами на основе регистров сдвига. На каждом такте поступивший бит сдвигает k предыдущих и к нему добавляется их сумма по модулю 2. Вытесняемый бит добавляется к гамме.

Строго это можно представить в виде следующих отношений:

r1:=r0 r2:=r1 ... rk-1:=rk-2 r0:=a0 r1 a1 r2 ... ak-2 rk-1

Гi:= rk-

Здесь r0 r1 ... rk-1 - k однобитных регистров, a0 a1 ... ak-1 - коэффициенты неприводимого двоичного полинома степени k-1. Гi - i-е значение выходной гаммы.

Период М-последовательности исходя из ее свойств равен 2k-1.

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для заданного k. Эта характеристика приведена в таблице:

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 4713 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

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

#
05.02.201689.09 Кб27Мет_указ_ПР_1.doc
#
05.02.20167.84 Mб88Общий_лекция.pdf
#
05.02.2016795.5 Кб33Т2_3_Матем_основ.pptx
#
05.02.2016556.73 Кб15Табл_Вижин.docx