<< Предыдущая

стр. 4
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

другого у этих наборов совпадают позиции всех единиц. Например, A =
1 0 0 1 0 1 1 0 0 0 и B = 0 0 1 0 0 1 0 1 1 0 – наборы, связанные сдвигом.
Из приведенной выше теоремы сформулируем следствия.
Следствие 1. Если Ai, i = 1, 2, 3, …, k – двоичные векторы, не свя-
занные сдвигом, и В – произвольный вектор, то существует одна булева
функция F, преобразующая любой вектор Ai в вектор В, т. е. B = F(Ai),
i = 1, 2, 3, …, k.
П р и м е р 1. Пусть A1 = 1011; A2 = 1001; A3 = 0110; B = 0111.
Построим часть таблицы истинности функ-
Пример 1 ции F, выписывая только те наборы, на кото-
рых функция определена, при этом для удоб-
a b cd e g hF
ства введем очевидные переобозначения
10110
аргументов.
1011 1 Упражнение. Постройте диаграмму Вей-
ча функции F и убедитесь в том, что при не-
1011 1
котором способе доопределения функция
1011 1
будет иметь вид
10010
F=a?c?e g.
1001 1
Проверьте, что эта функция из любой при-
1001 1
веденной последовательности Ai (i = 1, 2, 3)
1001 1
строит одну и ту же последовательность В.
01 100 Следствие 2. Если Ai и Bi – произволь-
ные векторы, причем Ai не связаны сдвигом,
011 0 1
то существует одна булева функция F, пре-
0110 1
образующая каждый вектор Ai в соответ-
0110 1
ствующий ему вектор Bi.
Пример 2. Пусть требуется найти одну функцию F, преобразую-
щую векторы:
A1 = 1011 в вектор B1 = 0110,
A2 = 0111 в вектор B2 = 1001,
A3 = 0101 в вектор B3 = 1110.

22
Пример 2
Построим часть таблицы истинности фун-
кции F, выписывая только те наборы, на ко-
a b cd eghF
торых функция определена.
Упражнение. Постройте диаграмму Вей- 10110
ча функции F и убедитесь в том, что при не- 1011 1
котором способе доопределения функция
1011 1
будет иметь вид
1011 0
F = d ? e g h ? bc ? be .
01111
В частном случае следствия 2 некоторые
0111 0
значения Bi могут совпадать с соответству-
0111 0
ющими им Ai.
0111 1
П р и м е р 3. Пусть требуется найти
функцию F, преобразующую векторы: 01011
A1 = 1011 в вектор B1 = 1011, 0101 1
A2 = 0110 в вектор B2 = 1101,
0101 1
A3 = 1001 в вектор B3 = 1001.
Здесь векторы B1 = A1, B3 = A3, B2 ?A2. 0101 0
Построим часть таблицы истинности фун-
кции F.
Пример 3
Упражнение. Проверьте, что при неко-
тором способе доопределения a b cd eghF
F = a ?? b? c ? bc ? de. 10111
Следствие 3. Если Ai, i = 1, 2, 3, …, k – 1011 0
произвольные двоичные векторы, не свя-
1011 1
занные сдвигом, то существует одна буле-
1011 1
ва функция F, преобразующая A1 в любой
вектор Ai , т. е. A2 = F(A1), A3 = F(A2), …, 01101
Ak = F (Ak – 1) и A1 = F(Ak). 0110 1
П р и м е р 4. Пусть требуется найти
0110 0
булеву функцию F, обеспечивающую следу-
0110 1
ющие преобразования: A1 > A2 > A3 > A1,
10011
где A1 = 1101, A2 = 0110, A3 = 1001.
Упражнение. Используя описанную 1001 0
выше методику, выпишите часть таблицы 1001 0
истинности, постройте диаграмму Вейча и
1001 1
найдите один из вариантов решения.

