Если из построенной матрицы выделить минимальный набор столбцов так, чтобы в матрице, построенной только из этих столбцов строки, на которых элементы вектора A принимают значение 1 отличались бы от строк, на которых элементы вектора A принимают значение 0, то выделенные столбцы будут составлять минимальный набор аргументов функции F.
Обратная к F функция, которая восстанавливает вектор A по вектору B, определена всего на 12 наборах аргументов, а на N= 223 – 12 наборах не определена. Следовательно, ее можно доопределить 2N способами. Это число настолько велико, что задачу однозначного нахождения обратной к F функции можно считать нереальной.
Поскольку преобразование F является односторонней функцией и нахождение обратной функции неоднозначно, возможно использовать эти преобразования в криптографии.
П.3.4. Использование булевых преобразований двоичных последовательностей в криптографии.
1.А и В знают булеву функцию F. А передает В некоторую последовательность А1 и оба вырабатывают общий ключ K1 = F(A1) = A2, после однократного применения которого ключ уничтожается. Затем с помощью этой же функции F А и В вырабатывают новый ключ K2 = 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. Каждый клиент банка снабжен набором паролей. Подписывая свое сообщение любым из них, клиент может быть уверен, что банк определит от кого пришло сообщение. (Следствие 4).
4. При заключении контракта по электронной почте отправитель сообщения может ставить под ним различные подписи. Перехватчику при этом трудно отследить автора сообщения. Однако, как получающая сторона, так и арбитр (зная функцию F) сумеют доказать, кто подписывал контракт.
5. Функция F может быть выбрана так, чтобы изменять только некоторые фрагменты текста, например, даты, суммы платежа, шифры, пароли, оставляя текст осмысленным. При обработке всего сообщения функцией F получатель имеет истинный текст, а осмысленность его вводит перехватчика в заблуждение. При попытке активного перехватчика исказить некоторые фрагменты текста осмысленность сообщения может быть потеряна, и тогда получатель будет знать, что вмешался активный перехватчик (Следствие 2 , пример 3.).
Для проведения экспериментов использовались две программы:
Заданы последовательности А и F. Находятся последовательности В.
Заданы последовательности А и В. Находится булева функция F, преобразующая А в В. Идея этой программы основана на минимизации слабоопредлеленных функций большого числа аргументов.