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

Вид материала

Методические указания

Содержание Криптографические методы преобразования информации. методы замены и подстановки 3.1. Цели работы 3.2. Теоретическая часть Методом шифрования (шифром) Таблица 3.1 Таблица замен Рис. 3.3. Матрица Вижинера Рис. 3.5. Пример шифрования с помощью матрицы Вижинера 3.4. Требования к оформлению отчета Варианты заданий

Подобный материал:

• Методические указания к выполнению лабораторных работ для студентов, обучающихся, 99.32kb.
• Методические указания к выполнению лабораторных работ по дисциплине «Интеллектуальные, 653.36kb.
• Методические указания по выполнению практических/лабораторных работ для студентов, 652.21kb.
• Методические указания к выполнению лабораторных работ по дисциплине информатика для, 1065.17kb.
• Методические указания по их выполнению по дисциплине «исследование систем управления», 134.73kb.
• Методические указания к выполнению курсовых работ по дисциплине «Система государственного, 329.69kb.
• Методические указания к выполнению лабораторных работ по курсу «вычислительная техника, 640.55kb.
• Методические указания по выполнению курсовых работ по дисциплине «Экономический анализ», 282.08kb.
• Методические указания к проведению лабораторных работ. Специальность 23. 01. 02 «Автоматизированные, 1178.37kb.
• Методические указания по выполнению контрольных работ и домашних заданий (рефератов), 314.07kb.

КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ

ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ. МЕТОДЫ ЗАМЕНЫ И ПОДСТАНОВКИ

3.1. Цели работы:	рассмотреть понятие криптографической защиты информации;
	ознакомиться с классификацией методов криптографического преобразования информации;
	изучить методы прямой и полиалфавитной замены;
	изучить методы перестановок.

3.2. Теоретическая часть


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

преобразования информации


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

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





Рис. 3.1. Классификация методов криптографического

преобразования информации


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

Шифрование - основной вид криптографического преобразования информации в КС. Под шифрованием понимается процесс преобразования открытой информации в зашифрованную информацию (шифртекст) или процесс обратного преобразования зашифрованной информации в открытую. Процесс преобразования открытой информации в закрытую получил название зашифрование, а процесс преобразования закрытой информации в открытую - расшифрование.

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

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




Рис. 3.2. Классификация методов шифрования


Рассмотрим некоторые методы шифрования с симметричным ключом.


3.2.2. Метод прямой замены (моноалфавитной подстановки)


Сущность методов замены (подстановки) заключается в замене символов исходной информации, записанных в одном алфавите, символами из другого алфавита по определенному правилу. Самым простым является метод прямой замены. Символам S_0i исходного алфавита А₀, с помощью которых записывается исходная информация, однозначно ставятся в соответствие символы S_1i; шифрующего алфавита A₁. В простейшем случае оба алфавита могут состоять из одного и того же набора символов. Например, оба алфавита могут содержать буквы русского алфавита.

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

Алгоритм моноалфавитной замены может быть представлен в виде последовательности шагов.

Шаг 1. Формирование числового кортежа L_0h путем замены каждого символа s_0iТ₀(i=), представленного в исходном алфавите А₀ размера [1R], на число h_0i(s_0i), соответствующее порядковому номеру символа S_0i в алфавите А₀.

Шаг 2. Формирование числового кортежа L_1h путем замены каждого числа кортежа L_0h на соответствующее число h_1i; кортежа L_1h, вычисляемое по формуле:

h_1i, = (k₁  h_0i(s_0i)+k₂)(mod R),

где k₁ - десятичный коэффициент;

k₂ - коэффициент сдвига.

Выбранные коэффициенты k₁, k₂ должны обеспечивать однозначное соответствие чисел h_0i и h_1i, а при получении h_1i = 0 выполнить замену h_1i=R.

Шаг 3. Получение шифртекста Т₁ путем замены каждого числа h_1i(s_1i) кортежа L_1h соответствующим символом s_1i  T₁ (i=) алфавита шифрования A₁ размера [1R].

Шаг 4. Полученный шифртекст разбивается на блоки фиксированной длины b. Если последний блок оказывается неполным, то в конец блока помещаются специальные символы-заполнители (например, символ *).


Пример. Исходными данными для шифрования являются:

Т₀= <МЕТОД_ШИФРОВАНИЯ>;

