Лабораторная работа 9. КП_ЛР1_КозловаВИ.docx. Булевы преобразования двоичных последовательностей
 Скачать 477.63 Kb.
|
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра ИС ОТЧЕТ по лабораторной работе по дисциплине Конструирование программ» Тема: БУЛЕВЫ ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ» Студент(ка) гр. 0372 Козлова В.И. Преподаватель Копыльцов А.В. Санкт-Петербург 2022 Цель работы. ознакомиться с методами преобразования двоичных последовательностей булевыми функциями и использованием этих преобразований для решения некоторых задач защиты информации в компьютерных сетях. Основные теоретические положения. Теорема: Для того, чтобы существовали булевы функции F, преобразующие произвольную последовательность А в произвольную последовательность В необходимо и достаточно, чтобы А была бы ненулевой последовательностью. Число аргументов F не превышает 2n –1. Необходимость следует из того, что при нулевой последовательности А все элементы последовательности В будут либо нулями, либо единицами ив этом случае Вне может быть произвольной последовательностью Определение. Два набора и длины n будем называть связанными сдвигом, 𝐴 𝑖 𝐴 𝑗 если при некотором сдвиге одного набора относительно другого у этих наборов совпадают позиции всех единиц. Например, A = 1 0 0 1 0 1 1 0 0 0 и B = 0 0 1 0 0 1 0 1 1 0 – наборы, связанные сдвигом. Из приведенной выше теоремы сформулируем следствия. Следствие 1. Если, i = 1,2,3,…,k – двоичные векторы несвязанные сдвигом 𝐴 𝑖 и В – произвольный вектор, то существуют булевы функции F, преобразующие любой вектор в вектор В, те. B = F( ), i = Следствие 2. Если и произвольные векторы, причем не связаны 𝐴 𝑖 𝐵 𝑖 𝐴 𝑖 сдвигом, то существуют булевы функции F, преобразующие каждый вектор в 𝐴 𝑖 соответствующий ему вектор 𝐵 𝑖 Следствие 3. Если, i = 1,2,3,…,k – произвольные двоичные векторы, несвязанные сдвигом, то существуют булевы функции F, преобразующие в 𝐴 1 любой вектор , те ), = F( ), …, = F ( ) и F( Количество наборов длины n несвязанных сдвигом и их долю в общем числе двоичных наборов длины n. Расчет произведем для наборов длины n веса q (т.е. содержащих ровно q единиц. Число таких наборов будет равно. Поскольку общее число наборов длины, 𝑞) = 𝑃(𝑛 − 𝑞, 𝑞 − 1) = 𝐶 𝑛−1 𝑞−1 n веса q равно, то доля наборов несвязанных сдвигом составляет q/n. 𝐶 𝑛 𝑞 3 Экспериментальные результаты. Прочитали теоретический материал. Взяли любую ненулевую последовательность А, задались некоторой функцией F, получили вручную последовательность В и проверили результат с использованием программы на компьютере. Взяли ненулевую последовательность A = Задали некоторую функцию F = !a[i-2] # a[i] + Получили вручную последовательность В b[0] = !a[0-2] # a[0] + a[0-1] = !a[-2] # a[0] + a[-1] = !0 # 1 + 0 = 1 # 1 + 0 = 0 b[1] = !a[1-2] # a[1] + a[1-1] = !a[-1] # a[1] + a[0] = !0 # 1 + 1 = 1 # 1 + 1 = 1 b[2] = !a[2-2] # a[2] + a[2-1] = !a[0] # a[2] + a[1] = !1 # 0 + 1 = 0 # 0 + 1 = 1 b[3] = !a[3-2] # a[3] + a[3-1] = !a[1] # a[3] + a[2] = !1 # 0 + 0 = 0 # 0 + 0 = 0 b[4] = !a[4-2] # a[4] + a[4-1] = !a[2] # a[4] + a[3] = !0 # 1 + 0 = 1 # 1 + 0 = 0 B = Проверили результат с использованием программы на компьютере: Последовательность B, полученная вручную, совпадала с последовательностью, полученной с использованием программы. Вывод к пункту 2: научились получать последовательность B, имея ненулевую последовательность A и некоторую функцию F. 4 3. Взяли две пятиразрядные двоичные последовательности и и 𝐴 1 𝐴 2 некоторую также пятиразрядную последовательность В. Нашли функцию которая из любой последовательности и строит одну 𝐴 1 𝐴 2 последовательность В. Проверили результат. Пусть 10110, = 11000 и B = 𝐴 1 𝐴 2 11010. Составили таблицу истинности для и b c d e f g h i B 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 По полученным значениям построили диаграмму Вейча и доопределили е Получили: Проверили результат с использованием компьютера: Для Для 6 Вывод к пункту 3: научились находить функцию, которая из двух различных последовательностей и строит одну последовательность В с помощью А 1 А 2 диаграммы Вейча. 4. Взяли любую ненулевую четырехразрядную последовательность Аи задались некоторой функцией F. На компьютере нашли последовательность В = F(A). Используя методику, изложенную в теоретическом разделе, вручную нашли функцию F’, которая из В восстанавливает А, те. A = F’(B). Проверили результат на компьютере. Взяли ненулевую четырехразрядную последовательность Аи задались функцией F = a[i-1] + !a[i] На компьютере нашли последовательность В = Используя методику, изложенную в теоретическом разделе, вручную нашли функцию F’, которая из В восстанавливает А, те. A = F(B). Построили таблицу истинности b c d e f g A 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 7 По полученным значениям построили диаграмму Вейча и доопределили её: Получили обратную функцию F’ = a[i-1]*a[i+1] + !a[i]. Проверили результат на компьютере: В результате получили функцию F’, обратную кто есть A = Вывод к пункту 4: научились находить функцию F’, обратную к заданной, которая восстанавливает заданную последовательность А из последовательности B, полученной с помощью заданной функции F. 5. Подсчитали количество, а затем выписали все ненулевые несвязанные сдвигом последовательности длины 4. Выбрали произвольно три из них, например, , , . Нашли функцию F, которая из последовательности 𝐴 1 𝐴 2 𝐴 3 𝐴 1 строит последовательность, из строит, а из опять, те F( 𝐴 2 𝐴 2 𝐴 3 𝐴 3 𝐴 1 𝐴 2 𝐴 1 ), = F( ), = F( ). Проверили результат на компьютере 8 Все последовательности, содержащие один ноль или единицу, связаны сдвигом. Поэтому выписываем по одной последовательности с одной и тремя единицами 1000 и 1110. Последовательность стремя единицами существует только одна 1111. Остаются последовательности с двумя единицами. Последовательности с одинаковыми расстояниями между ближайшими единицами связаны сдвигом, при этом возможных минимальных расстояний может быть только два ноль (1100) и один (1010). Итого пять последовательностей 1010 𝐴 2 = 1110 𝐴 3 = 1111 𝐴 4 = 1100 𝐴 5 = Выбрали произвольно три из них, например 1010 𝐴 3 = 1111 𝐴 4 = Нашли функцию F, которая из последовательности строит 𝐴 1 последовательность , из строит, а из опять. F = a[i-1] XOR a[i] + 𝐴 3 𝐴 3 𝐴 5 𝐴 5 𝐴 1 a[i + Проверили результат на компьютере: Из получим 9 Из получим : 𝐴 3 А 4 Из опять получим : А 4 𝐴 1 По полученным значениям построили диаграмму Вейча и доопределили её: Получили функцию F = a[i-1] XOR a[i] + a[i + 2] 10 Вывод к пункту 5: научились находить функцию F, которая из последовательности строит последовательность, из строит, а из А 3 А 2 А 3 А 3 опять , те F( ), = F( ), = F( ). А 3 А 3 А 3 А 3 А 3 А 3 А 3 А 3 6. Предложим 3 варианта использования Теоремы и ее следствий (приведенных в теоретической части) для защиты информации в компьютерных сетях. ● булевы функции могут использоваться для многократного генерирования одноразовых ключей булевы функции могут использоваться для проверки паролей – это основано на сложности нахождения обратной булевой функции; ● булевы функции могут использоваться для идентификации отправителей сообщений (это основано на втором следствии из теоремы). Вывод к пункту 6: рассмотрели варианты использования теоремы и ее следствий для защиты информации в компьютерных сетях. Вывод: входе лабораторной работы ознакомились с методами преобразования двоичных последовательностей булевыми функциями и использованием этих преобразований для решения некоторых задач защиты информации в компьютерных сетях |