РАЗДЕЛ 2.
ВЫДЕЛЕНИЕ И ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ КЛАССА НЕЛИНЕЙНЫХ БУЛЕВЫХ ФУНКЦИЙ, ИСПОЛЬЗОВАНИЕ КОТОРОГО ПОЗВОЛЯЕТ ПОВЫСИТЬ ЭФФЕКТИВНОСТЬ АСЗИ ОСНОВАННЫХ НА БФП
Алгоритмические средства защиты информации являются одной из важнейших составляющих современных информационных технологий [33,81,82]. Анализ структур АСЗИ, основанных на БФП, показывает, что уровень их стойкости и производительность в определяющей степени зависят от используемых БФП, которые основаны на системах булевых функций, обладающих высокими значениями характеристик устойчивости к методам анализа [21, 83,84].
В первом разделе было показано, что наиболее слабой стороной известных методов построения БФП, удовлетворяющих требованиям устойчивости к анализу, является экспоненциальная вычислительная сложность. Это накладывает существенные технологические ограничения на повышение эффективности АСЗИ, препятствуя синтезу БФП большой разрядности. С другой стороны, применение преобразований большой разрядности требует разработки эффективных вычислительных структур, реализующих такие преобразования как программными, так и аппаратными средствами.
Создание эффективных методов синтеза БФП для АСЗИ и способов организации их вычисления может быть произведено на основе замкнутого класса булевых функций, удовлетворяющих требованиям, указанным в предыдущем разделе. Использование такого класса, с одной стороны, позволит гарантировать стабильность характеристик любых линейных комбинаций составляющих преобразование булевых функций. С другой стороны, благодаря унификации операций при организации вычисления булевых функций, имеющих одинаковую структуру, возможна разработка эффективной реализации таких преобразований [85] как программными, так и аппаратными средствами.
2.1. Теоретическое исследование свойств булевых функций, содержащих конъюнкцию линейных функций невырожденного базиса
Многие существующие методы синтеза БФП для АСЗИ [8,9,65,66,86] используют табличное представление булевых функций и их систем при построении преобразований. Преимуществом такого подхода является то, что он обеспечивает высокую скорость реализации систем сложных функций программными средствами, а, следовательно, и скорость определения характеристик, важных при построении БФП для АСЗИ. Однако, при этом, объемы памяти, требуемой для хранения БФП, растут пропорционально m2n (для n?m разрядного преобразования - m функций, определенных на множестве из n аргументов), что уже для 32-х аргументов выходит за рамки возможностей современных компьютеров. С другой стороны табличное предоставление булевых функций осложняет аппаратную реализацию преобразований, поскольку построение на основе таблиц истинности логических схем и их оптимизация требует дополнительных затрат ресурсов, резко возрастающих с увеличением разрядности преобразования. Таким образом, ввиду отмеченных недостатков, табличное представление не может быть использовано для построения БФП большой разрядности.
Другим подходом является использование при построении преобразований для АСЗИ булевых функций, заданных в аналитическом виде. Преимущество такого подхода заключается в том, что аналитическое представление булевых функций требует значительно меньших объемов памяти, чем табличное. В дополнение к этому, аналитическое описание булевой функции является эквивалентом логической схемы, основанной на соответствующем базисе, следовательно, выбирая различную булеву алгебру для представления функций можно получить описание аппаратной реализации в соответствующем базисе без дополнительных затрат.
При построении БФП для АСЗИ удобной представляется алгебраическая нормальная форма (АНФ) булевых функций, представляющая собой сумму по модулю 2 конъюнктивных термов в алгебре Жегалкина. АНФ в отличие от других аналитических представлений (булева алгебра, стрелка Пирса, штрих Шеффера и др.) не нуждается в трудоемком этапе минимизации для построения логических схем при аппаратной реализации.
Фактором, осложняющим применение аналитического представления булевых функций при построении БФП, является трудоемкость программной реализации сложных функций и их систем, а, следовательно, недопустимо низкая скорость определения характеристик функций (балансность, нелинейность, строгий лавинный эффект) важных при построении БФП для АСЗИ. Универсальным подходом является преобразование функции в табличное представление для определения её характеристик, однако при этом проявляются все недостатки использования табличного представления, указанные выше.
Альтернативой является проведение дополнительного теоретического исследования булевых функций с целью определения признаков наличия у заданных в АНФ функций свойств, необходимых при построении БФП для АСЗИ. Поскольку нахождение универсальных признаков маловероятно, следует ограничить область исследования некоторым классом булевых функций, в рамках которого будет возможно построение БФП с указанными в предыдущем разделе характеристиками.
Перспективными с точки зрения решения задачи построения БФП для АСЗИ представляются булевы функции, содержащие конъюнктивную составляющую в виде суперпозиции элементов невырожденного линейного базиса. Конъюнктивная составляющая обеспечивает нелинейность таких функций, а использование суперпозиции позволяет распространять определенные свойства на целые семейства булевых функций, имеющих одинаковую структуру.
Для удобства дальнейшего изложения введем определение полной линейной функции. Полной линейной функцией Ф(Х) от n переменных, определенной на непустом множестве переменных Х, называется функция-сумма по модулю 2 всех переменных множества Х (т.е. функция не имеющая фиктивных переменных в множестве Х):
Ф(Х) = x1 ? x2 ? ... ? xn.
Рассмотрим нелинейные булевы функции, состоящие из конъюнктивной суперпозиции линейных составляющих:
fk(X) = Ф(X1)* Ф(X2)* ... * Ф(Xk) ? L(X), (2.1)
где Xi ? X ? i=0...k, Xi ? Xj = ? ? i,j: i ? j, X1 ? X2 ? ... ? Xk = X,