А₀=<А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _>;

А₁=<О Р Щ Ь Я Т Э _ Ж М Ч Х А В Д Ы Ф К С Е З П И Ц Г Н Л Ъ Ш Б У Ю>;

R=32; k₁=3; k₂=15, b=4.

Пошаговое выполнение алгоритма приводит к получению следующих результатов.

Шаг 1. L_0h= <12, 6, 18, 14, 5, 32, 24, 9, 20, 16, 14, 3, 1, 13, 9, 31>.

Шаг 2. L_1h= <19, 1, 5, 25, 30, 15, 23, 10, 11, 31, 25, 24, 18, 22, 10, 12>.

Шаг З. Т1=<СОЯГБДИМЧУГЦКПМХ>.

Шаг 4. Т2=<СОЯГ БДИМ ЧУГЦ КПМХ>.

При расшифровании сначала устраняется разбиение на блоки. Получается непрерывный шифртекст T_i длиной К символов. Расшифрование осуществляется путем решения целочисленного уравнения:

K₁h_0i+k₂=nR+h_1i,

При известных целых величинах k₁, k₂, h_1i и R величина h_0i вычисляется методом перебора n.

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

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


Таблица 3.1

Таблица замен

s0i	А	Б	В	Г	Д	Е	Ж	З	И	К	Л	М	Н	О	П	Р
h0i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
s1i	К	З	Ц	Л	Б	О	Ь	Э	М	А	Ы	С	П	Г	Ъ	У
h1i	18	21	24	27	30	1	4	7	10	13	16	19	22	25	28	31
s0i	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я	_
h0i	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
s1i	Р	Я	_	Ч	В	Ф	Е	И	Н	Ш	Ю	Щ	Т	Ж	Х	Д
h1i	2	5	8	11	14	17	20	23	26	29	32	3	6	9	12	15

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

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


3.2.3. Метод полиалфавитной замены


Существенно более стойкими являются методы полиалфавитной замены. Такие методы основаны на использовании нескольких алфавитов для замены символов исходного текста. Формально полиалфавитную замену можно представить следующим образом. При N - алфавитной замене символ s₀₁ из исходного алфавита А₀ заменяется символом s₁₁ из алфавита A₁, s₀₂ заменяется символом s₂₂ из алфавита А₂ и так далее. После замены S_on символом s_nn из A_n символ S_0(n+i) замещается символом S_1(n+1) из алфавита A₁ и так далее.

Наибольшее распространение получил алгоритм полиалфавитной замены с использованием таблицы (матрицы) Вижинера Тв, которая представляет собой квадратную матрицу [RR], где R - количество символов в используемом алфавите. В первой строке располагаются символы в алфавитном порядке. Начиная со второй строки, символы записываются со сдвигом влево на одну позицию. Выталкиваемые символы заполняют освобождающиеся позиции справа (циклический сдвиг). Если используется русский алфавит, то матрица Вижинера имеет размерность [3232] (рис. 3.3).

А

Б

В

Г

Д

.

.

.

.

.

.

.

Ь

Ы

Ъ

Э

Ю

Я

_

Б

В

Г

Д

Е

.

.

.

.

.

.

.

Ы

Ъ

Э

Ю

Я

_

А

Тв

=

В

Г

Д

Е

Ж

.

.

.

.

.

.

.

Ъ

Э

Ю

Я

_

А

Б

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

_

А

Б

В

Г

.

.

.

.

.

.

.

Э

Ю

Я

_

А

Б

В

Рис. 3.3. Матрица Вижинера


Шифрование осуществляется с помощью ключа, состоящего из М неповторяющихся символов. Из полной матрицы Вижинера выделяется матрица шифрования Т_ш, размерностью [(M+1),R]. Она включает первую строку и строки, первые элементы которых совпадают с символами ключа. Если в качестве ключа выбрано слово <ЗОНД>, то матрица шифрования содержит пять строк (рис. 3.4).

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

З

И

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

А

Б

В

Г

Д

Е

Ж

ТШ

=

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Д

Е

Ж

З

И

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

А

Б

В

Г

Рис. 3.4. Матрица шифрования для ключа <ЗОНД>


Алгоритм зашифрования с помощью таблицы Вижинера представляет собой следующую последовательность шагов.

Шаг 1. Выбор ключа К длиной М символов.

