Добавлен: 19.03.2024
Просмотров: 7
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)
Кафедра ИС
ОТЧЕТ
по лабораторной работе по дисциплине Конструирование программ»
Тема: БУЛЕВЫ ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ»
Студент(ка) гр. 0372
Козлова В.И.
Преподаватель
Копыльцов А.В.
Санкт-Петербург
2022
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)
Кафедра ИС
ОТЧЕТ
по лабораторной работе по дисциплине Конструирование программ»
Тема: БУЛЕВЫ ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ»
Студент(ка) гр. 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 несвязанных сдвигом и их долю в общем числе
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
ознакомиться с методами преобразования двоичных последовательностей булевыми функциями и использованием этих преобразований для решения некоторых задач защиты информации в компьютерных сетях.
Основные теоретические положения.
Теорема: Для того, чтобы существовали булевы функции 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
содержащих ровно 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
Взяли ненулевую последовательность 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
строит одну последовательность В с помощью
А
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
Получили обратную функцию 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
Последовательности с одинаковыми расстояниями между ближайшими единицами связаны сдвигом, при этом возможных минимальных расстояний может быть только два ноль (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
:
????
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: рассмотрели варианты использования теоремы и ее следствий для защиты информации в компьютерных сетях.
Вывод: входе лабораторной работы ознакомились с методами преобразования двоичных последовательностей булевыми функциями и использованием этих преобразований для решения некоторых задач защиты информации в компьютерных сетях
А
3
А
2
А
3
А
3
опять
, те F( ),
= F( ),
= F( ).
А
3
А
3
А
3
А
3
А
3
А
3
А
3
А
3 6. Предложим 3 варианта использования Теоремы и ее следствий
(приведенных в теоретической части) для защиты информации в компьютерных сетях.
●
булевы функции могут использоваться для многократного генерирования одноразовых ключей булевы функции могут использоваться для проверки паролей – это основано на сложности нахождения обратной булевой функции;
●
булевы функции могут использоваться для идентификации отправителей сообщений (это основано на втором следствии из теоремы).
Вывод к пункту 6: рассмотрели варианты использования теоремы и ее следствий для защиты информации в компьютерных сетях.
Вывод: входе лабораторной работы ознакомились с методами преобразования двоичных последовательностей булевыми функциями и использованием этих преобразований для решения некоторых задач защиты информации в компьютерных сетях