23
Пример 4 Таблица истинности этой функции будет
иметь следующий вид.
a b cd eghF Одно из возможных решений
F = a? b ? g ? bc ? ? eh.
11010
1101 1 Представляет интерес определение коли-
чества наборов длины n, не связанных сдви-
1101 1
гом, и их доли в общем числе двоичных на-
1101 0
боров длины n.
01101
Расчет произведем для наборов длины n
0110 0 веса q (т. е. содержащих ровно q единиц).
Для этого заметим, что если в младшем раз-
0110 0
ряде поставить 1, а остальные q – 1 единиц
0110 1
на оставшихся n – 1 позициях расставить так,
10011
чтобы получить разные двоичные коды, то
1001 1
мы получим все наборы, не связанные сдви-
1001 0 гом, содержащие ровно q единиц. Тогда чис-
ло таких наборов
1001 1
?1
S (n, q) = P(n ? q, q ? 1) = C q?1 .
n
Поскольку общее число наборов длины n веса q равно C q , тоn
доля наборов, не связанных сдвигом, составляет q/n. Так, например,
при n = 20, q = 10 S(20, 10) = 92378.
2.3. Минимизация слабо определенных булевых функций
Возьмем теперь произвольный вектор A (1 0 0 1 1 1 0 1 0 0 0 1) и
некоторую функцию F = ai & ai – 3 ? ai + 2 ? ai + 5 . Применив преобразо-
вание F к вектору A, получим вектор B (1 1 0 1 0 1 1 1 0 1 0 0). Для того
чтобы найти функцию, которая по вектору B восстанавливала бы век-
тор A, можно построить таблицу истинности частично определенной
функции 23 аргументов (табл. 6.).
Если из данной матрицы выделить минимальный набор столбцов так,
чтобы в матрице, построенной только из этих столбцов, строки, на кото-
рых элементы вектора A принимают значение 1, отличались бы от строк,
на которых элементы вектора A принимают значение 0, то выделенные
столбцы будут составлять минимальный набор аргументов функции F.
Обратная к F функция, которая восстанавливает вектор A по векто-
ру B, определена всего на 12 наборах аргументов, а на N = 223 – 12
24
Таблица 6


a b c d e f g h i j k l m n o p q r s t u v w A

1 1 0 1 0 1 1 1 0 1 0 0 1

1 1 0 1 0 1 1 1 0 1 0 0 0

1 1 0 1 0 1 1 1 0 1 0 0 0

1 1 0 1 0 1 1 1 0 1 0 0 1

1 1 0 1 0 1 1 1 0 1 0 0 1

1 1 0 1 0 1 1 1 0 1 0 0 1

1 1 0 1 0 1 1 1 0 1 0 0 0

1 1 0 1 0 1 1 1 0 1 0 0 1

1 1 0 1 0 1 1 1 0 1 0 0 0

1 1 0 1 0 1 1 1 0 1 0 0 0

1 1 0 1 0 1 1 1 0 1 0 0 0

1 1 0 1 0 1 1 1 0 1 0 0 1
25
наборах не определена. Следовательно, ее можно доопределить 2N спо-
собами. Это число настолько велико, что задачу однозначного нахож-
дения обратной к F функции можно считать нереальной.
2.4. Использование булевых преобразований
двоичных последовательностей в криптографии
Поскольку преобразование F является односторонней функцией и
нахождение обратной функции неоднозначно, можно использовать эти
преобразования в криптографии.
1. А и В знают булеву функцию F. А передает В некоторую последо-
вательность А1, и оба вырабатывают общий ключ K1 = F(A1) = A2,
который после однократного применения уничтожается. Затем с по-
мощью этой же функции F А и В вырабатывают новый ключ K 2 =
= F(A2) = F(F(A1)) и т. д. Последовательность А1 может формиро-
ваться в соответствии с алгоритмом RSA или быть стандартной, на-
пример, 101010101010101…, и в этом случае вообще не передаваться
по открытому каналу. Периодически исходная последовательность A1
может меняться. Одноразовые ключи могут использоваться в системе
DES или анологичной системе (следствие 3).
2. Булевы преобразования могут использоваться для проверки паро-
ля. Так, если А отправляет В запрос А1, а В отвечает на него В1 = F(A1),
то активный перехватчик, даже зная А1 и В1, не может однозначно вос-
становить функцию F, поэтому, маскируясь под “своего”, на другой зап-
рос А2 ответит результатом преобразования другой функцией F / (A2) ?
? F(A2) (теорема).
3. Каждый клиент банка снабжен набором паролей. Подписывая свое
сообщение любым из них, клиент может быть уверен, что банк опреде-
лит, от кого пришло сообщение (следствие 2).
4. При заключении контракта по электронной почте отправитель со-
общения может ставить под ним различные подписи. Перехватчику при
этом трудно отследить автора сообщения. Однако, как получающая
сторона, так и арбитр (зная функцию F) сумеют доказать, кто подписы-
вал контракт.
5. Функция F может быть выбрана так, чтобы изменять только неко-
торые фрагменты текста, например, даты, суммы платежа, шифры, па-
роли, оставляя текст осмысленным. При обработке всего сообщения
функцией F получатель имеет истинный текст, а осмысленность его

