Введение к работе
Многие потоковые шифры состоят из линейной части, порождающей последовательность с большим периодом, обычно состоящей из одного или нескольких регистров сдвига с линейной обратной связью (linear feedback shift registers, LFSR), и нелинейной комбинирующей функции /, которая порождает выходную последовательность по данным линейным входам. Исследования криптографической устойчивости таких шифров большей частью сводятся к исследованию нелинейной функции /, в частности, к исследованию этой функции с точки зрения того, удовлетворяет или не удовлетворяет она некоторым критериям, необходимым для того, чтоб успешно противостоять различным криптографическим атакам.
Для того, чтобы противостоять этим атакам (таким, как атакам Берлекэм-па-Мэсси, различным типам корреляционных и линейных атак [27, 20, 15] и алгебраической атаке (см. [16])), функция должна удовлетворять следующим критериям:
1. Уравновешенность. Булева функция должна выдавать нули и единицы с одинаковой вероятностью.
2. Хорошая корреляционная иммунность (порядка т). Выход булевой функции должен быть статистически независим от комбинации любых т ее входов. Уравновешенная корреляционно-иммунная порядка т булева функция называется т-устойчивой.
3. Хорошая нелинейность. Булева функция должна находиться на достаточно большом расстоянии от любой аффинной функции.
4. Высокая алгебраическая степень.
5. Высокая алгебраическая иммунность. Ни функция, ни ее дополнение не должно иметь аннигиляторов низкой степени.
Также важными критериями являются низкая автокорреляция, простая схемная реализация и т.д. Критерии зачастую конфликтуют друг с другом, выяснению их взаимосвязей посвящена обширная литература.
В первой части данного исследования будут рассмотрены взаимосвязи между корреляционной иммунностью и нелинейностью для разных типов неуравновешенных булевых функций, во второй - будет исследоваться алгебраическая устойчивость различных видов функций, имеющих применение в криптографии. В третьей части будет предложена новая конструкция корреляционно-иммунных булевых функций, оптимальных по многим параметрам, при этом некоторые из известных конструкций являются частными случаями предлагаемой конструкции.
В главе 1 настоящей работы получены следующие результаты.
В разделе 1.1 даются предварительные сведения и основные понятия. В разделе 1.2 исследуется возможность существования неуравновешенной корреляционно-иммунной функции с определенным набором спектральных характеристик (коэффициентов Уолша). В разделе 1.3 улучшается нижняя оценка Зенга и Занга ([32]) на т, при которых граница нелинейности 2n l — 2т не достигается. Теперь она составляет т \п + log2 n+const, значение константы мы приводим далее точно. В разделе 1.4 исследован наиболее общий случай, когда Х/(0) = 2т+г (mod 2т+г+1) при 1 і п — т — 1, включающий неуравновешенные функциии с нелинейностью 2n_1 — 2m+1. Показано, что для достаточно больших п такая нелинейность для неуравновешенных функций достигаться не может, потому что на т получена оценка т \п+ -Hog2n + 0(г), значение 0{г) мы далее раскрываем. Заметим, что в работе Таранникова [29] доказывается, что данная верхняя оценка нелинейности 2"-1 — 2m+1 m-устойчивых булевых функций от п переменных достигается при О.бп— 1 т п — 2. Поэтому при больших т максимальная нелинейность неуравновешенных корреляционно-иммунных функций порядка т меньше максимальной нелинейности m-устойчивых функций.
Таким образом, хотя верхняя оценка нелинейности 2П-1 — 2т+1 для неуравновешенных корреляционно-иммунных функций выше, чем для уравновешенных, мы видим, что при больших т большие значения нелинейности достигаются именно для уравновешенных функций.
Далее, в главе 2 рассматривается алгебраическая иммунность булевых функций. Алгебраическая иммунность - это способность противостоять разного рода алгебраическим атакам на регистры сдвига с линейной обратной связью (linear feedback shift registers, LFSR). Эти атаки впервые были предложены в [16]. Они раскрывают секретный ключ путем решения системы уравнений, зависящих от многих переменных. Данные системы уравнений описывают соотношения между битами ключа/состояния и выходными битами / (комбинирующей функции для LFSR). Если найдено такое соотношение низкой степени, алгебраические атаки очень эффективны ([17]).
В [16] показано, что указанные соотношения низкой степени и, соответственно, успешные алгебраические атаки существуют для некоторых хорошо известных шифров, которые иммунны по отношению ко всем другим известным атакам. В частности, доказано, что соотношение малой степени существует для шифров, использующих комбинирующую функцию / с малым количеством входов. Эти соотношения малой степени можно получить, получая многочлены малой степени, содержащие / в качестве делителя, т.е. умножая функцию / на подходящие функции д малой степени так, чтобы произведение f-g снова было малой степени. Если для функции / такая функция д существует (причем / не обязательно должна иметь малое количество входов), то алгебраическую атаку можно успешно провести. Таким образом, изучение булевых функций с точки зрения существования функций малой степени, содержащей данную в качестве делителя, имеет как теоретический, так и практический интерес.
В [16] предложено три разновидности такого рода атак. В [22] авторы сводят эти три вида к двум и вводят новый термин - алгебраическая иммунность. Авторы доказывают, что если алгебраическая иммунность достаточно высока, то алгебраическим атакам можно успешно противостоять.
Ранее важными критериями для комбинирующих функций в LFSR признавались высокая алгебраическая степень, высокий порядок корреляционной иммунности (устойчивости) и большое расстояние до множества аффинных функций (высокая нелинейность), чтобы успешно противостоять атакам Берлекэмпа-Мэсси и различным типам корреляционных и линейных атак [20, 15]. Существуют различные взаимосвязи между ними, не позволяющие одновременно достигать оптимальных по всем критериям параметров, например, неравенство Зигенталера, утверждающее, что корреляционно-иммунная порядка т функции от п переменных не может иметь алгебраическую степень большую, чем п — т.
Требование высокой алгебраической иммунности может конфликтовать с требованиями удовлетворения остальным критериям. В [22] авторы показали, что, например, функции класса Майораны-Макфарланда, имеющие высокую устойчивость, высокую нелинейность (асимптотически порядка 2п— 1) и оптимальную алгебраическую степень ([19, 14, 12, 23], - имеют при этом достаточно низкую алгебраическую иммунность и не могут противостоять алгебраическим атакам.
В главе 2 следующим образом исследуется алгебраическая иммунность.
В разделе 2.1 даются предварительные сведения и основные понятия. В разделе 2.2 с точки зрения алгебраической иммунности рассматривается одна рекурсивная последовательность функций, и доказывается, что последовательность порядков алгебраической иммунности этих функций является возрастающей. Более того, находится порядок роста (не меньше, чем 0{у/п)) этой последовательности (здесь п - это количество входов булевой функции. В разделе 2.3 исследуется влияние линейных переменных и полученный результат распространяется на введенные Таранниковым в [28] функции. В разделе 2.4 доказывается, что любая последовательность функций, получаемая при помощи конкатенации, имеет неубывающую последовательность порядков алгебраической иммунности, а также формулируются условия, при которых эта последовательность является невозрастающей. Более того, доказывается, что минимальная степень аннигилятора для функций, введенных Таранниковым в [29], степени п не меньше, чем O(v n). В разделе 2.5 тот же результат распространяется на конструкцию Пасалича-Майтры-Юхансона-Саркара ([24]). В разделе 2.6 приводятся некоторые результаты для одного класса бент-функций, также получающихся друг из друга по индукции (частного случая конструкции Ротхауза [25]). Наконец, в разделе 2.7 посчитанная в [22] оценка вероятности того, что данная функция от п переменных имеет аннигилятор порядка не более, чем d, распространяется с уравновешенных функций на произвольные функции.
Далее, в главе 3 вводится новое рекурсивное семейство функций, частными представителями которого являются рассматриваемые в главе 2 функции, предложенные Таранниковым [29] и (на основе его работы) Пасаличем-Май-трой-Карле-Юхансоном [24]. В разделе 3.1 даются предварительные сведения и основные понятия, необходимые для построения данного семейства. В разделе 3.2 дается метод его построения, а также показывается, что с точки зрения достижения максимальной корреляционной иммунности предложенные функции являются налучшими. В разделе 3.3 показывается, что для данного семейства конструкций справедливы основные результаты главы 2, т.е. нижние оценки на алгебраическую иммунность, полученные в разделах 2.2, 2.3 и 2.5. Напомним, что в литературе не встречается нижних оценок алгебраической иммунности ни для одной конструкции булевых функций, не говоря уже о семействе конструкций.
Результаты автора опубликованы в работах [1]-[6], а также в совместной работе [30].
