№1 БУЛЕВЫ ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

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

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра ИС

отчет

по лабораторной работе №1

по дисциплине «Конструирование программ»

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

Студент гр. 0375		Яблоков В.А.
Преподаватель		Копыльцов А. В.

Санкт-Петербург

2022

Цель работы:

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

Ход работы:

1. A₁ = 101101, F = a[i + 2] ˄ a[i] ˅ !a[i + 1]. Найдем последовательность B:

b[1] = a[3] ˄ a[1] ˅ !a[2] = 1 ˄ 1 ˅ 1 = 1.

b[2] = a[4] ˄ a[2] ˅ !a[3] = 1 ˄ 0 ˅ 0 = 0.

b[3] = a[5] ˄ a[3] ˅ !a[4] = 0 ˄ 1 ˅ 0 = 0.

b[4] = a[6] ˄ a[4] ˅ !a[5] = 1 ˄ 1 ˅ 1 = 1.

b[5] = a[7] ˄ a[5] ˅ !a[6] = 0 ˅ 0 = 0.

b[6] = a[8] ˄ a[6] ˅ !a[7] = 1 = 1.

Таким образом, B = 100101. Проверка на компьютере:

Получена та же самая последовательность.

2. A₁ = 10001, A₂ = 11001, B = 01000.

F = a[i - 2] ˄ a[i] XOR a[i + 3].

Проверка на компьютере:

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

3. A = 1001, F = a[i - 2]  a[i] ˄ a[i + 2], B = 1011. Построим таблицу истинности частично определенной функции, доопределив ее нулями на пустых клетках:

a[i - 3]	a[i - 2]	a[i - 1]	a[i]	a[i + 1]	a[i + 2]	a[i + 3]	A
0	0	0	1	0	1	1	1
0	0	1	0	1	1	0	0
0	1	0	1	1	0	0	0
1	0	1	1	0	0	0	1

Выберем из таблицы первый, третий, пятый и шестой столбцы, получим:

a[i - 3]	a[i - 1]	a[i + 1]	a[i + 2]	A
0	0	0	1	1
0	1	1	1	0
0	0	1	0	0
1	1	0	0	1

Получим функцию: F* = !a[i - 3] * !a[i - 1] * !a[i + 1] * a[i + 2] + a[i - 3] * a[i - 1] * !a[i + 1] * !a[i + 2]. Проверка на компьютере:

Получена исходная последовательность B, значит, F* найдена правильно.

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

1. А и В знают булеву функцию F. А передает В некоторую последовательность А₁ и оба вырабатывают общий ключ F(A₁) = A₂ = K₁, после однократного применения которого ключ уничтожается. Затем с помощью этой же функции А и В вырабатывают новый ключ K₂ = F(A₂) и т.д. Последовательность А₁ может быть стандартной, например, 101010101010101… и вообще не передаваться по открытому каналу. (Следствие 3 теоремы.)

2. Булевы преобразования могут использоваться для проверки пароля. Так, если А отправляет В запрос А₁, а В отвечает на него В₁ = F(A₁), то активный перехватчик даже зная А₁ и В₁ не может однозначно восстановить функцию F, поэтому маскируясь под «своего» на запрос А₂ ответит результатом преобразования другой функцией F’ (A₂)  F(A₂). Каждый клиент банка снабжен несколькими паролями. Подписывая свое сообщение любым из них, клиент может быть уверен, что банк определит - от кого пришло сообщение. (Следствие 2 теоремы).

3. Все клиенты банка разбиваются на группы, клиенты каждой группы получают свои различные пароли. Банк может определить принадлежность клиента к группе. (Следствие 2 теоремы).

Выводы:

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