Шаг 2. Построение матрицы шифрования T_ш,=(b_ij) размерностью [(M+1), R] для выбранного ключа К.

Шаг 3. Под каждым символом s_0r исходного текста длиной I символов размещается символ ключа k_m, (рис. 3.5). Ключ повторяется необходимое число раз.

Шаг 4. Символы исходного текста последовательно замещаются символами, выбираемыми из Т_ш по следующему правилу:

1) определяется символ k_m ключа К, соответствующий замещаемому символу s_or;

2) находится строка i в Т_ш, для которой выполняется условие k_m=b_i1;

3) определяется столбец j, для которого выполняется условие:

s_or=b_1j;

4) символ s_or замещается символом b_ij.

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

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

Шаг 1. Под шифртекстом записывается последовательность символов ключа по аналогии с шагом 3 алгоритма зашифрования.

Шаг 2. Последовательно выбираются символы s_1r из шифртекста и соответствующие символы ключа k_m. В матрице Т_ш определяется строка i, для которой выполняется условие k_m= b_i1. В строке i определяется элемент b_ij =s_1r. В расшифрованный текст на позицию г помещается символ b_1j.

Шаг 3. Расшифрованный текст записывается без разделения на блоки. Убираются служебные символы.

Пример. Требуется с помощью ключа К = <ЗОНД> зашифровать исходный текст

Т = <БЕЗОБЛАЧНОЕ_НЕБО>. Механизмы зашифрования и расшифрования представлены на рис. 3.5.

Исходный текст

Б

Е

З

О

Б

Л

А

Ч

Н

О

Е

_

Н

Е

Б

О

Ключ

З

О

Н

Д

З

О

Н

Д

З

О

Н

Д

З

О

Н

Д

Текст после замены

И

У

Ф

Т

И

Ш

Н

Ы

Ф

Ы

Т

Г

Ф

У

О

Т

Шифртекст

И

У

Ф

Т

И

Ш

Н

Ы

Ф

Ы

Т

Г

Ф

У

О

Т

Ключ

З

О

Н

Д

З

О

Н

Д

З

О

Н

Д

З

О

Н

Д

Расшифрованный текст

Б

Е

З

О

Б

Л

А

Ч

Н

О

Е

_

Н

Е

Б

О

Исходный текст

Б

Е

З

О

Б

Л

А

Ч

Н

О

Е

_

Н

Е

Б

О

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


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

Для повышения крилтостойкости может использоваться модифицированная матрица шифрования. Она представляет собой матрицу размерности [11,R], где R - число символов алфавита. В первой строке располагаются символы в алфавитном порядке. Остальные 10 строк нумеруются от 0 до 9. В этих строках символы располагаются случайным образом.

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


3.2.4. Методы перестановки


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

Перестановки получаются за счет разницы путей записи исходной информации и путей считывания зашифрованной информации в пределах геометрической фигуры. Криптостойкость метода зависит от длины блока (размерности матрицы). Так для блока длиной 64 символа (размерность матрицы 8х8) возможны 1,6х10⁹ комбинаций ключа. Для блока длиной 256 символов (матрица размерностью 16х16) число возможных ключей достигает 1,4х10²⁶. Решение задачи перебора ключей в последнем случае даже для современных ЭВМ представляет существенную сложность.

Перестановки используются также в методе, основанном на применении маршрутов Гамильтона. Этот метод реализуется путем выполнения следующих шагов.

Шаг 1. Исходная информация разбивается на блоки. Если длина шифруемой информации не кратна длине блока, то на свободные места последнего блока помещаются специальные служебные символы-заполнители (например, *).

Шаг 2. Символами блока заполняется таблица, в которой для каждого порядкового номера символа в блоке отводится вполне определенное место (рис. 6).

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

Шаг 4. Зашифрованная последовательность символов разбивается на блоки фиксированной длины L. Величина L может отличаться от длины блоков, на которые разбивается исходная информация на шаге 1.

Расшифрование производится в обратном порядке. В соответствии с ключом выбирается маршрут и заполняется таблица согласно этому маршруту.

Таблица	маршрут 1	Маршрут 2

Рис. 3.6. Вариант 8-элементной таблицы

и маршрутов Гамильтона


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

