Материал: metod_cripto_n

21

Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ

УНИВЕРСИТЕТ им. А.И. ГЕРЦЕНА

Факультет математики

Кафедра информатики

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

к выполнению лабораторных работ по дисциплине

Защита информации в компьютерных сетях

ОСНОВНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА

направление 050200 физико-математическое образование

Квалификация выпускника: Магистр физико-математического образования

Пояснительная записка

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

Работа №1 знакомит студентов с использованием булевых преобразований в криптографии. Для изучения работы целесообразно познакомиться с учебным пособием [1] Студент должен овладеть методами минимизации булевых выражений и уметь находить булевы функции, связывающие несколько последовательностей одинаковой длины.

Работа №2 является вспомогательной при изучении важного раздела дисциплины “Теории чисел”, так как в современных криптографических системах именно этот раздел дискретной математики используется очень широко. Для успешного выполнения работы можно ознакомиться с учебным пособием [3].

Работа №3 знакомит студентов с методами разделения секрета. Оригинальный подход к решению этой криптографической задачи изложен в пособии [2].

Работа №4 знакомит студентов с классической системой с открытым распределением ключей – системой RSA и некоторыми вариантами ее использования. Описание этой системы также имеется в учебном пособии [2].

Кроме того, полезными для изучения различных вопросов оценки криптостойкости различных систем являются пособия [4,5]

Литература для подготовки к выполнению лабораторных работ.

1. Ерош И.Л. Дискретная математика. Булева алгебра, комбинационные схемы. Преобразование двоичных последовательностей. Учебное пособие СПбГУАП.2001г.

2. Ерош И.Л. Дискретная математика. Математические вопросы криптографии. Учебное пособие СПбГУАП.2001г.

3. Ерош И.Л. Дискретная математика. Теория чисел. Учебное пособие СПбГУАП.2001г.

4. Ерош И.Л. Дискретная математика. Комбинаторика. Учебное пособие СПбГУАП.2001г.

5. Ерош И.Л. Элементы теории дискретных групп. Учебное пособие СПбГУАП. 1998г.

Содержание

1. Булевы преобразования двоичных последовательностей ............................................….3

2. Элементы теории чисел ………….................................................................................…...9

3. Исследование схем разделения секрета ............................................................................11

4. Исследование криптографической системы RSA ............................................................17

Лабораторная работа №1 Булевы преобразования двоичных последовательностей

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

Теоретические пояснения

1.Постановка задачи

Пусть имеются две двоичные последовательности A(a₁,a₂,…,a_n) и B(b₁,b₂,…,b_n), При этом a_i,b_i  {0,1}, i = 1,2,3,…,n. Элементы последовательности B будем получать булевым преобразованием последовательности A, при этом b_i будет результатом булевого преобразования, зависящего от a_i и некоторых элементов из окружения a_i. Максимальное число аргументов булевой функции F равно N= 2n-1. Так для n = 3 , N = 5, для n = 4, N = 7, для n = 5, N = 9. Здесь и далее a_i = 0 при 0> i >n-1.

2.Теорема о преобразованиях двоичных последовательностей.

Сформулируем теорему, на основании которой можно строить булевы функции, преобразующие одну последовательность в другую. Эта теорема является аналогом теоремы, доказанной в [1].

Теорема: Для того, чтобы существовали булевы функции F, преобразующие произвольную последовательность А в произвольную последовательность В необходимо и достаточно, чтобы А была бы ненулевой последовательностью. Число аргументов F не превышает 2n –1.

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

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

a1 a2 … an	b1
a1 a2 … an	b2
a1 a2 … an	b3
………………...................	....
a1 a2 … an+1	bn

Если хотя бы один элемент последовательности А не равен 0, то все наборы, на которых функция определена будут различными, поэтому не существует ни одной одинаковой пары наборов, на которой функция должна принимать одновременно значение 0 и 1.

Пример. Пусть A (101), B(011). Функции F будут зависеть от аргументов F(a_i-2,a_i-1,a_i,a_i+1,a_i+2). Таблица истинности этих функций (точнее только та ее часть, на которой функции определены) будет иметь вид:

Функции пяти аргументов задается на 32 наборах. Однако эта функция задана в примере всего на трех наборах. На остальных 29 наборах функция неопределена и ее можно доопределить 2²⁹ способами. Диаграмма Вейча этой функции будет иметь вид:

-----------------------------------					ai-2
		-----------------------------------					ai-1
	----------------				----------------			ai
--	--	--	--	--	--	0	--		| |
--	--	--	--	--	--	--	--	| |
--	--	--	--	1	--	--	--		ai+2
--	1	--	--	--	--	--	--	ai+1

Доопределить и минимизировать данную функцию достаточно просто: . Действительно, применив булево преобразование F к A, получим B. При длинах векторов A и B равных n, булева функция будет задаваться на n наборах, а на 2^(2n-1) – n наборах функция будет не определена. Доопределение и минимизация булевой функции не однозначны.

Определение. Два набора A_i и A_j длины n будем называть связанными сдвигом, если при некотором сдвиге одного набора относительно другого у этих наборов совпадают позиции всех единиц. Например, A = 1 0 0 1 0 1 1 0 0 0 и B = 0 0 1 0 0 1 0 1 1 0 – наборы, связанные сдвигом. Из приведенной выше теоремы сформулируем следствия.

Следствие 1. Если A_i, i = 1,2,3,…,k – двоичные векторы не связанные сдвигом и В – произвольный вектор, то существуют булевы функции F, преобразующие любой вектор A_i в вектор В, т.е. B = F(A_i), i = 1,2,3,…,k.

Пример 1. Пусть A₁ = 1011; A₂ = 1001; A₃ = 0110; B = 0111. Построим часть таблицы истинности функции F, выписывая только те наборы, на которых функция определена.

a b c d e g h	F
1 0 1 1	0
1 0 1 1	1
1 0 1 1	1
1 0 1 1	1
1 0 0 1	0
1 0 0 1	1
1 0 0 1	1
1 0 0 1	1
0 1 1 0	0
0 1 1 0	1
0 1 1 0	1
0 1 1 0	1

Упражнение. Постройте диаграмму Вейча функции F, и убедитесь в том, что при некотором способе доопределения функция будет иметь вид: .

Проверьте, что эта функция из любой приведенной последовательности A_i (i = 1,2,3) строит одну и ту же последовательность В.