2001-0084-0-01 (1274906), страница 4
Текст из файла (страница 4)
Если Ai и Bi – произволь01ные векторы, причем Ai не связаны сдвигом,то существует одна булева функция F, пре1образующая каждый вектор Ai в соответ1ствующий ему вектор Bi.2. Пусть требуется найти одну функцию F, преобразую-1 0 0 11 0 0 11 0 0 10 10 1 10 1 1 00 1 1 01Примерщую векторы:A1 = 1011 в вектор B1 = 0110,A2 = 0111 в вектор B2 = 1001,A3 = 0101 в вектор B3 = 1110.22Построим часть таблицы истинности функции F, выписывая только те наборы, на которых функция определена.Упражнение.
Постройте диаграмму Вейча функции F и убедитесь в том, что при некотором способе доопределения функциябудет иметь видF = d ∨ e g h ∨ bc ∨ be .В частном случае следствия 2 некоторыезначения Bi могут совпадать с соответствующими им Ai.П р и м е р 3. Пусть требуется найтифункцию F, преобразующую векторы:A1 = 1011 в вектор B1 = 1011,A2 = 0110 в вектор B2 = 1101,A3 = 1001 в вектор B3 = 1001.Здесь векторы B1 = A1, B3 = A3, B2 ≠A2.Построим часть таблицы истинности функции F.Упражнение.
Проверьте, что при некотором способе доопределенияF = a ∨ b c ∨ bc ∨ de.Следствие 3. Если Ai, i = 1, 2, 3, …, k –произвольные двоичные векторы, не связанные сдвигом, то существует одна булева функция F, преобразующая A1 в любойвектор Ai , т. е. A2 = F(A1), A3 = F(A2), …,Ak = F (Ak – 1) и A1 = F(Ak).П р и м е р 4. Пусть требуется найтибулеву функцию F, обеспечивающую следующие преобразования: A1 → A2 → A3 → A1,где A1 = 1101, A2 = 0110, A3 = 1001.Упражнение. Используя описаннуювыше методику, выпишите часть таблицыистинности, постройте диаграмму Вейча инайдите один из вариантов решения.Пример 2ab c de g h F1 0 1 1 01 0 1 11 0 1 1111 0 1 100 1 1 1 10 1 1 10 1 1 1000 1 1 110 1 0 1 10 1 0 10 1 0 1110 1 0 10Пример 3ab c de g h F1 0 1 1 11 0 1 11 0 1 11 0 1 10110 1 1 0 10 1 1 00 1 1 00 1 1 01011 0 0 1 11 0 0 11 0 0 11 0 0 100123Пример 4ab c de g h F1 1 0 1 01 1 0 11 1 0 11 1 0 11100 1 1 0 10 1 1 00 1 1 00 1 1 00011 0 0 1 11 0 0 11 0 0 11 0 0 1101Таблица истинности этой функции будетиметь следующий вид.Одно из возможных решенийF = a b ∨ g ∨ bc ∨ eh.Представляет интерес определение количества наборов длины n, не связанных сдвигом, и их доли в общем числе двоичных наборов длины n.Расчет произведем для наборов длины nвеса q (т.
е. содержащих ровно q единиц).Для этого заметим, что если в младшем разряде поставить 1, а остальные q – 1 единицна оставшихся n – 1 позициях расставить так,чтобы получить разные двоичные коды, томы получим все наборы, не связанные сдвигом, содержащие ровно q единиц. Тогда число таких наборовS (n, q) = P(n − q, q − 1) = C qn−−11 .Поскольку общее число наборов длины n веса q равно C qn , тодоля наборов, не связанных сдвигом, составляет 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 – 1224Таблица 6a251bcdefghijklmnopqrstuvwA11010111010011101011101001101011101001101011101001101011101001101011101001101011101001101011101001101011101001101011101001101011101001010111010000111010001наборах не определена.
Следовательно, ее можно доопределить 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;27B4 = 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.Рассмотрена задача преобразования произвольных двоичных последовательностей булевыми функциями. Доказана теорема, позволяющаяпо любым двум произвольным последовательностям находить булевовыражение, связывающее эти последовательности.С помощью приведенной теоремы автором была получена функция,которая для конкретного набора изображений выполняла преобразование, обратное известной функции Конвея.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
