Перемешивающие свойства преобразований

Лекция 1. Перемешивающие свойства преобразований 1.1. Существенные переменные булевых функций Пусть – булева функция (б.ф.) переменных. Обозначим , . Векторы и называются соседними по –й координате, если и для любого , . Переменную называют фиктивной или несущественной для б.ф. , если для любых соседних по -й координате векторов и , . В противном случае переменная - существенная. Таблицу б.ф., имеющей фиктивную переменную, можно сократить на 1 столбец и по числу строк в 2 раза. Б.ф. и называют равными (), если одну можно получить из другой введением или удалением фиктивных переменных. Есть две б.ф., не имеющие существенных переменных: константы «0» и «1». Канонический вид АНФ задан суммой мономов по модулю 2: , (1.1) где – двоичный коэффициент при одночлене (мономе) . Заметим, что зависит от фиктивно равен 0 коэффициент при каждом мономе, зависящем от , . 1.2. О сложности решения систем уравнений Алгебраические (аналитические) методы анализа криптографических систем основаны на решении систем уравнений, связывающих элементы ключей, открытых и шифрованных текстов. Системы уравнений, возникающие в криптоанализе, как правило, имеют решения (уравнения являются совместными). Решение системы возможно за конечное число вычислительных шагов, что определяется возможностью полного перебора конечного числа ключей. Однако проблема решения является в общем случае сложной (что косвенно подтверждается теорией сложности вычислений), так как число необходимых операций компьютера зависит от длины ключа экспоненциально. Вместе с тем, для частных классов систем уравнений сложность решения может быть значительно ниже. Положим, что уравнения составлены и размещены в памяти вычислителя. Рассмотрим типичный случай, когда в левой части систем уравнений записаны булевы функции, – бинарный ключ длины . Пусть требуется решить систему (1.2) булевых уравнений: Всякий ключ , при котором удовлетворяется система уравнений (1.2), называется ее истинным решением (или просто решением). (1.2) Полное опробование требует перебора до вариантов ключа и подстановки вариантов в каждое уравнение. Примем за одну операцию подстановку в любое уравнение системы (1.2) любого варианта ключа с целью проверки выполнимости уравнения. Такой тотальный алгоритм требует выполнения до операций. При больших переборный алгоритм нереально реализовать в приемлемое время. Отметим, что алгоритм не требует значительной памяти. Пусть в левой части записано треугольное преобразование, т.е. система уравнений имеет вид: (1.3) Алгоритм последовательного опробования с использованием особенностей системы уравнений (1.3) опробует на каждом шаге значения только «новых» переменных, т.е. только тех, которые не были опробованы на предыдущих шагах. Обозначим множество номеров существенных переменных функции . В системе (1.3) имеем: , . Построим алгоритм опробования переменных: 1) Опробуем 2 значения переменной , подставляем их в 1-е уравнение системы (1.3). Значение бракуется, если . В противном случае выполняем следующий шаг. 2) Опробуем все значения пары переменных при каждом неотбракованном значении , например, при , подставляя их во 2-е уравнение системы. Значение бракуется при . В противном случае выполняем -й шаг, . Пусть . Опробуем все значения набора переменных при , подставляя их в -е уравнение системы (1.3). Значение набора бракуется, если . В противном случае выполняем следующий шаг. Если же и , то данный набор - решение системы уравнений (1.3). Метод не требует большой памяти, надёжность его равна 1 (потеря истинного решения исключена). Оценим среднюю трудоёмкость метода последовательного опробования в рамках следующей вероятностной модели. Пусть для любой правой части системы уравнений (1.3) при случайном равновероятном выборе двоичного набора : 1) , ; 2) уравнения системы (1.3) независимые: при подстановке в различные уравнения любых значений переменных выполнимость каждого уравнения не зависит от выполнимости других уравнений. Элементарной операцией (эл.оп.) алгоритма последовательного опробования считаем проверку выполнимости любого уравнения системы (1.3) при подстановке в него любого набора значений переменных. Обозначим: - средняя трудоёмкость -го шага алгоритма; - среднее число наборов , не отбракованных после -го шага, . Тогда , где из описания алгоритма имеем: , . Отсюда , т.е. трудоёмкость решения системы (1.3) линейно зависит от . Реализация метода эффективна и для треугольно-ступеньчатой системы уравнений. Пусть множество из уравнений системы разделено на непустых подмножеств, где , , и в левой части системы , , …, . Построим шагов опробования переменных: 1) опробуем значений набора переменных , подставляя их в первых уравнений системы. Значение набора бракуется, если . Для каждого оставшегося набора выполняем следующий шаг. 2) опробуем значений набора переменных и подставляем набор во вторую группу из r2 уравнений. Этот набор бракуется, если . Для каждого оставшегося набора выполняем следующий шаг и т.д., всего шагов. Реализация метода как правило не требует значительной памяти, надёжность метода равна 1. Оценим среднюю трудоёмкость метода последовательного опробования в условиях той же вероятностной модели. Из описания алгоритма имеем: , ,…,, . Следовательно, ++…+. Отсюда если , то . Для системы уравнений (1.2) оценим трудоёмкость последовательного опробования в общем случае. Обозначим решетку всех подмножеств множества . Заметим, что в описанных алгоритмах последовательности опробования подмножеств переменных соответствует цепям в . В первом алгоритме – цепи длины , и во втором алгоритме - цепи длины . В общем случае пометим в символом подмножества . Наилучший алгоритм опробования соответствует одной из наиболее длинных цепей, начинающихся в помеченной вершине и завершающихся в вершине . Алгоритм надежен, так как множество вложено в один из элементов цепи, . Средняя трудоемкость алгоритма тем меньше, чем длиннее цепь в . Вообще длина цепи не больше , отсюда . Следовательно, если близок к n, то близка к трудоёмкости метода полного перебора. Пример 1.2.1. Оценим среднюю трудоёмкость двух алгоритмов последовательного опробования для системы уравнений: Здесь , , , . Пометим эти множества - вершины решетки (на рис.1 изображена часть решетки). Рисунок 1. Схема алгоритма опробования Построим два 4-шаговых алгоритма последовательного опробования: на основе цепи 1: - и на основе цепи 2: . Приведем характеристики этих алгоритмов. Таблица 2.1. Характеристики 4-шаговых алгоритмов опробования алгоритм на основе цепи 1 алгоритм на основе цепи 2 № шага 1 2 3 4 1 2 3 4 № уравнения 1 2 3 4 3 4 1 2 №№ опробуемых (новых) переменных 2 1 трудоемкость опробования на шаге 2 число неотбракованных вариантов после шага 1 1 Средняя трудоемкость алгоритма опробования на основе цепи 1 равна 18, на основе цепи 2 равна 14. Итак, сложность определения ключа зависит от множеств . Далее эта зависимость характеризуется с помощью матриц и графов. 1.3. Начала теории графов 1.3.1. Основные понятия, способы задания графов. Множество и бинарное отношение на множестве образуют пару, которую называют графом (обозначается . Элементы множества называются вершинами, а элементы множества — ребрами графа. Если множества и конечные, то граф называют конечным; при граф называют -вершинным, или графом с вершинами. Обычно вершина отождествляется с номером . Если , то говорят, что данное ребро соединяет вершины и или инцидентно этим вершинам, где при вершины и смежные. Ребро называется петлей в вершине . Ребра, инцидентные общей вершине , называют смежными. Вершина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная одному ребру, и само это ребро называют висячими, или концевыми. Несколько ребер, инцидентных общей паре вершин, называют кратными или параллельными. Граф без кратных ребер и петель называется полным, если смежны его любые две вершины. Граф с петлями полный, если смежны его любые две вершины и в каждой вершине есть петля. Если элементы каждой пары упорядочены, то называют ориентированным графом, кратко орграфом, и его ребра называют дугами. Дуга орграфа изображается стрелкой, исходящей из и заходящей в . Если бинарное отношение симметрично, то граф называется неориентированным, и ребро графа изображается отрезком. Далее неориентированный граф – просто граф. Граф (орграф) помеченный, если некоторыми символами помечены его вершины и/или ребра (дуги). Помеченные элементами множества вершины-вершинного графа можно задать множеством , где . Помеченные элементами множества ребро или дугу можно задать тройкой , где . Мультиграфом называют граф с кратными (параллельными) ребрами или дугами, т.е. допускается наличие нескольких ребер или дуг вида . Метки кратных помеченных ребер или дуг не обязательно одинаковы. В графе степенью вершины , обозначаемой , называется число ребер, инцидентных вершине . Вершине орграфа соответствует пара чисел , где — число дуг, заходящих в вершину, и — число дуг, исходящих из вершины. Числа и называются полустепенью захода и полустепенью исхода вершины . Отметим 2 способа задания графов и орграфов с n вершинами. 1) списком ребер (дуг) и изолированных вершин; для мультиграфа следует указать кратности ребер (дуг), либо кратным ребрам (дугам) присвоить различные номера в списке; 2) матрицей смежности (соседства) вершин графа, орграфа или мультиграфа размера (обозначается , где — число ребер или дуг вида . Для графа при любых . Число петель графа равно сумме элементов главной диагонали матрицы смежности. Матрица смежности однозначно задает непомеченный орграф. относится к неотрицательным матрицам, все элементы которых не меньше 0, записывают . Если все элементы матрицы больше 0, то она называется положительной, записывают . 1.3.2. Пути в графе, связность. В графе (орграфе) путем из вершины в вершину (соединяющим и ) называется система ребер (дуг): , где ; вершины пути и называются соответственно начальной и конечной. Этот путь задан короче в виде последовательности вершин: . Длиной пути (обозначается ) называют число составляющих его ребер. Если имеется путь из в длины , то говорят, что вершина графа -достижима (или достижима за шагов) из вершины . Если ребро или дуга (вершина ) принадлежит пути, то говорят, что путь проходит через ребро или через дугу (через вершину ). На множестве путей графа определена частичная полугрупповая операция конкатенации (присоединения), обозначим ее . Для путей и конкатенация допустима . При . Теорема 1.3.1. Пусть — матрица смежности вершин орграфа и , тогда в число путей длины из в равно , Доказательство. (индукция по ). Для теорема верна по определению матрицы . Докажем ее при любых для , если она верна для . По определению , тогда по правилу умножения матриц . (1.4) По предположению есть число путей длины в графе из в . Тогда есть число путей длины из в таких, что предшествует вершине j. Просуммировав по , получаем общее число путей длины в графе из в , которое в силу (1.4) равно . Пример 1.3.1. Найдем число путей длины 6 из 1 в 3 и из 2 в 5 в 5-вершинном орграфе, заданном списком дуг: (1,3), (1,4), (2,1), (2,2), (2,5), (3,2), (3,4), (3,5), (4,1), (4,3), (5,2), (5,4), (5,5). Построим — матрицу смежности вершин орграфа: . Возводя в квадрат, находим матрицы и затем : , . Найдем искомые элементы матрицы : , . Первое число получено скалярным умножением 1-й строки матрицы на 3-ю строку матрицы ; второе число получено скалярным умножением 2-й строки матрицы на 5-ю строку матрицы . Путь в графе называют циклом (в орграфе — контуром). Петля есть цикл длины 1. Путь (цикл) называется простым, если он не проходит дважды ни через одну вершину. Простой путь (цикл) в графе не проходит дважды ни через одно ребро. Длина простого пути не больше числа вершин. Путь (цикл), проходящий через все вершины графа, называется полным. Длина полного пути в -вершинном сильно связном орграфе не больше . Циклы в графе называются независимыми, если множества вершин этих циклов попарно не пересекаются. Подходом к циклу называется путь в графе, все вершины которого, за исключением последней, являются ациклическими. Неориентированный граф (орграф) связный (сильно связный), если в нем найдется путь из любой вершины в любую. Орграф связный, если связен неориентированный граф, полученный заменой в нем дуг на ребра. В -вершинном графе обозначим множество всех путей из в . Длина кратчайшего пути из в в (или расстояние от до в ) равно: ; всякий путь из в длины называют кратчайшим путем в из в . В общем случае кратчайший путь определен неоднозначно. Замечание. В некоторых задачах длину следует положить равной не нулю, а длине кратчайшего контура, проходящего через вершину . Расстоянием от до в , где и – подмножества вершин, равно: . Диаметр п-вершинного сильно связного орграфа равен: . Диаметр -вершинного сильно связного орграфа не более . В графе из следует: для любой пары вершин и для некоторой пары вершин . Из теоремы 1.4.1 следует: . Пример 1.3.2. Диаметр орграфа из примера 1.4.1 равен 2: матрица содержит нули и . 1.4. Примитивные графы и неотрицательные матрицы Первая постановка задачи о неотрицательных квадратных матрицах была дана Фробениусом в 1912 г.: «имеются ли при неотрицательной матрице положительные матрицы во множестве ,,…,,…}?». Иными словами, содержит ли положительные матрицы циклическая полугруппа ? Если содержит, то матрица называется примитивной, и наименьшее натуральное , при котором , называется экспонентом матрицы , обозначается . Если полугруппа не содержит положительных матриц, то матрица называется не примитивной и полагаем . Множество целочисленных неотрицательных матриц порядка обозначим . Множество матриц смежности вершин -вершинных орграфов с петлями совпадает с , поэтому понятия примитивности и экспонента распространены c на орграфы. Связь между графами и устанавливает теорема 1.3.1. Следовательно, примитивность орграфа и величина экспонента определена свойствами путей в графе, в частности, орграф полный. Свойства примитивности и экспонента равносильно интерпретируется на матричном и на графовом языке. Далее - матрица смежности вершин орграфа . Мультипликативная полугруппа гомоморфно отображается, с помощью замены каждого положительного элемента единицей, на полугруппу всех 0,1-матриц порядка (все элементы которых суть 0 или 1), обозначим ее . Это отображение согласовано со свойством примитивности, то есть прообразом любой примитивной 0,1-матрицы является класс примитивных матриц из , и прообразом любой не примитивной 0,1-матрицы является класс не примитивных матриц из . Далее рассмотрим мультипликативный моноид , , где умножение выполняется как для целочисленных матриц с последующей заменой положительных чисел единицами. На множестве матриц одинакового размера над упорядоченным множеством определен частичный порядок. Если , , то для всех допустимых пар . Из правила умножения матриц и из основной теоремы следует: 1) примитивная матрица не содержит нулевых строк и столбцов, отсюда если , то при любом ; 2) монотонность: если , то ; 3) если , то . 4) наследственность: если примитивная, то и примитивная, ; 5) примитивный орграф является сильно связным; 6) не меньше диаметра графа ; 7) случайно равновероятно выбранная матрица при с вероятностью, стремящейся к 1, является примитивной и . Пример 1.4.1. Пусть , тогда , . Отсюда примитивная, . Орграф сильно связный, он состоит из контура (1,2,3) и петли в вершине «1». Матрица не примитивная. 1.5. Оценки экспонентов матриц и графов Работы с основополагающими результатами опубликованы в середине XX века Виландтом (Wielandt H.), Перкинсом (Perkins P.), соавторами Далмэджем и Мендельсоном (Dulmage A.L., Mendelsohn N.S.), установившими термин «экспонент», и др. Получены условия примитивности и оценки экспонентов матриц и орграфов, как универсальные, так и частные. Пусть содержит множество контуров длины соответственно, где . Обозначим . Критерий примитивности орграфа (Перкинс, 1961) определяется множеством его контуров: сильно связный орграф примитивный содержит множество контуров такое, что НОД. Универсальная оценка для -вершинного графа дана Виландтом, 1950: . (1.5) Известны более точные оценки для -вершинных орграфов. Если содержит контур длины , то . (1.6) Если - диаметр примитивного орграфа , то . Если содержит множество контуров , то , (1.7) здесь – число Фробениуса для аргументов , равное наибольшему целому числу, не принадлежащему аддитивной полугруппе , , где – длина кратчайшего пути из в , проходящего через некоторую вершину контура длины , . Заметим, что ; . В общем случае технически трудно вычислить число Фробениуса , так как при не существует простых формул, однако известны быстрые компьютерные алгоритмы. Неявно оценена ниже. Теорема 1.5.1 Если примитивный -вершинный орграф содержит примитивное множество контуров длин , то . (1.8) Оценка (1.8) уточнена с учетом структуры орграфа . Обозначим – часть орграфа . Теорема 1.5.2. Если орграф содержит примитивное множество контуров длин и орграф связный, то . (1.9) Из (1.6) следует, что для сильно связного орграфа с петлей при . (1.10) Эта оценка уточнена с учетом (1.8). Обозначим: – множество вершин с петлей в орграфе , - длина кратчайшего пути из из в , проходящего через вершину . В имеются пути из в любой длины . Следовательно, для примитивного орграфа с петлями . (1.11) Оценки (1.8)-(1.10) уточены, если в известны длины двух контуров. Теорема 1.5.3. Пусть n>2 и Г содержит два простых контура длины и , имеющих общих вершин, где и . Тогда , ; (1.12) , . (1.13) 1.6. Метод быстрого экспоненцирования Метод быстрого экспоненцирования (удвоение степени матрицы на каждом шагу вычислений) можно использовать как для распознавания примитивности матрицы, так и для нахождения точного значения ее экспонента. Используем оценку (1.5). В силу свойства 1) раздела 1.5 матрица порядка примитивная при . Тогда при последовательном вычислении матриц распознавание примитивности матрицы требует не более возведений матриц в квадрат. Пусть и содержит нули, где . Тогда нахождение равносильно нахождению , при котором и содержит нули, где . Для дихотомического поиска такого требуется еще не более умножений матриц. Вычислительная сложность обеих задач не превышает