1. А и В знают булеву функцию F. А передает В некоторую последовательность А1 и оба вырабатывают общий ключ F(A1) = A2 = K1, после однократного применения которого ключ уничтожается. Затем с помощью этой же функции А и В вырабатывают новый ключ K2 = F(A2) и т.д. Последовательность А1 может быть стандартной, например, 101010101010101… и вообще не передаваться по открытому каналу. (Следствие 3 теоремы.)
2. Булевы преобразования могут использоваться для проверки пароля. Так, если А отправляет В запрос А1, а В отвечает на него В1 = F(A1), то активный перехватчик даже зная А1 и В1 не может однозначно восстановить функцию F, поэтому маскируясь под «своего» на запрос А2 ответит результатом преобразования другой функцией F’ (A2) F(A2). Каждый клиент банка снабжен несколькими паролями. Подписывая свое сообщение любым из них, клиент может быть уверен, что банк определит - от кого пришло сообщение. (Следствие 2 теоремы).
3. Все клиенты банка разбиваются на группы, клиенты каждой группы получают свои различные пароли. Банк может определить принадлежность клиента к группе. (Следствие 2 теоремы).
Представляется важным найти класс нетривиальных функций F, при которых уравнение F(X) = B разрешимо относительно вектора X(x1,x2,…,xn) при любых значениях элементов вектора В (b1,b2,…,bn). Снабдив такой функцией F официального получателя сообщений, можно по исходному тексту B1,B2,B3… вычислять криптотекст x1,x2,x3…, который и передавать по открытому каналу. Официальный получатель, используя функцию F, восстановит исходное сообщение, так как B1= F(X1), B2= F(X2), B3 = F(X3)…
В качестве примера такой функции для шести разрядных произвольных векторов В (b1,b2,…,b6) можно взять функцию F = ai-2ai+4ai-4ai+3. Значения элементов вектора X для этой функции определятся следующим образом:
x1 = b1b2b3b4b6
x2 = b4
x3 = b1b2b3b4b5b6
x4 = b4b6
x5 = b1b4b6
x6 = b1b2b4b6
Для 10 разрядных векторов можно взять функцию F = aiai-6ai+5. В этом случае элементы вектора X будут вычисляться следующим образом:
x1 = b1b6,
x2 = b1b2b6b7,
x3 = b1b2b3b6b7b8,
x4 = b1b2b3b4b6b7b8b9,
x5 = b1b2b3b4b5b6b7b8b9b10,
x6 = b61,
x7 = b1b6b71,
x8 = b1b2b6b7b81,
x9 = b1b2b3b6b7b8b9b101,
x10 = b1b2b3b4b6b7b8b9b101.
Если исходный текст состоит из последовательности векторов Bi, например,
Если N представлено в канонической форме (1), то количество делителей числа N, обозначим его D(N), вычисляется следующим образом:
D(N) = (n1+1)(n2+1)…(nk+1).
Так, для числа 560 количество делителей D(560) = (4+1)(1+1)(1+1) = 20. Если N = P – простое число, то количество его делителей равно 2 (1 и само число P).
Пусть два числа N1 и N2 представлены в канонической форме:
N1 = p1 n1p2 n2…pk nk
N2 = p1 s1p2 s2…pk sk
Тогда НОК (N1,N2) = p1 max(n1,s1) p2 max(n2,s2) … pk max(nk,sk), а
НОД (N1,N2) = p1 min(n1,s1) p2 min(n2,s2) … pk min(nk,sk).
Примеры 1. Найти НОК и НОД следующих пар чисел:
a) 575 и 155
b) 840 и 188650
c) 4851 и 29106
d) 975 и 616
Если в каноническом представлении одного из чисел отсутствует какой-либо простой сомножитель, его можно ввести в нулевой степени. Например, для чисел N1 = 235271 и N2 = 3151112 прежде чем находить НОК и НОД требуется их привести к одинаковой форме, т.е. сделать так, чтобы в каноническом представлении обоих чисел присутствовали бы одинаковые простые числа в соответствующих степенях, а именно:
N1 = 23305271110;
N2 = 20315170112.
Тогда НОК (N1,N2) = 23315271112 = 508200,
НОД (N1,N2) = 20305170110 = 5.
Примеры 2 . Найти НОК и НОД следующих пар чисел:
a) N1 = 440 ; N2 = 6050
b) N1 = 234 ; N2 = 4125
c) N1 = 66550 ; N2 = 40131
d) N1 =388 ; N2 = 1647
Приведенный алгоритм легко обобщается на произвольное количество чисел, для которых требуется определить НОК и НОД.
Примеры 3. Найти НОК и НОД для следующих наборов чисел:
a) N1 = 60 ; N2 = 350 ; N3 = 495;
b) N1 =265 ; N2 = 104 ; N3 = 93.
c) N1 = 2100 ; N2 =630 ; N3 = 5880; N4 = 9450;
d) N1 = 700 ; N2 = 495 ; N3 = 104; N1 = 103 ; N2 = 260 ; N3 = 121.
Если P-1 представляется в виде произведения простых чисел в первых степенях, т.е. P-1 = p1p2p3…ps., то P-1 называется евклидовым числом. Например, P=23. P-1 = 22 = 21111
Пример. Проверьте, какие из приведенных простых чисел при вычитании 1 являются евклидовыми: 11,29,31,43,53,59,71.
Запустите программу проверки числа. Эта программа позволяет выделить наименьший простой сомножитель из любого числа. Так, если Вы ввели число N, то программа представит его в виде N =p*q’, где p – наименьший простой сомножитель числа N. Например, Вы ввели число 21571. Программа представит его в виде: 11*1961. Если теперь ввести число 1961, то программа это число представит в виде: 37*53. Таким образом, каноническое представление числа 21571 = 11*37*53. Ознакомьтесь с работой программы и выполните все примеры, приведенные в теоретической части.
Найдите 3 трехразрядных евклидовых числа. Для этого возьмите несколько простых чисел, вычтите из каждого 1 и представьте в канонической форме. Если P-1 будет иметь вид: P-1 = p1p2p3…ps., то P-1 – евклидово число.
Оформите отчет. Отчет должен содержать:
Прочитайте теоретический материал и выполните все упражнения.
Возьмите любую ненулевую последовательность А, задайтесь некоторой функцией F, получите вручную последовательность В и проверьте результат с использованием программы на компьютере.
Возьмите две пятиразрядные двоичные последовательности А1 и А2 и некоторую также пятиразрядную последовательность В. Найдите функцию F, которая из любой последовательности А1 и А2 строит одну последовательность В. Проверьте результат с использованием компьютера.
Возьмите любую ненулевую четырехразрядную последовательность А и задайтесь некоторой функцией F. На компьютере найдите последовательность В = F(A). Используя методику, изложенную в теоретическом разделе, вручную найдите функцию F’, которая из В восстанавливает А, т.е. A = F(B). Проверьте результат на компьютере.
Подсчитайте количество, а затем выпишите все ненулевые не связанные сдвигом последовательности длины 4. Выберите произвольно три из них, например, A1,A2,A3. Найдите функцию F, которая из последовательности A1 строит последовательность A2, из A2 строит A3, а из A3 опять A1, т.е. A2 = F(A1), A3 = F(A2), A1 = F(A3). Проверьте результат на компьютере.
Предложите 3 варианта использования Теоремы и ее следствий (приведенных в теоретической части) для защиты информации в компьютерных сетях.
Оформите отчет. Отчет должен содержать:
a) Титульный лист с указанием университета, кафедры, дисциплины, названия лабораторной работы, № группы, фамилии студента и преподавателя.
b) Все решения, выполненные вручную.
с) Комментарии при проверке решений на компьютере.
d) Описание задач защиты информации, в которых возможно использование булевых преобразований двоичных последовательностей.
Цель работы: Ознакомить студентов с канонической формой представления чисел, нахождением количества делителей произвольного числа, нахождением наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) нескольких чисел, нахождением евклидовых чисел.
Любое целое положительное число N может быть представлено в так называемой канонической форме, т.е. в виде произведения некоторых простых чисел в соответствующих степенях, а именно:
N = p1 n1p2 n2…pk nk, (1)
где p1,p2,…,pk – простые числа, n1,n2,…,nk – целые положительные числа.
Простым числом p называется целое, которое не имеет никаких делителей кроме 1 и самого себя. Начальный ряд простых чисел (кроме 1, которое условно также принимается за простое число): 2,3,5,7,11,13, 17,19,23,29,31,37, 41,43…
Для перевода числа N в каноническую форму можно воспользоваться следующим алгоритмом. Число N делится на наименьшее простое число 2 до тех пор, пока возможно деление без остатка. Затем делится на следующее простое число 3 и т.д. После чего выписывается (1).
Пример. N = 560; 560 : 2 = 280; 280 : 2 = 140; 140 : 2 = 70; 70 : 2 = 35. Число 35 на 2 нацело не делится. На 3 также не делится. Делим на 5; 35 : 5 = 7. Число 7 простое, следовательно, каноническая форма числа 560 = 245171.
B1 = 1011100011; B2 = 1111111111; B3 = 0111100011; B4 = 0000000000; B5 = 1011011100;
B6 = 0110001011 ; тогда отправитель сообщений может вычислить соответствующие векторы Xi криптотекста и передать их по открытому каналу: X1 = 1100010000; X2 = 0000000000;
X3 = 0100011000; X4 = 0000011111; X5 = 0110000101 ; X6 = 0010110110.
Получатель сообщения с помощью функции F = aiai-6ai+5 преобразует векторы Xi в векторы открытого текста Bi.
Нелегальный перехватчик сообщения, даже зная пары Bi и Xi, не сможет восстановить функцию F.
Ерош И.Л., Игнатьев М.Б., Москалев Э.С. Адаптивные системы управления промышленными роботами. Учебное пособие для втузов. Л.1985, 144 с.
Кузнецов О.П., Адельсон – Вельский Г.М. Дискретная математика для инженера. Москва, Энергоатомиздат, 1988, 480 с.
a) Титульный лист с указанием университета, кафедры, дисциплины, названия лабораторной работы, № группы, фамилии студента и преподавателя.
b) Описание всех вычислений.
c) Выводы по всем пунктам.