26
вводит перехватчика в заблуждение. При попытке активного перехват-
чика исказить некоторые фрагменты текста осмысленность сообще-
ния может быть потеряна, и тогда получатель будет знать, что вмешал-
ся активный перехватчик (следствие 2, пример 3).
Важно определить класс нетривиальных функций 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)…
В качестве примера такой функции F для 6-разрядных произвольных
векторов В (b1, b2, …, b6) можно взять функцию F = ai ?2 ai + 4 ? ai ?4 ai +3 .
Значения элементов вектора X для этой функции определятся следую-
щим образом:
x1 = b1 ? b2 ? b3 ? b4 ? b6,
x2 = b4,
x3 = b1 ? b2 ? b3 ? b4 ? b5 ? b6,
x4 = b4 ? b6,
x5 = b1 ? b4 ? b6,
x6 = b1 ? b2 ? b4 ? b6.
Для 10-разрядных векторов можно взять функцию F = ai ? ai -6 ai +5 .
В этом случае элементы вектора X будут вычисляться следующим
образом:
x1 = b1 ? b6,
x2 = b1 ? b2 ? b6 ? b7,
x3 = b1 ? b2 ? b3 ? b6 ? b7 ? b8,
x4 = b1 ? b2? b3 ? b4 ? b6 ? b7 ? b8 ? b9,
x5 = b1 ? b2 ? b3 ? b4? b5 ? b6 ? b7 ? b8 ? b9 ? b10,
x6 = b6 ? 1,
x7 = b1 ? b6 ? b7? 1,
x8 = b1 ? b2 ? b6 ? b7 ? b8 ? 1,
x9 = b1 ? b2 ? b3 ? b6 ? b7 ? b8 ? b9 ? b10 ? 1,
x10 = b1 ? b2 ? b3? b4 ? b6 ? b7 ? b8 ? b9 ? b10 ? 1.
Если исходный текст состоит из последовательности векторов Bi,
например, B 1 = 1011100011; B 2 = 1111111111; B 3 = 0111100011;
27
B4 = 0000000000; B5 = 1011011100; B6 = 0110001011 ; тогда отправи-
тель сообщений может вычислить соответствующие векторы X i
криптотекста и передать их по открытому каналу: X1 = 1100010000;
X2 = 0000000000; X3 = 0100011000; X4 = 0000011111; X5 = 0110000101;
X6 = 0010110110.
Получатель сообщения с помощью функции F = ai ? ai –6 ai +5 пре-
образует векторы Xi в векторы открытого текста Bi.
Нелегальный перехватчик сообщения, даже зная пары Bi и Xi , не
сможет восстановить функцию F.
Заключение
В пособии в краткой форме изложены методы анализа и синтеза ком-
бинационных схем на основе свойств булевых функций. Рассмотрен
метод минимизации как полностью определенных, так и частично опре-
деленных булевых функций с использованием диаграмм Вейча.
Показано, что диаграммы Вейча можно применять и для упрощения
произвольных булевых выражений. К сожалению, этот метод имеет су-
щественные ограничения: он может применяться к функциям, число
аргументов которых не превышает 10–11.
Рассмотрена задача преобразования произвольных двоичных после-
довательностей булевыми функциями. Доказана теорема, позволяющая

<< Предыдущая

стр. 4
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>