Пусть требуется зашифровать исходный текст То = <МЕТОДЫ_ПЕРЕСТАНОВКИ>. Ключ и длина зашифрованных блоков соответственно равны: К=<2,1,1>, L=4. Для шифрования используются таблица и два маршрута, представленные на рис. 6. Для заданных условий маршруты с заполненными матрицами имеют вид, показанный на рис. 7.

Маршрут 2	Маршрут 1	Маршрут 1

Рис. 3.7. Пример шифрования с помощью

маршрутов Гамильтона


Шаг 1. Исходный текст разбивается на три блока:

Б1=<МЕТОДЫ_П>;

Б2 = <ЕРЕСТАНО>;

БЗ = <ВКИ*****>.

Шаг 2. Заполняются три матрицы с маршрутами 2,1,1 (рис. 3.7).

Шаг 3. Получение шифртекста путем расстановки символов в соответствии с маршрутами.

Ti = <ОП_ТМЕЫДЕСРЕТАОНИ*КВ****>.

Шаг 4. Разбиение на блоки шифртекста

Т1=<ОП_Т МЕЫД ЕСРЕ ТАОН И*КВ ****>.

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



Рис. 3.8. Схема перестановок


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

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


3.3. Задание¹.


Создать программы, осуществляющие шифрование и дешифрование текстовой строки согласно варианту с помощью выбранных методов шифрования (табл. 3.2)²:

• методом моноалфавитной замены: описать последовательность шагов, составить таблицу замен;
  
• методом полиалфавитной замены: описать последовательность, составить матрицу шифрования для своего ключа (табл. 3.2);
  
• методом перестановки: описать последовательность действий с выбранными параметрами согласно варианту (рис. 3.9).
  

3.4. Требования к оформлению отчета


Отчет должен быть выполнен в соответствии с требованиями ЕСКД.

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


Таблица 3.2

Варианты заданий

№ вар.	Коэффициенты для метода простой замены	Ключ для метода полиалфавитной замены	Маршруты Гамильтона
Ключ	Длина зашифрованных блоков
1	b=4 R=65	k1=1; k2=3	АТОМ	К=[1,2,3]	8
2	k1=1; k2=5	БАНК	К=[2,3,4]
3	k1=1; k2=5	БРЕД	К=[3,4,5]
4	k1=1; k2=7	ЯХТА	К=[4,5,6]
5	k1=1; k2=7	КЛЮЧ	К=[5,6,1]
6	k1=1; k2=11	КЛАД	К=[6,2,3]
7	k1=1; k2=13	КЛИН	К=[1,3,5]
8	k1=1; k2=7	СОРТ	К=[2,4,6]
9	k1=1; k2=13	ЛОЖЬ	К=[3,4,1]
10	k1=1; k2=15	ОБЕД	К=[4,2,5]
11	k1=1; k2=3	ПЛЯЖ	К=[5,2,3]
12	k1=1; k2=11	ЧУШЬ	К=[2,6,3]
13	k1=1; k2=15	СНЕГ	К=[6,3,2]
14	k1=1; k2=3	ЗАЛП	К=[5,1,2]
15	k1=1; k2=5	БРАК	К=[1,5,4]
16	k1=1; k2=13	ВИЗА	К=[2,3,5]
17	k1=1; k2=11	ВОДА	К=[3,4,6]
18	k1=1; k2=3	ВИНТ	К=[4,5,2]
Алфавит: R=[абвгдежзийклмнопрстуфхцчшщъыьэюяАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_].

Маршрут 1	Маршрут 2	Маршрут 3
Маршрут 4	Маршрут 5	Маршрут 6

Рис. 3.9. Маршруты Гамильтона для выполнения задания

Контрольные вопросы.

1. Что такое криптографическое преобразование информации?
   
2. На какие группы классифицируются методы криптографии?
   
3. Что такое метод шифрования?
   
4. Что такое криптоанализ?
   
5. В чем состоит смысл симметричной криптографии?
   
6. Какие основные этапы зашифрования информации методом простой замены?
   
7. Что такое полиалфавитная замена?
   
8. Какие основные этапы построения матрицы Вижинера?
   
9. Чем обосновывается криптостойкость описанных в лабораторной работе методов?
   
10. Каковы основные требования, предъявляемые к симметричным криптоалгоритмам?
    
11. В чем отличие методов перестановки от подстановки?