Материал: metod_cripto_n

Следствие 2. Если A_i и B_i – произвольные векторы, причем A_i не связаны сдвигом, то существуют булевы функции F, преобразующие каждый вектор A_i в соответствующий ему вектор B_i.

Пример 2. Пусть требуется найти функцию F, преобразующую векторы

A₁ = 1011 в вектор B₁ = 0110,

A₂ = 0111 в вектор B₂ = 1001,

A₃ = 0101 в вектор B₃ = 1110.

Построим часть таблицы истинности функции 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	0
0 1 1 1	1
0 1 1 1	0
0 1 1 1	0
0 1 1 1	1
0 1 0 1	1
0 1 0 1	1
0 1 0 1	1
0 1 0 1	0

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

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

Пример 3. Пусть требуется найти булеву функцию F, обеспечивающую следующие преобразования: A₁  A₂  A₃  A₄  A₅  A₆  A₁, где A₁ = 1011, A₂ = 0110, A₃ = 0111, A₄ = 1001, A₅= 0101, A₆ = 1111.

Упражнение. Используя описанную выше методику, выпишите часть таблицы истинности, постройте диаграмму Вейча и найдите один из вариантов решения (в диаграмме Вейча в пустых клетках должны стоять прочерки, т.е. на этих наборах функция не определена). Диаграмма Вейча этой функции будет иметь вид:

Одно из возможных решений: F = a c e  e g  a b  ac  c d  c d e  b c  e f g. (знак «» означает унарную операцию отрицания).

Представляет интерес определить количество наборов длины n не связанных сдвигом и их долю в общем числе двоичных наборов длины n. Расчет произведем для наборов длины n веса q (т.е. содержащих ровно q единиц). Для этого заметим, что если в младшем (например, левом) разряде поставить 1, а остальные q-1 единиц на оставшихся n- 1 позициях расставить так, чтобы получить разные двоичные коды, то мы получим все наборы, не связанные сдвигом, содержащие ровно q единиц. Тогда число таких наборов будет равно . Поскольку общее число наборов длины n веса q равно , то доля наборов не связанных сдвигом составляет q/n. Так, например, при n = 20, q = 10 S(20,10) = 92378.

3.Минимизация слабо определенных булевых функций

Возьмем теперь произвольный вектор A (1 0 0 1 1 1 0 1 0 0 0 1) и некоторую функцию F = a_i  a_i-3  a_i+2  a_i+5. Применив преобразование F к вектору A, получим вектор:

B (1 1 0 1 0 1 1 1 0 1 0 0). Чтобы найти функцию, которая по вектору B позволила бы восстановить вектор A, можно построить таблицу истинности частично определенной функции 23 аргументов вида:

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

Обратная к F функция, которая восстанавливает вектор A по вектору B, определена всего на 12 наборах аргументов, а на N= 2²³ – 12 наборах не определена. Следовательно, ее можно доопределить 2^N способами. Это число настолько велико, что задачу однозначного нахождения обратной к F функции можно считать нереальной.

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

Упражнение. Докажите еще одно (четвертое) следствие из приведенной теоремы:

Пусть имеются А_i (i = 1,2,…,k₁), B_j (j = 1,2,…,k₂), C_s(s = 1,2,…,k₃)… и произвольные векторы Y₁,Y₂,Y₃…Тогда существует булева функция F, такая, что F(Ai) = Y₁, F(B_j) = Y₂, F(C_s) = Y_3.