О свойствах корреляционно-иммунных функций с высокой нелинейностью

• Автор: Ботев, Антон Алексеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 79 с.

Многие потоковые шифры состоят из линейной части, порождающей последовательность с большим периодом, обычно состоящей из одного или нескольких регистров сдвига с линейной обратной связью (linear feedback shift registers, LFSR), и нелинейной комбинирующей функции /, которая порождает выходную последовательность по данным линейным входам. Исследования криптографической устойчивости таких шифров большей частью сводятся к исследованию нелинейной функции /, в частности, к исследованию этой функции с точки зрения того, удовлетворяет или не удовлетворяет она некоторым критериям, необходимым для того, чтоб успешно противостоять различным криптографическим атакам.
Для того, чтобы противостоять этим атакам (таким, как атакам Берлекэм-па-Мэсси, различным типам корреляционных и линейных атак [27, 20, 15] и алгебраической атаке (см. [16])), функция должна удовлетворять следующим критериям:
1. Уравновешенность. Булева функция должна выдавать нули и единицы с одинаковой вероятностью.
2. Хорошая корреляционная иммунность (порядка т). Выход булевой функции должен быть статистически независим от комбинации любых т ее входов. Уравновешенная корреляционно-иммунная порядка т булева функция называется т-устойчивой.
3. Хорошая нелинейность. Булева функция должна находиться на достаточно большом расстоянии от любой аффинной функции.
4. Высокая алгебраическая степень.
5. Высокая алгебраическая иммунность. Ни функция, ни ее дополнение не должно иметь аннигиляторов низкой степени.
Также важными критериями являются низкая автокорреляция, простая схемная реализация и т.д.
Критерии зачастую конфликтуют друг с другом, выяснению их взаимосвязей посвящена обширная литература.
В первой части данного исследования будут рассмотрены взаимосвязи между корреляционной иммунностью и нелинейностью для разных типов неуравновешенных булевых функций, во второй - будет исследоваться алгебраическая устойчивость различных видов функций, имеющих применение в криптографии. В третьей части будет предложена новая конструкция корреляционно-иммунных булевых функций, оптимальных по многим параметрам, при этом некоторые из известных конструкций являются частными случаями предлагаемой конструкции.
Наиболее общая ситуация в исследовании криптографических параметров такова: фиксируются параметры п (число переменных) и т (порядок корреляционной иммунности); при фиксированных п и т оптимизируются другие криптографически важные параметры. В частности, в работах [32], [26] и [28] независимо друг от друга доказано, что нелинейность п1(/) для фиксированных гг и ш не больше, чем 2"~1 — 2т (для уравновешенных функций п1(/) < 2"-1 — 2т+1). В работе Зенга и Занга [32] доказано, что если О.бп — 0.4 < т < п — 2, то п/(/) < 2"-1 — 2т+1. Далее показано (в работе [21]), что данная граница нелинейности может достигаться при юе2(У5+1)п + °(1ое2 П) < ш < п - 2, = 0.5902... Этот результат
является в настоящий момент рекордным.
В главе 1 настоящей работы получены следующие результаты.
В разделе 1.1 даются предварительные сведения и основные понятия. В разделе 1.2 исследуется возможность существования неуравновешенной корреляционно-иммунной функции с определенным набором спектральных характеристик (коэффициентов Уолша). В разделе 1.3 улучшается нижняя оценка Зенга и Занга ([32]) на т, при которых граница нелинейности 2"

не достигается. Теперь она составляет т > п + | log2 n+const, значение константы мы приводим далее точно. В разделе 1.4 исследован наиболее общий случай, когда х/(0) = 2т+г (mod 2m+l+1) при 1 < i < п — т — 1, включающий неуравновешенные функциии с нелинейностью 2"-1 — 2m+1. Показано, что для достаточно больших п такая нелинейность для неуравновешенных функций достигаться не может, потому что на т получена оценка т < + %pHog2n + О (г), значение O(i) мы далее раскрываем. Заметим,
что в работе Таранникова [29] доказывается, что данная верхняя оценка нелинейности 2"-1 — 2m+1 m-устойчивых булевых функций от п переменных достигается при О.бп — 1 < т < п —2. Поэтому при больших т максимальная нелинейность неуравновешенных корреляционно-иммунных функций порядка т меньше максимальной нелинейности m-устойчивых функций.
Таким образом, хотя верхняя оценка нелинейности 2п~1 — 2m+1 для неуравновешенных корреляционно-иммунных функций выше, чем для уравновешенных, мы видим, что при больших т большие значения нелинейности достигаются именно для уравновешенных функций.
Далее, в главе 2 рассматривается алгебраическая иммунность булевых функций. Алгебраическая иммунность - это способность противостоять разного рода алгебраическим атакам на регистры сдвига с линейной обратной связью (linear feedback shift registers, LFSR). Эти атаки впервые были предложены в [16]. Они раскрывают секретный ключ путем решения системы уравнений, зависящих от многих переменных. Данные системы уравнений описывают соотношения между битами ключа/состояния и выходными битами / (комбинирующей функции для LFSR). Если найдено такое соотношение низкой степени, алгебраические атаки очень эффективны ([17]).
В [16] показано, что указанные соотношения низкой степени и, соответственно, успешные алгебраические атаки существуют для некоторых хорошо известных шифров, которые иммунны по отношению ко всем другим
Для доказательства этой теоремы в аналоге формулы (2.16) для аннигиляторов <7»+з(г+1)-1,о и 5п+з(г+1)-1,о рассматриваются последовательно члены при 1Гзг_|_з, Ж32+4, 'Г,‘1/+3"ЦЧ/—4- ДЛЯ (?п+3(г+1) —1,1 ^ Яг, • 3(г -1) — 1.1 рассматриваются члены жзг+з, хзг+4, хзг+5, всё остальное аналогично;
Наконец, для доказательства самой теоремы 2.4 можно заметить, что при последовательном применении формул (2.30) - (2.31.1) при г > 1 в рп+з»-1,о содержится член Х0Хз . . . £3г(?*г-1,0 + 9п-1л) или х0х3... х3Ддп_цо + дп-1,0 в зависимости от четности г, а в дп+з»_1д содержатся члены хох3 ... жзДЕдп-1), а также х2х5 ... х3^2{дп-я + дп-1,1) или х2хъ ... х3^2(дп-цо + дп-1,1) (в зависимости от четности г), после чего рассуждения аналогичны тем, которые применялись для доказательства теоремы 2.2.
Таким образом, теорема 2.4 доказана. Следствием ее будет следующее:
Следствие 2.5. Для функций РМЛЭ порядок минимальной степени аннигилятора не может быть меньше, чем П(Дп), где п - количество входов. Другими словами, для этих функций верна оценка А1Д) = С1(Дп).
Доказательство. Из теоремы 2.5 следует, что после 1 + 2 + • • ■ + г = О (г2) итераций минимальная степень аннигилятора будет не меньшей, чем г. Поскольку при каждой итерации количество переменных увеличиваеся на 3, минимальная степень аннигилятора будет не меньше, чем ЩДп), где п -количество входов функции РМЛБ. Таким образом, утверждение следствия доказано.
Следствие 2.6. Для функций высокой нелинейности, предложенных в работе [24], верна оценка А1(/) = Q(v/n), где п - количество входов или степень многочлена функции.
Доказательство. Рассматриваемые функции есть конкатенация функций РМЛЯ, для которых утвеждение верно по следствию 2.5. По теореме 2.3 степень аннигилятора конкатенации функций не меньше максимума степеней