Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М В. ЛОМОНОСОВА

Факультет Вычислительной математики и кибернетики

Баев Владимир Валерьевич

Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций

Специальность 01.01 09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Москва-2008

003164559

Работа выполнена на кафедре математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета имени М В. Ломоносова.

Научный руководитель: кандидат физико-математических

наук, старший научный сотрудник Логачёв О А

Официальные оппоненты: доктор физико-математических наук,

профессор Гашков С.Б

Защита диссертации состоится 15 февраля 2008 года в 11:00 на заседании диссертационного совета Д 501 001.44 при Московском государственном университете им. M В Ломоносова по адресу. 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМиК МГУ. httpV/www cmc.msu ru в разделе «Наука» - «Работа диссертационных Советов» - «Д 501.001 44»

Автореферат разослан «_» января 2008 г.

Ученый секретарь диссертационного

кандидат физико-математических наук Ролдугин П В

Ведущая организация. Российский государственный

гуманитарный университет

совета профессор

Трифонов H П

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В теории конечных автоматов, теории кодирования и криптологии возникают задачи решения систем булевых уравнений, имеющих определённую структуру Как известно, задача решения произвольной системы полиномиальных булевых уравнений является ИР-трудной, и в настоящее время для решения таких систем не известно алгоритма, который бы имел сложность по порядку меньшую, чем

20(п)

, где п — число булевых переменных в системе Однако, для конкретных классов систем булевых уравнений иногда удаётся разработать более эффективные алгоритмы

Одним классом конечных автономных автоматов, [3], являются фильтрующие генераторы Они используются для генерации псевдослучайных последовательностей Непосредственным применением таких генераторов являются потоковые шифры, [1] Фильтрующий генератор выдает двоичную последовательность, зависящую от начального состояния (секретного ключа) При побитовом сложении этой последовательности с открытым текстом получается зашифрованное сообщение Функция выхода фильтрующего генератора называется также фильтрующей функцией

В 2003 г в работе [12] был предложен метод анализа фильтрующих генераторов (а также других классов псевдослучайных генераторов), основанный на понижении степени исходной совместной системы полиномиальных булевых уравнений относительно начального состояния генератора. Этот метод был назван авторами алгебраической атакой

Основным требованием для эффективного применения метода алгебраических атак является существование (по крайней мере, одной) ненулевой булевой функции д низкой степени (степени многочлена Жегалкина) в, которая является обнуляющим множителем либо для самой фильтрующей функции /, либо для её отрицания / + 1, то есть /д = 0 или (/ + 1)д = 0

Метод алгебраических атак позволяет (в некоторых случаях) по части выходной последовательности находить начальное состояние фильтрующего генератора за время 0(пЗЛ), где п — длина регистра состояния генератора (число булевых переменных фильтрующей функции /), а (1 — degg — степень обнуляющего множителя д (аннигилятора) функции / или / + 1

Таким образом, возникает задача поиска ненулевых аннигиляторов низкой степени для булевой функции выхода фильтрующего генератора В 2004 г в работе [18] был представлен алгоритм, находящий базис пространства аннигиляторов степени < й со сложностью

0(|зирр(/)| пМ) Булева функция / задается на входе этого алгоритма списком элементов множества яирр(/) = {х | ¡(х) = 1} — носителя функции / Затем, в 2006 г в работе [15] этот алгоритм был немного улучшен, но общая оценка сложности осталась прежней Одним из основных требований для двоичных псевдослучайных генераторов является равенство частот встречаемости 0 и 1 в выходной последовательности Это требование налагает на фильтрующую функцию условие уравновешенности, то есть вектор значений функции содержит одинаковое количество нулей и единиц, равное |зирр(/)| = 2П_1 Как видно, для таких функций алгоритм, предложенный в [18] имеет экспоненциальную (относительно числа переменных функции /) сложность Поэтому актуальна задача разработки более эффективных алгоритмов поиска низкостепенных аннигиляторов для функций, используемых в качестве фильтрующей, в том числе и для уравновешенных. Если при этом представлять функцию вектором значений или носителем, то экспоненциальной сложности избежать не удастся Значит, нужно использовать другие представления функции, желательно именно те, которые фигурируют в описании анализируемых генераторов

В той же работе [18] было введено понятие алгебраической иммунности булевой функции. Значение алгебраической иммунности А1{/) булевой функции / равно минимальному значению числа <1, для которого существует ненулевая булева функция д степени й такая, что /<7 = 0 или (/ + 1)<7 = 0 Значение алгебраической иммунности фильтрующей функции характеризует сложность применения метода алгебраических атак для анализа фильтрующего генератора

Метод алгебраических атак использует представления аннигиляторов фильтрующей функции в виде многочленов Жегалкина. При больших значениях алгебраической иммунности ненулевой аннигилятор наименьшей степени может иметь многочлен Жегалкина с очень большим количеством мономов, а значит, вычисление этого аннигилятора является очень трудоемкой алгоритмической задачей, даже если исходить только из размера ответа С другой стороны, применение аннигилятора высокой степени в методе алгебраических

атак будет неоправданно сложным, даже если многочлен Жегалкина этого аннигилятора содержит мало мономов То есть, неформально, отсутствие ненулевых аннигиляторов низкой степени у функций / и / +1 является показателем иммунности данного фильтрующего генератора к анализу методом алгебраических атак

Как было отмечено выше, в случае большого значения алгебраической иммунности функции / достаточно найти лишь само значение А1(/) либо как-то его оценить В работах [12] и [18] было доказано, что для любой булевой функции / от п переменных имеет место оценка А1(/) < \п/2|. В работах [18] и [14] было исследовано,

распределение значения алгебраической иммунности на множестве уравновешенных функций В частности в [14] доказано, что доля уравновешенных функций / от п переменных, для которых выполнены неравенства у — ^ 1п п < ^4/(/) < ^^, стремится к единице

при п —* оо. То есть алгебраическая иммунность почти всех уравновешенных булевых функций от п переменных имеет асимптотический порядок п / 2 — максимально возможный.

В 2005 и 2006 годах был опубликован ряд работ, [8], [13], [9], [7], в которых описываются конструкции классов булевых функций, имеющих максимальное значение алгебраической иммунности, равное \п/2\ В [2] доказано, что для конструкций последовательностей функций, построенных в работах [5] и [2], имеет место нижняя оценка их алгебраической иммунности вида

Задачи вычисления значения алгебраической иммунности и построения классов булевых функций, имеющих общие оценки алгебраической иммунности, активно исследуются специалистами по дискретным функциям и связаны, в основном, с разработкой и анализом потоковых шифров.

В 2003 г. в работе [11] был предложен метод быстрых алгебраических атак, являющийся усовершенствованием метода алгебраических атак. Он в ряде случаев работает эффективнее и предполагает существование более общего вида тождеств низкой степени, связывающих значения фильтрующей функции / и значения ее аргументов Метод быстрых алгебраических атак был в дальнейшем улучшен в работах [6] и [17] В работах [10] и [16] предложены алгоритмы поиска для фильтрующей функции / так называемых статических соотношений

/д = }г, ¿^д ^ е, Аеёк < 6

для малых значений чисел е < й Эти алгоритмы оперируют с табличными представлениями функций, и их сложность зависит линейно от 2я. В связи с этим возникает задача более эффективного поиска подобных тождеств для других способов представления функций

Цель диссертации. Первая цель работы состоит в разработке эффективных алгоритмов поиска ненулевых аннигиляторов (обнуляющих множителей) низкой степени для булевых функций. Алгоритмы должны работать с несколькими представлениями функций, подающихся на вход этих алгоритмов. Для каждого алгоритма должна быть получена оценка сложности.

Вторая цель диссертации состоит в разработке эффективных алгоритмов поиска для фильтрующей функции / тождеств низкой степени, обобщающих тождество ¡д — 0 и пригодных для использования в методе быстрых алгебраических атак

Третьей целью работы является описание новых классов булевых функций, для которых могут быть получены оценки (как верхние, так и нижние) алгебраической иммунности

Научная новизна. Результаты, полученные в диссертации, являются новыми Основные из них состоят в следующем 1 Исследована задача существования и нахождения аннигиляторов низкой степени для булевых функций Для поиска аннигиляторов низкой степени разработаны алгоритмы, которые оперируют со следующими представлениями входной булевой функции многочлен Жегалкина, ДНФ, трэйс представление ([4]), СФЭ и формула в базисе булевых операций конъюнкции, дизъюнкции и отрицания. Причем, для представления булевой функции в виде многочлена Жегалкина, ДНФ и трэйс представления разработанные алгоритмы вычисляют базис пространства аннигиляторов степени ^ с1 Доказано, что такая же алгоритмическая задача для представления булевой функции в виде КНФ (а также формулы и СФЭ) является ЫР-трудной. Для представления в виде СФЭ получен рекурсивный алгоритм, который находит базис некоторого подпространства аннигиляторов степени ^ й. Для каждого алгоритма получена полиномиальная верхняя оценка сложности Более того, все эти оценки зависят линейно от длины соответствующего представления булевой функции

2. Для поиска тождеств низкой степени, которым удовлетворяет булева функция выхода фильтрующего генератора, разработаны полиномиальные алгоритмы, на вход которым булева функция подается в виде многочлена Жегалкина или трэйс представления

3. Найдены некоторые классы булевых функций /, для которых получены асимптотики значения алгебраической иммунности AI(f) ~ 2Vñ при числе переменных п оо. Найденные классы задаются в виде параметрических семейств трэйс представлений

Методы исследования. В диссертации используются методы линейной алгебры, комбинаторики, теории множеств, алгебры многочленов и конечных полей, а также асимптотические методы математического анализа.

Теоретическая и практическая ценность. Работа носит теоретический характер. В ней представлен широкий набор эффективных алгоритмов вычисления алгебраических характеристик булевых функций, таких как пространство низкостепенных аннигиляторов и алгебраическая иммунность. Результаты диссертации могут быть использованы для дальнейшего развития теории булевых функций, поиска связей между различными представлениями булевых функций, а также при разработке и криптографическом анализе потоковых шифров

Апробация работы. Результаты диссертации докладывались на семинаре механико-математического факультета МГУ «Булевы функции в криптологии» под руководством О А. Логачёва и Ю.В Та-ранникова, на семинаре по теории кодирования Института проблем передачи информации РАН под руководством JIА Бассалыго, на 1-й и 2-й международных научных конференциях по проблемам безопасности и противодействия терроризму (2005, 2006, Москва), на VII международной конференции «Дискретные модели в теории управляющих систем» (2006, Покровское), на VI молодёжной научной школе по дискретной математике и ее приложениям (2007, Москва), на IX международном семинаре «Дискретная математика и ее приложения» (2007, Москва), на международной научной школе «Булевы функции в криптологии и информационной безопасности» (2007, Звенигород).

Публикации. Результаты диссертации опубликованы в 8 работах, две из которых — в рецензируемом журнале, входящем в список ВАК

Структура и объём работы. Диссертация состоит из введения, трех глав и списка литературы, включающего 53 наименования. Общий объём диссертации составляет 101 с границу

Во введении даются основные определения, делается краткий обзор работ, связанных с темой диссертации Излагаются основные результаты диссертации с указанием их дополняющего места в общей картине достижений в данной области исследования булевых функций. В конце введения приведен полный список основных результатов диссертации

Глава 1 посвящена алгоритмическим вопросам поиска аннигиляторов булевых функций. Эта глава имеет трехуровневую древовидную структуру разделов

В разделе 1.1 разработаны алгоритмы поиска аннигиляторов для различных способов представления булевых функций, подаваемых на вход этим алгоритмам

Введем обозначения. — поле из 2-х элементов. Тп — множество всех отображений ~> (множество всех булевых функций от п переменных) Для булевой функции / е Тп введём обозначение для линейного пространства её аннигиляторов степени ^ й.

МЛ ={9€?п\/9 = 0, ¿еёд < й) Введем обозначение для суммы биномиальных коэффициентов

Раздел 1.1.1 посвящен алгоритмам, работающим с представлением булевой функции в виде многочлена Жегалкина.

В разделе 1.1.1.1 предложен алгоритм AMI поиска базиса пространства На вход алгоритму подается многочлен Жегалкина функции / На выходе — многочлены Жегалкина базисных функций пространства Лг(/)- Оценка сложности алгоритма AMI — d 3

0(Mf(Sn) ), где Mf — длина многочлена Жегалкина функции /

(количество мономов) Алгоритм AMI составляет и решает однородную систему линейных уравнений, задающей пространство Ad(f) В разделе 1.1.1.2 получен явный вид этой системы.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В разделе 1.1.1.3 предложен алгоритм АМ1Б поиска базиса пространства

Ai,e(/) = {(9,h) е Т1 | fg = h, deg g ^ e, deg h ^ d}.

Как отмечалось выше, тождества вида fg = h при малых значениях степеней функций g и h используются в методе быстрых алгебраических атак. На вход алгоритму AMI Б подается многочлен Жегалкина функции /. На выходе — пары многочленов Жегалкина базиса пространства Ai,e(f) ■ Сложность алгоритма АМ1Б имеет оценку

0(Mf(SeJ).

В разделе 1.1.1.4 изложен приём, позволяющий для некоторых входных функций / существенно сократить вычисления. Результатом применения этого приёма к алгоритму AMI является алгоритм AMI 2, который, однако, имеет такую же 0614500 оценку сложности, что и алгоритм AMI

В разделе 1.1.2 предложен алгоритм АД1, получающий на входе ДНФ функции /. Он вычисляет многочлены Жегалкина базисных функций пространства Дг(/) за время 0(JDj(j5*)3), где Dj — количество элементарных конъюнкций в ДНФ, задающей функцию /. Также доказана следующая теорема.

Теорема 1.14. Для любых чисел n,d Eh таких, что 0 ^ d < п, задача вычисления базиса линейного пространства Ad(f) для функции /, заданной в виде КНФ, является NP-трудной

В разделе 1.1.3.1 предложены алгоритмы АФ1 и АС1, которые соответственно по формуле и схеме из функциональных элементов в базисе операций {->,&, V} находят многочлены Жегалкина базисов пары пространств G С Ad(f +1), II С Ad(f) Однако, при этом пространства G и Я могут оказаться тривиальными, в то время, как пространства Ad(f) и Mf +1) могут содержать ненулевые функции Аналогично теореме 1.14 доказывается, что задача вычисления базиса линейного пространства Ad(f) для функции /, заданной в виде формулы или СФЭ в базисе операций {—V}, является ЛГР-трудной Сложность алгоритмов АФ1 и АС1 — 0(Cy(S^)3), где Cj — длина

формулы или размер СФЭ, задающей функцию /.

В разделе 1.1.3.2 доказаны следующие две теоремы о пространствах аффинных аннигиляторов произведения булевых функций.

Теорема 1.16. Пусть 6 Тп — ненулевые функции степени ^ 1 (аффинные), причем /1^/2 и /1^/2+1 Тогда пространство А (Л /2) представгшо в виде прямой суммы

Л (Л Ь) = Ш)®АШ

Теорема 1.17. Пусть /1;/2 € ^ \ 0 Первые т переменных фиктивны для функции а остальные переменные фиктивны для функции ¡1 Тогда пространство А^^ /2) представимо в виде прямой суммы

Ш = Ш)®АШ

В разделе 1.1.3.3 доказана следующая теорема про структуру пространства Ад (/) для функции /, имеющей фиктивные переменные

Теорема 1.18. Пусть для некоторого к к ^ п переменные хг (к ^ г ^ п) фиктивны дня ненулевой функции / £ Тп Для каждого т £ {к — 1, , п} рассмотрим функцию /т 6 Тт, положив /т(хь ,хт) - }{хъ.. ,хт,0, ,0) В частности, / = /„ Мы будем

П—ТП

подразумевать вложения Д(/т) С Тт С Яод произведением Лг(/т_1) агт будем понимать множество произведений каждой функции из Д(/т_1) на «селекторную» функцию [(х1; 11и)нги] В указанных обозначениях пространство А^ (/) представгшо в виде следующей прямой суммы линейных пространств

Л(/) = Ф Лг-^(и)(Л-1)'

ГЧ Ти„

где — количество единиц в векторе и € К

п-к+1 „ „1

а х, — х,

х?=1

Раздел 1.1.4 посвящен алгоритмам, работающим с трэйс представлением булевой функции Поле Галуа СГ(2п) из 2п элементов является линейным пространством над полем Зафиксируем произвольный изоморфизм (р 6^(2") —> ¥2 линейных пространств над полем (р задаёт также отождествление функционального пространства Тп с пространством функций GF(2n) —Функции / € Тп взаимно однозначно соответствует функция /оу 2")->Г2.

Трэйс представление функции / GF(2п) —> F2 задаётся формулой следующего вида

f(x) = '¿Vrn(as хв), Ттп(х) = |>2\ a, G GF{2n)

s—0 к=О

Любую функцию / GF(2") —> GF(2n) можно представить единственным (интерполяционным) многочленом степени ^ 2" — 1 с коэффициентами из поля GF(2") Тот факт, что эта функция / принимает только значения из подполя F2 С GF(2П), задает некоторое условие на коэффициенты интерполяционного многочлена Фактически, такой многочлен также является трэйс представлением функции / GF(2n) —> F2.

В разделе 1.1.4.1 разработан алгоритм ATI, на вход которому подается трэйс представление булевой функции / Этот алгоритм вычисляет трэйс представления базисных функций пространства Ad(f) за время 0(Tj(nS^)3), где Tj — длина трэйс представления

функции / — количество ненулевых коэффициентов интерполяционного многочлена

В разделе 1.1.4.2 предложен алгоритм АТ1Б поиска базиса пространства Ade(f). На вход алгоритму ATI Б подается трэйс представление функции /. На выходе — пары трэйс представлений базиса пространства Ade(f). Сложность алгоритма ATI Б имеет оценку

0(Tf(nSeJ).

В разделе 1.1.4.3 разработан алгоритм АТК1, вычисляющий значение AI(f) для функции / е Тп, заданной трэйс представлением. Алгоритм АТК1 представляет собой итерационный процесс Сложность каждой итерации есть 0(n2TjSfL log(nTyS'f)), где Tj — длина трэйс представления функции /, а d = AI(f). Чем короче трэйс представление функции /, тем меньше итераций потребуется совершить алгоритму АТК1.

В разделе 1.1.4.4 проведён анализ фильтрующего генератора WG, который был представлен в 2005 г на конкурсе потоковых шифров eSTREAM в Интернете, [19]. Десятки ученых, занимающихся анализом потоковых шифров, публиковали на сайте конкурса свои статьи, в которых они анализировали ту или иную систему шифрования, представленную на этом конкурсе Было доказано, что генератор

WG обладает рядом хороших характеристик, но про значение алгебраической иммунности фильтрующей функции fWG Е авторами генератора высказывались только предположения и приводились некоторые оценки. Функция fWG задана трэйс представлением, длина которого равна Tf = 5 • 29 = 145. С помощью алгоритма АТК1

удалось вычислить значение AI(fWG) = deg fWG —11 Алгоритм совершил 6 итераций. На вычислительной машине с процессором IBM Power4 1,3 ГГц программе понадобилось около 2 ГБ оперативной памяти. Время работы программы составило 250 секунд («4 минуты)

В разделе 1.1.5 показано, что дают алгоритмы AMI и ATI для частично определённых функций / : \ 0 —> F2 выхода фильтрующего генератора. Для таких функций расширяется понятие аннигилятора: функция д Е Тп является аннигилятором функции /, если f(x)g(x) = 0 для любого ненулевого вектора х. В соответствии с этим определяется линейное пространство аннигиляторов степени

AKf) ■■= {9 е Fn 1 deg <7 iC d, f(x)g(x) = 0 Vs G F2" \ 0} Э Ad(f).

Получены некоторые достаточные условия равенства пространств А1(/) — Л*(/)- Причём эти условия легко вычислимы в процессе выполнения алгоритмов AMI и ATI. В частности, доказаны следующие утверждения.

Следствие 1.28. Пусть Mj — количество мономов в многочлене Жегалкина функции f Е Тп, и пусть имеет место неравенство Mfsdn < 2п Тогда A*d(f) = Ad(f)

Следствие 1.30. Ad(f) — Ad(f) для любой функции f Е Тп и любого числа d < п — deg /

Среди алгоритмов получения оценок алгебраической иммунности булевых функций мы выделим класс алгоритмов, которые предназначены для проверки тривиальности пространства Ad(f). Коротко будем называть их алгоритмами проверки. Эти алгоритмы выдают один из двух ответов. «Ad(f) = 0» или «неопределённость». Причём первый ответ выдаётся только в тех случаях, когда вычисления, проделанные алгоритмом проверки, доказывают тривиальность пространства Ad(f). В случаях, когда не удаётся это доказать, выдаётся второй ответ. Преимущество такого класса алгоритмов над описан-

ными выше алгоритмами вычисления базиса пространства Ad(f) заключается в том, что сложность алгоритмов проверки гораздо меньше. Недостатки же очевидны. Если Ad(f) ^ 0, то алгоритм проверки обязательно выдаст ответ «неопределенность» и не найдет ни одного ненулевого аннигилятора Более того, не всегда, когда пространство Ad(f) тривиально, алгоритм проверки может вычислительно это доказать Доля тех функций, для которых выдается первый ответ, характеризует качество алгоритма проверки

Алгоритм 1 из [15], предложенный в 2006 г, также относится к классу алгоритмов проверки тривиальности пространства Ad (/) для табличного представления функции / б Fn. Про этот детерминированный алгоритм была доказана следующая теорема.

Теорема ([15], Theorem 2). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных Тогда математическое ожидание времени работы алгоритма 1 для входной функции Fn можно оценить

0{nd), а вероятность того, что на выходе будет ответ «неопределенность» оценивается 0(е~2 n(1+0W)) В указанных оценках d считается константой, а асимптотика рассматривается при п —> оо

В разделе 1.2 предложены алгоритмы проверки АМ2 и АД2, являющиеся модификациями алгоритма 1 из [15] для представления входной функции в виде многочлена Жегалкина и в виде ДНФ соответственно Сложность этих двух алгоритмов есть 0{М ■ nd) при M, п —» оо, где M — количество мономов в многочлене Жегалкина (для алгоритма АМ2) или количество элементарных конъюнкций в ДНФ (для алгоритма АД2) Причем, в отличие от оценки сложности алгоритма 1 из [15] оценка сложности алгоритмов АМ2 и АД2 имеет место для каждой входной функции, размер представления которой равен M. Алгоритмы АМ2, АД2 и алгоритм 1 из [15] устроены так, что получая на вход соответствующие представления одной и той же булевой функции все 3 алгоритма выдают одинаковые ответы Это значит, что доля уравновешенных функций из Тп, для которых алгоритмы АМ2 и АД2 выдают ответ «неопределенность», также, как и

для алгоритма 1 из [15], оценивается 0(е~2 n(1+0W))

Глава 2 посвящена получению верхних и нижних оценок алгебраической иммунности некоторых классов булевых функций, заданных в виде трэйс представления

В разделе 2.1 доказаны следующие ключевые утверждения Следствие 2.9. Мп ^ 5,Уа £ \ 0, для функции

/(х) = Тгп(а х"1) имеет место оценка А1{/) ^ |2*<]п + 4| — 4

Следствие 2.11. В работе [20] было доказано, что А1(Тгп(х~1)) ^ + [п/1>/п]| — 2 для любого п^2 Объединяя этот результат со следствием 2.9, получаем асимптотику алгебраической иммунности следа от инверсии А1(Тгп(х~1)) ~ 2^/п при п оо

В разделах 2.2 и 2.3 дальше развивается техника получения нижних и верхних оценок алгебраической иммунности Доказаны следующие 4 теоремы

Теорема 2.12. У к £ N Зп0 : Уп ^ п0, ,ак_г £ {0,1} С Ъ,

Vа £ вР(2п) \ 0, для числа тп = 2п - 2к+1 + • 2г, для функ-

ции /(х) = Тгп(а • хт) имеет место оценка

AI(f) ^ mm

п

,[2VrT+T+5] - & - 6

+ 1,

к + 1(т) + 4

где I (т) — максимальное число последовательно стоящих единиц в наборе из к чисел 1 ,

Теорема 2.20. Ук £ N Эп0 Уп^ п0, для любых различных чисел Т7?1; ,тм £ N. которые удовлетворяют предикату

Уг£{ 1, ,М} Зо:Гд,.. ,ar k £ {0,1} тг = 2п - + ¿>г>г • 2'

г=1

для любых ai,.,aM£GF( 2")\0, для любой функции h б Тп deg/i ^ к, для произвольного изоморфизма tp GF(2n) —>• F2 , для функции } • GF(2n) —► F2, заданной формулой

f(x) = ■ хШг) + h о ip{x), имеет место оценка

AI(f) > mm

п

2& + 4

,[2-Jn + k + 5\-k-6

+ 1

Теорема 2.24. Для каждой пары чисел (п, к) и для каждой функции / (7^(2™) —> из условия теоремы 2.12 имеет место оценка

п

№

к—1

+ Е«*-1

1=1

Теорема 2.25. Для каждой пары чисел {п,к) и для каждой функции / СР(2п) —> П<2 из условия теоремы 2.20 имеет место оценка

Л/(/) ^ 1>/п] +

п

[>/п]

+ к- 2

Из этих 4-х теорем следует, что для всех рассмотренных в них последовательностей классов функций имеет место асимптотика значения алгебраической иммунности А1{/) ~ 2Лг при п —> оо к при этом считается константой

Глава 3 посвящена систематическому подходу к поиску низкостепенных тождеств, которым удовлетворяет фильтрующая функция и которые могут быть использованы в методе быстрых алгебраических атак при анализе фильтрующих генераторов, [11]

В разделе 3.1 даны необходимые определения и приведены вспомогательные утверждения

Для фильтрующего генератора с функцией выхода / € Тп изоморфизм (р СР(2п) —► называется специальным, если выходная последовательность этого генератора представляется в виде {/ о где а € 2") — некоторый элемент, азе 6^(2")

— начальное состояние генератора

Для фиксированной функции / е Тп и фиксированных чисел ЛГ, (1, е, г множество всех тождеств следующего вида

Кх)= £ 9и(х) П(¡офгх))и\

«=(«0, '=0 wt(u)^г

¿её(1г о (р*1) (I, deg(5ц о <р~1) ^ е Vи,

образует линейное пространство -Йлг,й,е,г(/) наД полем При малых значениях чисел N, (I, е, г такие тождества, называемые динамическими соотношениями, также могут быть эффективно использованы в методе быстрых алгебраических атак Нетрудно видеть, что динами-

ческие соотношения являются обобщением статических соотношений и в отличие от статических соотношений используют несколько последовательных значений выходной последовательности генератора, а именно N +1 значение.

В разделе 3.2 разработан алгоритм БААТ1, вычисляющий базис линейного пространства Д/уде,г(/) Для фильтрующей функции

/ G Тп На входе этот алгоритм получает числа N, d,e,r и трэйс представление функции fotp, где ip — специальный изоморфизм фильтрующего генератора На выходе — список трэйс представлений базисных наборов функций (h,gu j wt(u) ^ г). Время работы алгоритма Б A ATI ограничивается сверху некоторым многочленом от следующих трех параметров длины трэйс представления функции / и чисел п, N. При этом числа d, е, г считаются константами, от них зависит степень многочлена, ограничивающего время работы алгоритма БААТ1

Частным случаем динамических соотношений являются нелинейные рекуррентные соотношения на выходную последовательность {/ о <p{aks)}keN фильтрующего генератора

/ о ip(aNх) = g(f о ф°х), Jo ф^х)), Ух £ CF(2n),deg3 < г

Множество Rn r(f) функций g е Тп, удовлетворяющих этому тождеству (в случае, если R^r(f) не пусто) соответствует аффинному подпространству в линейном пространстве ftj\r,o,o,r(/)

В разделе 3.3 предложена модификация алгоритма БААТ1 — алгоритм РТ1, вычисляющий рекуррентные соотношения степени г На вход алгоритму РТ1 подаётся то же, что и алгоритму БААТ1 На выходе — многочлены Жегалкина функций, порождающих аффинное пространство RN r(f). Время работы алгоритма РТ1 также ограничивается сверху некоторым многочленом от длины трэйс представления функции / и чисел п, N. При этом г считается константой, от которой зависит степень ограничивающего многочлена

СПИСОК ЛИТЕРАТУРЫ

[1] Алферов А П, Зубов А Ю , Кузьмин А С , Черемушкин А В Основы криптографии. M издательство «Гелиос АРВ», 2001 г

[2] Ботев А А О свойствах корреляционно-иммунных функций с высокой нелинейностью, дис канд физ -мат наук, МГУ им М В Ломоносова, мех -мат фак М,2005

[3] Кудрявцев В Б , Алёшин С В , Подколзин А С Введение в теорию автоматов — М Наука, 1985

[4] Логачев О А , Сальников А А , Ященко В В Булевы функции в теории кодирования и криптологии ■— М МЦНМО, 2004

[5] Таранников Ю В О корреляционно-иммунных и устойчивых булевых функциях, Математические вопросы кибернетики, Вып 11 — М Физматлит, 2002,с 91-148

[6] Armknecht F Improving Fast Algebraic Attacks, Fast Software Encryption 2004, LNCS 3017, pp 65-82, Springer, 2004

[7] Armknecht F, Krause M Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity, International Conference on Automata, Languages and Programming, ICALP 2006, Part II, LNCS 4052, pp 180-191, Springer, 2006

[8] Braeken A, Preneel В On the Algebraic Immunity of Symmetric Boolean Functions, Indocrypt 2005, LNCS 3797, pp 35-48, Springer 2005

[9] Carlet С A method of construction of balanced functions with optimum algebraic immunity, Cryptology ePrint Archive, http //epnnt mcr org/2006/149

[10] Courtois N Cryptanalysis of SFINKS Information Security and Cryptology, ICISC 2005, LNCS 3935, pp 261-269, Sponger, 2005

[11] Courtois N Fast Algebraic Attacks on Stream Ciphers with Linear Feedback, Crypto 2003, LNCS 2729, pp 177-194, Springer, 2003

[12] Courtois N, Meier W Algebraic Attacks on Stream Ciphers with Linear Feedback, Eurocrypt 2003, LNCS 2656, pp 345-359, Springer, 2003

[13] Dalai D К, Maitra S Balanced Boolean Functions with (more than) Maximum Algebraic Immunity, Cryptology ePrint Archive Report 2006/434, http //epnnt mcr org/2006/434

[14] Didier F A new bound on the block error probability after decoding over the erasure channel, IEEE Trans on Information Theory, vol IT-52, No 10,2006

[15] Didier F , Tillich J -P Computing the Algebraic Immunity Efficiently, Fast Software Encryption 2006, LNCS 4047, pp 359-374, Springer, 2006

[16] Gong G On Existence and Invariant of Algebraic Attacks, CACR online archive, Technical report 2004-17,2004

http //www cacr math uwaterloo ca/techreports/2004/corr2004-17 pdf

[17] Hawkes P , Rose G Rewriting Variables the Complexity of Fast Algebraic Attacks on Stream Ciphers, Crypto 2004, LNCS 3152, pp 390-406, Springer, 2004

[18] Meier W, Pasalic E, Carlet С Algebraic Attacks and Decomposition of Boolean Functions, Eurocrypt 2004, LNCS 3027, pp 474-491, Springer, 2004

[19] Nawaz Y, Gong G The WG Stream Cipher, eSTREAM, ECRYPT Stream Cipher Project, Report 2005/033, 2005 http //www ecrypt eu org/stream/

[20] Nawaz Y , Gong G , Gupta К С Upper Bounds on Algebraic Immunity of Boolean Power Functions, Fast Software Encryption 2006, LNCS 4047, pp 375389, Springer, 2006

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[21] Баев В В Алгебраическая иммунность фильтрующей функции генератора Материалы IX Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 18-23 июня 2007 г) / Под редакцией О М Ка-сим-Заде — М Изд-во механико-математического факультета МГУ, 2007 стр 418-420

[22] Баев В В Некоторые нижние оценки на алгебраическую иммунность функций, заданных своими трэйс формами, Дискретные модели в теории управляющих систем VII Международная конференция, Покровское, 4-6 марта 2006 г. Труды — М МАКС Пресс, 2006 стр 25-29

[23] Баев В В О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций, ж Дискретная математика, том 18, выпуск 3, 2006 стр 138-151

[24] Баев В В О сложности поиска аннигиляторов низкой степени для булевых функций, Материалы международной научной конференции по проблемам безопасности и противодействия терроризму Интеллектуальный Центр МГУ 2-3 ноября 2005 г — М МЦНМО, 2006 стр 198-204

[25] Баев В В Рекуррентные соотношения на выходную последовательность фильтрующего генератора и их обобщения, Материалы второй международной научной конференции по проблемам безопасности и противодействия терроризму Московский государственный университет им МВ Ломоносова, 25-26 октября 2006 г — М МЦНМО, 2007 стр 249-254

[26] Баев В В Структура пространства аннигиляторов для булевых функций с фиктивными переменными, Материалы второй международной научной конференции по проблемам безопасности и противодействия терроризму Московский государственный университет им МВ Ломоносова, 25-26 октября

2006 г — М МЦНМО, 2007 стр 255-258

[27] Баев В В Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина, ж Дискретная математика, том 19, выпуск 4, 2007 стр. 132-138

[28] Баев В В Эффективная проверка нижней границы алгебраической иммунности многочлена Жегалкина и ДНФ, Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля

2007 г) Часть I Под редакцией А В Чашкина 2007 стр 8-12

Подписано в печать 24 12 2007 Формат 60x88 1/16. Объем 1 25 п л Тираж 75 экз Заказ № 687 Отпечатано в ООО «Соцветие красок» 119992 г Москва, Ленинские горы, д 1 Главное здание МГУ, к А-102

Введение

Основные результаты диссертации

Глава 1. Алгоритмические вопросы поиска аннигиляторов булевых функций

1.1 Поиск аннигиляторов для различных способов представления булевой функции

1.1.1 Для представления функции в виде многочлена Жегалкина

1.1.1.1 Алгоритм АМ1 поиска базиса пространства аннигиляторов

1.1.1.2 Явный вид системы уравнений, задающей аннигиляторы

1.1.1.3 Алгоритм АМ 1Б поиска статических соотношений для быстрых алгебраических атак

1.1.1.4 Один способ улучшения алгоритма АМ 1 — алгоритм

1.1.2 Для представления функции в виде ДНФ

1.1.3 Для представления функции в виде формулы или схемы из функциональных элементов

1.1.3.1 Алгоритмы АФ1 и АС 1 поиска аннигиляторов

1.1.3.2 Дополнение: О линейных аннигиляторах произведения булевых функций

1.1.3.3 Дополнение: Структура пространства аннигиляторов для булевых функций с фиктивными переменными

1.1.4 Для представления функции в виде трэйс представления

1.1.4.1 Алгоритм АТ1 поиска базиса пространства аннигиляторов

1.1.4.2 Алгоритм АТ1Б поиска статических соотношений для быстрых алгебраических атак

1.1.4.3 Модификация алгоритма АТ1Б, ориентированная на короткое трэйс представление входной функции

1.1.4.4 Алгебраическая иммунность фильтрующей функции генератора

1.1.5 О поиске аннигиляторов для частично определённых функций

1.2 Алгоритмы проверки отсутствия ненулевых аннигиляторов

1.2.1 Проверка отсутствия ненулевых аннигиляторов низкой степени у многочлена Жегалкина

1.2.1.1 Основной вариант алгоритма АМ

1.2.1.2 Возможные пути модификации алгоритма АМ

1.2.2 Проверка отсутствия ненулевых аннигиляторов низкой степени у ДНФ

Глава 2. Нижние и верхние оценки алгебраической иммунности булевых функций, заданных трэйс представлением

2.1 Алгебраическая иммунность линейных функций от инверсии

2.2 Нижние оценки алгебраической иммунности более широких классов функций

2.3 Верхние оценки алгебраической иммунности более широких классов функций

Глава 3. Исследование метода быстрых алгебраических атак (Б А А)

3.1 Предварительные сведения

3.2 Полиномиальный алгоритм получения тождеств для метода БАА по трэйс представлению функции

3.3 Полиномиальный алгоритм получения нелинейных рекуррентных соотношений для фильтрующего генератора по трэйс представлению фильтрующей функции

3.4 Явное выражение для минимальной линейной комбинации предварительного шага метода БАА

В теории конечных автоматов, теории кодирования и криптологии возникают задачи изучения и решения систем булевых уравнений. Как известно, задача решения произвольной системы полиномиальных булевых уравнений является ЫР-трудной (см. [0182]), и в настоящее время для решения таких систем не известно алгоритма, который бы имел сложность по порядку меньшую, чем , где п — число булевых переменных в системе. Но поскольку в теории ИР-полных задач сложность оценивается «в худшем случае», то можно ставить задачи разработки более эффективных алгоритмов для конкретных классов систем булевых уравнений.

Анализ некоторых конечных автономных автоматов (см. [КАР85]) в ряде случаев сводится к исследованию систем булевых уравнений, описывающих функционирование этих автоматов и поэтому имеющих определённую структуру.

Основным предметом исследования данной диссертации является показатель алгебраической иммунности булевой функции и связанное с ним понятие аннигилятора (обнуляющего множителя) булевой функции. Знание аннигилятора низкой степени для функции выхода конечного автомата иногда позволяет повысить эффективность решения системы полиномиальных булевых уравнений, описывающих функционирование этого автомата.

В диссертации разработан ряд алгоритмов поиска аннигиляторов низкой степени, получены оценки их сложности. Также разработан комбинаторный метод получения нижних оценок алгебраической иммунности. С помощью этого метода получены оценки для функций из некоторых классов. Для этих же классов получены верхние оценки, имеющие ту же асимптотику что и нижние оценки при количестве переменных функций стремящемся к бесконечности.

Введём обозначения. ¥2 — поле из двух элементов. Тп — множество всех отображений —> F2 (множество всех булевых функций от п переменных). Функция д € Тп называется аннигилятором функции / € Тп, если / • <? = 0. Множество всех аннигиляторов функции / обозначим

АппЦ) {де?п\1-д = 0}.

Мы будем использовать стандартное отношение частичного порядка " ^" на множестве Тп. Для пары функций /,д еТп ^ 9(х) Чх е

Понятие аннигилятора тесно связано с этим отношением. А именно, если в следующей цепочке эквивалентных утверждений д ^ Н & д = Нд & д(Н + 1) = О подставить / вместо д, то получим, что 1 еАппЦ), (0.1) а если подставить / вместо h, то получим, что g^f&geAnn(f + l). (0.2)

Будем обозначать deg / — степень булевой функции / € Тп — степень её многочлена Жегалкина (см. [Yabl03]). При этом считаем degO = 0. Введём обозначения для линейного пространства аннигиляторов степени ^ d: Ad(f) ■= 4?(Я {де?п\1д = 0, degg ^ dj с Ann(f).

Верхний индекс п в обозначении этого пространства будем указывать, когда нам будет нужно явно акцентировать внимание на пространстве Тп, в котором мы рассматриваем аннигиляторы.

Множество {0} мы для краткости будем также обозначать 0, но только в тех случаях, когда контекст допускает единственную трактовку. Например, «F2ra \ 0» и «Ad(f) = 0».

Одним классом конечных автономных автоматов являются фильтрующие генераторы. Фильтрующий генератор (ФГ) состоит из двоичного регистра сдвига длины п с линейной обратной связью и фильтрующей булевой функции / £ Тп. На г -м шаге функционирования на выход фильтрующего генератора выдаётся значение f(Lls), где s € F2n — начальное состояние регистра, a L : F^ —» F^ — линейное преобразование регистра, совершаемое на каждом шаге.

Фильтрующие генераторы используются в качестве генераторов псевдослучайных двоичных последовательностей, в частности, в потоковых шифрах (см. также [AZKCH], [MOV]).

В 2003 г. в работе [СМ03] был предложен метод анализа фильтрующих генераторов (а также других типов псевдослучайных генераторов), основанный на понижении степени исходной совместной системы полиномиальных булевых уравнений относительно начального состояния генератора. Этот метод был назван авторами алгебраической атакой (АА).

Введём следующее обозначение для суммы биномиальных коэффициентов:

Метод АА позволяет (в некоторых случаях) по части выходной последовательности находить начальное состояние регистра фильтрующего

1 о генератора за время 0((5„) ), [СМОЗ].

Основным требованием для эффективного применения метода АА является существование булевой функции д низкой степени, ограничивающей фильтрующую функцию / сверху или снизу. В силу (0.1) и (0.2) д должна принадлежать либо линейному пространству

Апп(/ + 1) = {деГп\д^П, либо аффинному пространству i + Ann(f) = {heFn\f^h}. В 2004 г. в работе [МРС04] было введено понятие алгебраической иммунности булевой функции / е Тп. Значение алгебраической иммунности

AI(f) равно минимальному значению числа d, для которого существует ненулевая булева функция д 6 Тп степени d такая, что fg = 0 или (/ +1)<? = 0. Формально можно записать так:

AI(f) := min{d | Ad(f) * 0 или Ad(f +1) * 0}.

Таким образом, для анализа ряда псевдослучайных генераторов двоичных последовательностей стали нужны методы эффективного поиска аннигиляторов наименьшей степени d для фильтрующей функции / (в случае, когда AI(f) мало) либо поиска значения AI(f), если оно достаточно велико. Основная часть диссертации посвящена этому вопросу.

Заметим, что если мы имеем алгоритм вычисления базисов линейных пространств Ad(f) и Ad(f -f1), то мы можем вычислить значение A 1(f). А именно, мы можем последовательно перебирать все значения d ^ 0 и вычислять базисы пространств Ad(f) и Ad(f +1) до тех пор, пока мы не получим хотя бы одно ненулевое пространство. Вычисление же базиса одного конкретного пространства Ad(f) может дать нам оценку значения AI(f): если оказалось, что Ad(f) ^ 0, то это означает, что AI(f) ^ d.

В [МРС04] приведена следующая теорема, являющаяся модификацией теоремы 6.0.1 из [СМ03].

Теорема ([МРС04], Theorem 6.0.1). Для любой функции / е Fn существует ненулевая функция такая, что deg д ^ \п/2] и deg(fg) ^ [п/2].

Из этой теоремы следует, что AI(f)^\n/ 2] для любой функции

Для дальнейшего изложения нам понадобятся следующие обозначения. Для подмножества А С Тп положим mindeg(i4) := minjdeg/ | / € А]. Носителем функции / G Тп называется множество supp(/) := {о: е F2n | f(x) = 1}. Весом функции / 6 Тп называется мощность её носителя wt(/) := |supp(/)|.

Функция / € j называется уравновешенной, если wt(/) = 2n1. Множество функций степени ^ d будем обозначать

1Z(d,n) {f efn\ deg f^d}.

В [А04Е] минимальная степень аннигилятора булевой функции / оценивается через вес функции /. А именно, доказаны следующие 2 теоремы.

Теорема ([А04Е], Corollary 1). Если для функции / € Тп и числа d Е {0,.,п} выполнено неравенство S% > wt(/), то mindeg(Ann(f)) ^ d.

Теорема ([А04Е], Corollary 2). Если для функции f е Fn и числа d <Е {0,.,га} выполнено неравенство wt(/) > (2d — l)2n~d, то mindeg(Ann(f)) > d.

В 2004 г. в [МРС04] были доказаны следующие 2 теоремы о распределении значения алгебраической иммунности на множестве уравновешенных булевых функций.

Теорема ([МРС04], Theorem 3). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Рассмотрим произвольную последовательность {dn}n€N натуральных чисел такую, что dn ^ рп, где

In 2

0.22

Тогда существует предел вероятности того, что А1{Рп) ^ dn:

Р{А1(Рп) ^ dn} 0, при п —> оо.

Теорема ([МРС04], Theorem 4). Зафиксируем числа п и d такие, что О ^ d ^ п. Количество функций веса w из 7Z(d,п) обозначим € 1l(d,n)\wt(f) = w}\. Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда имеет место следующая оценка вероятности того, что AI(Fn) ^ d:

P{AI(Fn)^d}^ £ w=2n~d

2n—w -L 4 я \ ' 2" in—1

-¡n-d+1

2in- Е А»

W=1 n—d

2 я2n~d

2?j-i2n~d

2n r,Tl—1

Следующая теорема является переформулировкой теоремы 2 из [D05] в терминах двух предыдущих теорем.

Теорема ([D05], Theorem 2). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда для любого действительного числа а из интервала (0; 2 In 2) существует следующий предел вероятности.

Р{1< А1(Рп) < Щ - 1, при П - 00.

То есть алгебраическая иммунность почти всех уравновешенных булевых функций от п переменных имеет асимптотический порядок п/2 — максимально возможный.

Предыдущие теоремы дают некоторое представление о функции А1 Ъ и о распределении значения минимальной степени аннигилятора на множестве Тп. Они в рамках своей выразительности характеризуют свойство алгебраической иммунности сразу для группы функций. Другая сторона исследования этого свойства — алгоритмический подход, разработка алгоритмов вычисления функции А1 и поиска аннигиляторов низкой степени для заданной функции. То есть, когда мы хотим (имея один или несколько алгоритмов) находить аннигиляторы или алгебраическую иммунность для одной конкретной функции, а не для широкого класса.

Далее при описании алгоритмов в качестве модели вычислителя мы будем использовать ИАМ-машину (однопроцессорную машину с прямым доступом к памяти). То есть время получения доступа к ячейке памяти по её номеру ограничено сверху некоторой константой. Подразумеваем также, что алгоритм получает некоторые данные конечной длины в алфавите {0,1} на вход и выполняет некоторую последовательность базовых операций в зависимости от входных данных, формируя при этом выходные данные. Ответом алгоритма будем называть набор выходных данных, сформировавшихся после останова алгоритма. Базовыми операциями мы будем называть битовые операции и операцию получения значения из ячейки памяти по номеру этой ячейки. Считаем, что время работы алгоритма пропорционально количеству проделанных им базовых операций. Под сложностью алгоритма будем понимать функцию времени работы алгоритма, зависящую от входных данных этого алгоритма.

Впервые в работе [МРС04] были представлены 2 алгоритма (алгоритм 1 и алгоритм 2), получающих на вход число й и вектор (таблицу) значений функции / 6 Тп на всех 2п векторах пространства Ж2П. Алгоритм 1 вычисляет базис пространства за время • (в^)2). Для некоторых уравновешенных функций с количеством переменных п > 20 время работы этого алгоритма очень велико. Алгоритм 2 вероятностный. Он выдаёт базис некоторого линейного пространства С Тп, содержащего в себе пространство аннигиляторов А^). Если получилось, что = то это значит, что и А^}) = 0. Если же 0, то ничего более определённого, чем С утверждать нельзя. В частности, остаётся неизвестным, тривиально ли пространство Сложность этого

I л алгоритма оценивается 0((Sn) ), что расширяет область его применимости по сравнению с первым алгоритмом.

Алгоритм 2 из [DT06] является небольшой модификацией алгоритма 1 из [МРС04]. Новый алгоритм позволяет для некоторых функций существенно сократить вычисления за счёт использования некоторой информации о решаемой системе линейных уравнений. Общая оценка сложности осталась та же 0(wt(/) • (Sn)2).

Все упомянутые алгоритмы из работ [МРС04] и [DT06] работают с табличным представлением функции /, а их сложность пропорциональна весу функции. Это значит, что, в частности, для уравновешенных функций / € Тп эти алгоритмы будут иметь экспоненциальную от п сложность. В связи с этим замечанием возникает задача разработки алгоритмов поиска аннигиляторов для других способов представления функции /.

В главе 1 данной диссертации разработаны алгоритмы поиска аннигиляторов из пространства Ad(f) для некоторых способов представления функции /, отличных от табличного. Часть алгоритмов универсальны, т.е. для любой функции на входе они выдают базис пространства Ad(f), а другая часть алгоритмов для некоторых функций может выдать неопределённый ответ или базис некоторого подпространства Н С Ad(f). На вход каждому алгоритму из 1-й главы подаются числа п и d, а также булева функция / 6 Тп, заданная в виде некоторого представления.

В разделе 1.1.1.1 предложен алгоритм AMI поиска базиса пространства Ad(f). На вход алгоритму подаётся многочлен Жегалкина функции /. На выходе — многочлены Жегалкина базисных функций пространства Ad(f). Оценка сложности алгоритма AMI — где

Мj — длина многочлена Жегалкина функции / (количество мономов). В

разделе 1.1.1.4 изложен приём, позволяющий для некоторых функций существенно сократить вычисления. Результатом применения этого приёма к алгоритму AMI является алгоритм АМ12. В разделе 1.1.5 рассказано, что даёт алгоритм AMI для частично определённых функций / : F^ \ 0 —> F2.

В разделе 1.1.2 предложен алгоритм АД1, получающий на входе дизъюнктивную нормальную форму (ДНФ, см. [Yabl03]) функции /. Он вычисляет многочлены Жегалкина базисных функций пространства Ad(f) за

J Q время 0(Df(Sn) ), где Df — количество элементарных конъюнкций в ДНФ, задающей функцию /. Также доказана следующая теорема.

Теорема 1.14. Для любых чисел n,d£ N таких, что O^d^n, задача вычисления базиса линейного пространства Ad(f) для функции f £ Тп, заданной в виде конъюнктивной нормальной формы (КНФ, см. [Yabl03]), является NP-трудной.

В разделе 1.1.3.1 предложены алгоритмы АФ1 и АС1, которые по формуле либо схеме из функциональных элементов (СФЭ, см. [УаЫОЗ]) в базисе операций {-!,&;,V} находят многочлены Жегалкина базисов пары пространств в,Н С Причём (? С +1), Яс^(/). Однако, при этом пространства (? и Я могут оказаться тривиальными, в то время, как пространства и ^(/ + 1) могут содержать ненулевые функции.

Аналогично теореме 1.14 доказывается, что задача вычисления базиса линейного пространства для функции $ заданной в виде формулы или СФЭ в базисе операций {->,&,\/}, является ММрудной. о

Сложность алгоритмов АФ1 и АС1 — 0(С^{8п) ), где Су —длина формулы или размер СФЭ, задающей функцию /. В разделе 1.1.3.3 доказана следующая теорема про структуру пространства Дг(/) для функции /, имеющей фиктивные переменные.

Теорема 1.18. Пусть для некоторого к : к ^п переменные х^ (к ^ г ^ п) фиктивны для ненулевой функции / £ Тп. То есть

УС*!,.,**!) € Щак,.,ап),(Ьк,.,Ъп) е хъ.,хкьак,.,ап) = ¡(хъ.,хкъЬк,.,Ьп).

Для каждого т £ {к — 1,.,п} рассмотрим функцию /т € Тт, положив ¡т(хь.,хт):= ¡(хь.,хт,0,.,0). В частности, / = /п. Мы будем п-т подразумевать вложения Дт(/т) С Тт С Тп. Под произведением А^-1(/т-1)' хт будем понимать множество произведений каждой функции из Л™1(/т-1) на «селекторную» функцию [(х^.,хт) н-» хт]. В указанных обозначениях пространство АЦ(/) представимо в виде следующей прямой суммы линейных пространств:

Ш= © , ч=(иь.,и„)еГГШ: в4+1 wt(u)<íí где wt(и) —количество единиц в векторе и € а щ, Щ = 1 щ

V :=

1, щ = 0.

В разделе 1.1.4.1 предложен алгоритм ATI, на вход которому подаётся трэйс представление (ТП) функции /. Определение трэйс представления будет дано в разделе 1.1.4. Этот алгоритм вычисляет трэйс представления

А *} базисных функций пространства Ad{J) за время 0(Tf(nS„] ), где Tf — длина ТП функции /. В разделе 1.1.5 рассказано, что даёт алгоритм ATI для частично определённых функций / : F2n \ 0 F2.

Отметим, что все рассмотренные представления (носитель, многочлен, ДНФ, ТП) булевых функций, для которых построены полиномиальные алгоритмы, не сводятся полиномиально друг к другу. Это значит, что ни один из соответствующих алгоритмов (алгоритм 1 из [МРС04], АМ12, АД1, ATI) вычисления базиса пространства Ad(f) не является лишним, каждый ориентирован на своё представление функции /.

Среди алгоритмов получения оценок алгебраической иммунности булевых функций выделяется группа алгоритмов, которые предназначены для проверки тривиальности пространства Ad(f). Коротко будем называть их алгоритмами проверки. Эти алгоритмы выдают один из двух ответов: «Ad(f) = О» или «неопределённость». Первый ответ выдаётся только в тех случаях, когда вычисления, проделанные алгоритмом проверки, доказывают тривиальность пространства Ad(f). В случаях, когда не удаётся это доказать, выдаётся второй ответ. Преимущество такого класса алгоритмов над универсальными алгоритмами, описанными выше, заключается в том, что их сложность гораздо меньше. Недостатки же очевидны. Если Ad(f)^ 0, то алгоритм проверки обязательно выдаст ответ «неопределённость» и не найдёт ни одного ненулевого аннигилятора (в этом случае можно применить один из упомянутых ранее алгоритмов поиска аннигиляторов). Более того, не всегда, когда пространство Ad(f) тривиально, алгоритм проверки может вычислительно это доказать. Доля тех функций, для которых выдаётся первый ответ, характеризует качество алгоритма проверки. Алгоритмы 1 и 2 из [МРС04], о которых было рассказано выше, как раз являются примером пары (универсальный алгоритм, алгоритм проверки).

Алгоритм 1 из [DT06], предложенный в 2006 г., также относится к классу алгоритмов проверки тривиальности пространства Ad(f) для табличного представления функции / G Fn. Про этот детерминированный алгоритм была доказана следующая теорема.

Теорема ([DT06], Theorem 2). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда математическое ожидание времени работы алгоритма 1 для входной функции Fn можно оценить 0(п ), а вероятность того, что на выходе будет ответ «неопределённость» оценивается указанных оценках d считается константой, а асимптотика рассматривается при n —> со. (Для сравнения, время работы алгоритма 2 из [MPC 04] оценивается 0{{Sdnf) = 0(пЫ).)

В разделе 1.2 предложены алгоритмы проверки АМ2 и АД2, являющиеся модификациями алгоритма 1 из [DT06] для представления входной функции в виде многочлена Жегалкина и в виде ДНФ соответственно. Сложность этих двух алгоритмов есть 0(M-nd) при М, п —> оо, где М — количество мономов в многочлене Жегалкина (для алгоритма АМ2) или количество элементарных конъюнкций в ДНФ (для алгоритма АД2). Причём, в отличие от оценки сложности алгоритма 1 из [DT06] оценка сложности алгоритмов АМ2 и АД2 имеет место для каждой входной функции, размер представления которой равен М. Получая на вход соответствующие представления одной и той же булевой функции, алгоритмы АМ2 и АД2, а также алгоритм 1 из [DT06] всегда выдают одинаковые ответы. Это значит, что доля уравновешенных функций из Тп, для которых алгоритмы АМ2 и АД2 выдают ответ «неопределённость», также оценивается 0(е'2 n(1+0W)).

Кроме алгоритмического поиска аннигиляторов и значения алгебраической иммунности булевой функции особенный интерес представляют:

1. получение верхних и нижних оценок значения алгебраической иммунности для различных классов булевых функций,

2. соотношение алгебраической иммунности булевой функции с другими её характеристиками, которые также важны при анализе ФГ.

В работе [ВР05] приводится алгоритм вычисления алгебраической иммунности симметричных булевых функций. Описываются классы симметричных булевых функций из которые имеют максимальное значение алгебраической иммунности, равное \п / 2|.

В работах [DMS05], [DGM05], [QFL05], [DM06], [С06], [АК06], [LQ06] приводятся различные конструкции классов булевых функций, на которых также достигается максимум значения алгебраической иммунности.

В [BotDis] доказано, что для последовательностей функций, построенных с помощью ряда конструкций из [Т02], имеет место нижняя оценка их алгебраической иммунности вида ii(Vn), где п — количество переменных в этих функциях. Кроме того, в [BotDis] приводится новое семейство функций, алгебраическая иммунность которых также оценивается снизу fi(Vn).

Глава 2 данной диссертации посвящена получению верхних и нижних оценок алгебраической иммунности некоторых классов булевых функций, заданных в виде трэйс представления.

Поле GF(2n) (поле Галуа из 2п элементов, [LSYa], [LN88]) является линейным пространством над полем F2. Зафиксируем произвольный изоморфизм </7: —» Р2П линейных пространств над полем ?2. Ниже мы будем его регулярно использовать. <р задаёт также отождествление Тп с пространством функций С?^(2П) —» Функции / € Тп соответствует функция / о <р: вР(2п) .

Для функции / : 2П) Р2 и числа й е {1,.,п} обозначим := {у : ^(2В) | / • </ = О, о у,"1) < 6}.

Алгебраическая иммунность функции / : 6^(2п) —>■ Р2 определяется так же, как для булевой функции:

Л/(Я := тт{<* I * 0 или 4,(/ +1) * 0}.

Легко проверить, что и Л/(/) не зависят от выбора изоморфизма <р.

Функция абсолютного следа Тгп : С^(2П) —»Р2 определяется равенством п—1 к=0

В разделе 2.1 доказано следующее утверждение

Следствие 2.9. Уп ^ 5,\/о € С^(2П)\0, для функции /(х) = Тгп(а-х имеет место оценка А1(/) ^ 2л/га + 4

-4.

В работе [N0006] было доказано, что Л/(Тгп(ж-1)) ^ [>/п] + [п/[>/п]] —2 для любого п^2. Объединяя этот результат со следствием 2.9, получаем асимптотику алгебраической иммунности следа от инверсии: Л/(Ггп(ж-1)) ~ 2>/п при п —> оо.

В разделах 2.2 и 2.3 развивается техника получения нижних и верхних оценок алгебраической иммунности. Доказаны следующие 4 теоремы.

Теорема 2.12. Ук е N Зп0 : Уп ^ п0, Уа!,.,«^ € {0,1} С й, Уа €

6^(2П)\0, для числа т = 2п -2к+1 + ^^«г2^ ^ функции ¡(х) = Тгп(а ■ хт) имеет место оценка

А1Ц) > шш п

27^+1+5

-к-6 1, к + I (ш) + 4 где I (т) — максимальное число последовательно стоящих единиц в наборе из к чисел: Х,^,.,^^.

Теорема 2.20. У& € N Зп0 : Уп ^ п0, для любых различных чисел тъ.,тм £ 5П, которые удовлетворяют предикату

Уг € {1 Заф.,аг>к в {0,1} С Ъ : тг

2" -2*+Ч2\ г=1 для любых аъ.,ам € \ 0, для любой функции \ degЛ ^ к, для функции / : —заданной формулой м х) = ^Тгп(аг.хтг) + Ноф), г=1 имеет место оценка

А1(./) ^ пип тг

2£ + 4

2л/п+Т+~5) - А; - б 1.

Теорема 2.24. Для каждой пары чисел (п,к) м для каждой функции / : 2П) —> из условия теоремы 2.12 имеет место оценка п

А1Ц) ^ [>/п| +

1^1

А-1 г=1

Теорема 2.25. Для каждой пары чисел (щк) и для каждой функции / : 6^(2п) —> из условия теоремы 2.20 имеет место оценка п

Л/(/) ^ + Л-2.

Из этих 4-х теорем следует, что для всех рассмотренных в них последовательностей классов функций имеет место асимптотика значения алгебраической иммунности: А1(})~24п при п—>оо. к при этом считается константой.

Вернёмся к обсуждению методов анализа фильтрующих генераторов. В 2003 г. в работе [СОЗ] был предложен метод быстрых алгебраических атак (БАА), являющийся усовершенствованием метода АА. Он в ряде случаев эффективнее и предполагает существование более общего вида соотношений низкой степени, связывающих значения фильтрующей функции / и значения её аргументов. А именно, для применения метода БАА нужно знать тождества следующего вида.

Н(х) = д(х,/(1?х),0х),.,/(1нх)), \/х е Е?. (0.3)

При этом требуется, чтобы по вектору у Е можно было легко вычислить коэффициенты многочлена Жегалкина функции х д(х, у).

Функция И может быть задана многочленом Жегалкина. Однако, в [НЯ04] предложен приём, позволяющий при применении метода БАА вообще не использовать функцию /г — достаточно знать, что её степень не превосходит некоторого известного числа с?.

Говоря о тождествах вида (0.3) для БАА, будем полагать, что d = deg h, а степень функции д : F2n —> F2 по первым п булевым аргументам равна е. На числа d,e накладывается ограничение d ^ е.

Если известно хотя бы одно тождество (0.3) для малых значений чисел d и е, то метод БАА позволяет (в некоторых случаях) находить начальное состояние s фильтрующего генератора по сплошному куску некоторой длины Т выходной последовательности {f(Lls) •

В работе [СОЗ] приведены примеры анализа методом БАА генераторов, используемых в поточных шифрах LILI-128, Toyocrypt, Е0. Эти шифры подробно описаны в [SDGMO], [MI02], [ВТ01]. Позднее, в 2005 г. в работе [С05] метод БАА был использован для анализа поточного шифра SFINKS, [BLMPV].

Глава 3 данной диссертации посвящена систематическому подходу к поиску тождеств (0.3) для ФГ и некоторым деталям применения метода БАА.

Рассмотрим некоторые частные случаи тождеств (0.3).

1) Аннигилятор функции /. N = 0,h = 0,g(x,у) = g'(x)-y. Тождество (0.3) примет вид f(x)gXx) = 0 Уж в F2n, deg g'^e. Для такого тождества метод БАА не имеет преимуществ над методом АА.

2) Статические соотношения. N = 0. Тождество (0.3) примет вид h{x) = g(x,f(x)) = 9i(x)f(x) + g0(x). Поскольку deg#o = deg h, то считаем, что <70 = 0. Итого, для N = 0 нас интересуют пары функций g, h <Е Тп, для которых fg = h, degg ^ е, deg/г < d. (0.4)

Такие тождества были получены различными способами для генераторов, используемых в поточных шифрах LILI-128, Toyocrypt, SFINKS в работах [СОЗ] и [С05].

Алгоритмы АМ1Б и АТ1Б поиска тождеств (0.4) предложены в разделах 1.1.1.3 и 1.1.4.2 соответственно. Функция / на входах этих двух алгоритмов задаётся многочленом Жегалкина и трэйс представлением соответственно. Для этих представлений функции / алгоритмы поиска тождеств (0.3) похожи на алгоритмы поиска аннигиляторов и имеют такие же оценки сложности — 0(Mf -(5J)3) и 0(Tf ■ (nS^f) соответственно, где My — количество мономов в многочлене Жегалкина функции /, a Tf — длина ТП функции /.

3) Линейные (по битам выходной последовательности) динамические соотношения. N > 0. д(х,у) = (д(х),у) = ^ д^х) • у{. Тождество (0.3) примет вид Я

Кх) = 9í (?)f{L%x), deg дг ^ е, deg h^d. i=0

4) Нелинейные (по битам выходной последовательности) динамические соотношения. N > 0, функция д имеет вид g(x,y0,.,yN)= 9и(х)-Уо° •••••уУ, wt(«)<r (0.5) z€F2n, yo,-,VN eF2> Vw.

В работах [A02] и [AK03] для поточного шифра Е0 путём кропотливого анализа были найдены тождества (0.3) для d = 4, е = 3, г = 2, N = 3 и функций д вида (0.5).

Для фиксированных n,f,N,d,e,r множество всех пар функций (д,/г) таких, что

• функция д имеет вид (0.5),

• deg h^d,

• выполняется тождество (0.3), образует линейное пространство -ñjv,d,e,r(/) надполем F2.

В разделе 3.2 предложен алгоритм БААТ1, вычисляющий базис линейного пространства #лгде,г(/)- На входе этот алгоритм получает числа

N, d,e,r и ТП функции / 6 Тп для специального изоморфизма (р : GF(2n) —► F^, зависящего от линейного преобразования L регистра сдвига (о значении отождествления ср было рассказано выше). Пусть характеристический многочлен матрицы L примитивен (см. [LN88]), и а е GF(2n) — его корень (а — собственное число матрицы L). Изоморфизм ip выбирается так, чтобы выполнялось тождество

Lx = <р{а ■ <р~\х)) Vx G F2n. (0.6)

В разделе 3.1 конструктивно доказано существование такого изоморфизма. Более общее утверждение доказано в [GEN].

Время работы алгоритма БААТ1 ограничивается сверху некоторым многочленом от следующих трёх параметров: длины ТП функции / и чисел щ N. При этом числа d, е, г считаются константами (от них зависит степень многочлена, ограничивающего время работы алгоритма БААТ1).

5) Рекуррентные соотношения степени г на выходную последовательность фильтрующего генератора. h = 0, N > 0, д(х,у) = yN - д(Уо,.,Уя-1)- Тождество (0.3) примет вид f(LNx) = g(f(L°x),^f(LN-lx)), deg^r. (0.7)

Множество R^^if) функций д, удовлетворяющих тождеству (0.7), (в случае, если RNr(f) не пусто) соответствует аффинному подпространству в линейном пространстве -fyv,o,o,r(/)- В разделе 3.3 предложена модификация алгоритма БААТ1 — алгоритм РТ1, вычисляющий для последовательности {/(Lls)}2€N все рекуррентные соотношения вида (0.7). На вход алгоритму РТ1 подаётся то же, что и алгоритму БААТ1. На выходе будет набор функций дь.,дм, порождающий аффинное пространство RN^r(f). Выход будет пустым в случае, если не существует функций д степени ^ г, удовлетворяющих тождеству (0.7). Время работы алгоритма РТ1 также ограничивается сверху некоторым многочленом от длины ТП функции / и чисел n,N. При этом г считается константой, от которой зависит степень ограничивающего многочлена.

Оценка практической применимости алгоритмов БААТ1 и РТ1 неоднозначна. Соответствующие замечания приводятся в конце раздела 3.3.

Теперь вкратце опишем 3 основных шага метода БАА, обозначенных в

С03].

1. Поиск одного из тождеств вида (0.3) для малых значений d и е.

2. Предварительный шаг (precomputation step). Цель этого шага заключается в отыскании какого-нибудь вектора а = (aQ,.,aT) 6 F2 как можно меньшей размерности, для которого выполняется тождество Т

Oil • h{lJx) = 0 Vz<EF2n. (0.8) г=0

Найдя такой вектор, мы получаем тождество

• д(Ь\^х),!(Ь1+1х),.^(Ь{+мх)) = 0. (0.9) г=0

3. Подстановочный шаг (substitution step). Подставляем имеющиеся значения элементов выходной последовательности bi = f(Lls) для

Q^i^T + N + K в тождество (0.9), заменяя х на LJs. В результате получаем систему полиномиальных булевых уравнений степени ^ е относительно битов начального состояния s: т g(Li+Js,bi+j,bi+j+b.,bi+j+N) = О, О < J < Я. (0.10) .¿=0

Эта система решается методом линеаризации (см. [С03], [СМОЗ]).

В 2004 г. в работе [А041] был предложен вариант предварительного шага, допускающий распараллеливание. В работе [НИ04] было предложено

С"* II использовать "универсальную" линейную комбинацию ае¥2п на предварительном шаге. Под универсальностью имеется в виду то, что для этой линейной комбинации а тождество (0.8) будет выполняться для любой функции Л е Щй, п). Компоненты универсальной линейной комбинации являются коэффициентами следующего многочлена р^(Х) £ (7^(2П)[Х].

2"-1

Х) := ¿>Дг'П

0 г=0: где ^(г) — количество единиц в двоичной записи числа г, а а € (?^(2П) — корень примитивного характеристического многочлена матрицы Ь. В работе

1 з су

НЯ04] показано, как получить а за время 0(5^(1(^,5^) ), а также как, используя быстрое преобразование Фурье над полем 2П), снизить сложность подстановочного шага (без решения системы (0.10)) с <9(6^ до \ogSn) для некоторого класса тождеств (0.3).

В разделе 3.4 получено явное выражение для минимальной линейной комбинации, используемой на предварительном шаге метода БАА. А именно, пусть отождествление СР(2п) <-»■ Е2П задаётся специальным изоморфизмом (р, для которого выполняется (0.6). И при этом функция к: (3^(2") —> ¥2 задана многочленом над полем 2п):

2я) \ О, Ркс{ 0,1,.,2П-2}.

Тогда коэффициенты минимальной линейной комбинации для предварительного шага являются коэффициентами следующего многочлена, который мы будем называть минимальным многочленом для предварительного шага.

Х,(Х)=1[(Х-а{).

Если на предварительном шаге мы найдём линейную комбинацию а такую, что сИ^^^с^ -Ь(Ьгх)^ ^ е, то вместо системы (0.10) мы получим такую систему булевых уравнений относительно начального состояния

• т т

Причём степень всех этих уравнений также не превосходит числа е. При такой модификации предварительного шага минимальный многочлен примет вид

XA,eW= П Я-*')' iePh: wt(г)>е

В 2005 г. на открытом конкурсе поточных шифров eSTREAM был представлен фильтрующий генератор WG, [NG05]. Десятки учёных, занимающихся анализом поточных шифров1, публиковали на сайте конкурса свои статьи, в которых они анализировали ту или иную систему шифрования, представленную на этом конкурсе. В частности, про генератор WG его авторами было доказано, что выходная последовательность этого генератора обладает рядом хороших характеристик (большой период, высокая линейная сложность, одинаковость частот встречаемости наборов из нулей и единиц длины ^11, один хороший автокорреляционный показатель), но про значение алгебраической иммунности фильтрующей функции fWQ € Тп высказывались только предположения и приводились некоторые оценки. Функция fwQ задаётся трэйс представлением.

Вплоть до середины 2007 года никто так и не смог предложить действенного метода вычисления значения AI(fWG). Все разработанные ранее алгоритмы (в том числе и алгоритмы ATI и ATI Б из разделов 1.1.4.1 и 1.1.4.2 соответственно) требуют слишком много памяти (терабайты) и времени для вычисления AI(fWo).

В разделе 1.1.4.3 предложен алгоритм АТК1, позволяющий за приемлемое время вычислять значение алгебраической иммунности AI(f) функции f & заданной коротким ТП. Алгоритм АТК1 представляет собой итерационный процесс. Сложность каждой итерации есть

0/7 /1 где Tf — количество следов в ТП функции /, а d = AI(f). Количество итераций мало при малых значениях Tj. Количество следов в ТП функции fWQ равно Tf = 5. При реализации алгоритма АТК1 на вычислительной машине с процессором IBM Power4 1,3 ГГц для вычисления значения AI(Jwq) понадобилось всего 6 итераций. Программе потребовалось около 2 ГБ оперативной памяти. Время работы программы составило 250 секунд. Результат работы программы показал, что Al(fwc) = desfwG =П.

С помощью алгоритма АТК1 можно также находить для фильтрующего генератора статические соотношения (0.4), используемые в методе БАА. Для генератора WG было найдено 20 линейно независимых тождеств вида (0.4) для неконстантной функции д, для d = И и е = 8. Среди этих 20-ти тождеств есть 2 тождества с deg д = 5 и 17 тождеств с deg д = 6.

1 Основным компонентом поточного шифра является псевдослучайный генератор, который генерирует выходную последовательность, зависящую от начального состояния (значения секретного ключа).

Основные результаты диссертации

1. Разработаны алгоритмы поиска аннигиляторов степени < d булевых функций / б Тп, представленных на входе алгоритма в виде

• многочлена Жегалкина (алгоритмы AMI, АМ12, [BaDMl], [BalPM]),

• ДНФ (алгоритм АД 1, [ВаМВ5]),

• формулы или СФЭ в базисе булевых операций {—V} (алгоритмы АФ1, АС1, [ВаМВ5]),

• трэйс представления (алгоритм ATI, [BaTF06]).

Алгоритмы AMI, АМ12, АД1, ATI находят базис всего пространства Ad(f), а алгоритмы АФ1 и АС1 — лишь базис некоторого подпространства Н С Ad(f). Для алгоритма ATI получена оценка сложности вида

J о

0(Mj -(nSn) ), а для всех остальных алгоритмов получены оценки их

1 о сложности вида 0(Mj -(Sn) ), где Mj — длина соответствующего представления функции /.

2. Доказано, что задача вычисления базиса линейного пространства Ad(f) для функции / G Тп, заданной в виде КНФ, формулы или СФЭ в базисе операций {->,&,V}, является ММрудной. [ВаМВ5]

3. Разработаны алгоритмы поиска базиса пространства

А*,е(/) ••= i(9,h) 6 Tl | fg = h, degg ^ е, deg^ ^ d} для представления булевой функции / € Тп на входе алгоритма в виде

• многочлена Жегалкина (алгоритм АМ1Б, [BaDMl]),

• трэйс представления (алгоритм ATI Б).

Алгоритмы АМ1Б и АТ1Б имеют сложность 0{Mf-{Senf) и 0{Mf-(nSenf) соответственно, где Mj — длина соответствующего представления функции

4. Разработаны алгоритмы проверки тривиальности пространства Ad(f) для представления булевой функции / £ Тп на входе алгоритма в виде

• многочлена Жегалкина (алгоритм АМ2),

• ДНФ (алгоритм АД2).

Алгоритмы АМ2 и АД2 выдают один из двух ответов: «Ad(f) = 0» или «неопределённость». Первый ответ выдаётся только в тех случаях, когда пространство Ad(f) тривиально. Доказано, что доля уравновешенных функций / € Тп, для которых алгоритмы АМ2 и АД2 выдают второй ответ, оценивается Разработанные алгоритмы имеют сложность

0(Mf-nd), где My — размер соответствующего представления функции / G r Указанные оценки О(-) рассматриваются при п,Му —> оо. При этом d считается константой. [BalPM]

5. Получено выражение линейного пространства A$(fn) через линейные пространства Af(fk) для 1 ^ г < d, где к <п, и булева функция fn G Тп получается из функции fk G добавлением фиктивных переменных ^Jfc+l»—[ВаМВбр]

6. Найдены некоторые классы булевых функций / G Тп, для которых получены асимптотики значения алгебраической иммунности AI(f) ~ 2Vn при п —> оо. Найденные классы задаются в виде параметрических семейств трэйс представлений. [BaTFOô]

7. Разработан полиномиальный алгоритм БААТ1, который по специальному трэйс представлению функции / G ^ вычисляет некоторые тождества низкой степени, которым удовлетворяет функция /. Эти тождества используются в методе быстрых алгебраических атак, применяемом для анализа фильтрующих генераторов. [ВаМВб]

8. Разработан полиномиальный алгоритм РТ1, который находит рекуррентные соотношения на выходную последовательность фильтрующего генератора. На вход алгоритму РТ1 подаётся специальное трэйс представление фильтрующей функции / G Тп. [ВаМВб]

9. Получено явное выражение для минимальной линейной комбинации, которая используется на предварительном шаге метода быстрых алгебраических атак. [ВаМВб]

10. Разработан алгоритм АТК1, который позволяет вычислять значение AI(f) для функции / G Тп, заданной трэйс представлением. Алгоритм АТК1 представляет собой итерационный процесс. Сложность каждой итерации есть 0{n2TjSfl loginTjSfj), где Tj — длина трэйс представления функции /, а d = AI(f). Алгоритм АТК1 эффективнее алгоритма ATI для функций с коротким трэйс представлением. С помощью алгоритма АТК1 удалось вычислить значение AI(fWG) = degfWG = 11 для фильтрующей функции f\VG фильтрующего генератора WG, который был представлен на конкурсе поточных шифров eSTREAM в Интернете. [BaDMA7]

1. Баев В.В.: О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций, ж. Дискретная математика, том 18, выпуск 3,2006. стр. 138-

2. Баев В.В.: О сложности поиска аннигиляторов низкой степени для булевых функций. Материалы международной научной конференции по проблемам безопасности и противодействия терроризму. Интеллектуальный Центр МГУ. 2-3 ноября 2005 г. М: МЦНМО, 2006. стр. 198-

3. Ботев А.Д.: О свойствах корреляционно-иммунных функций с высокой нелинейностью, дис. канд. физ.-мат. наук, МГУ им. М.В. Ломоносова, мех.-мат. фак. М., 2005 Глухов М.М., Елизаров В.П., Нечаев А.А.: Алгебра, Учебник для студентов вузов: в 2-х т. М.: Гелиос АРВ, 2

4. Гэри М., Джонсон Д.: Вычислительные труднорешаемые задачи М.: Мир, 1

5. Кнут Д.: Искусство программирования Сортировка и поиск. М.: Мир, 1978. для машины и [BotDis] [GEN] [GJ82] [К78] ЭВМ. Т. 3.: [КАР85] Кудрявцев В.Б., Алёшин В., Подколзин А. С Введение

6. Лидл Р., Нидеррайтер Г.: Конечные поля, в 2-х т. М.: Мир, 1

7. Логачёв О. А., Сальников А. А., Ященко В. В.: Булевы функции в теории кодирования и криптологии М.: МЦНМО, 2

8. Таранников Ю. В.: О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002, с. 91-

9. Яблонский В.: Введение

10. Учеб. [LN88] [LSYa] [Т02] [УаЬЮЗ] [А02] Armknecht А Linearization Attack on the Bluetooth Key Stream Generator, Cryptology ePrint Archive: Report 2002/191, http://eprint.iacr.Org/2002/l 91 Armknecht F.: Improving Fast Algebraic Attacks, Fast Encryption 2004, LNCS 3017, pp. 65-82, Springer, 2004 98 Software [A04I]

11. Armknecht F., Krause M.: Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity, International Conference on Automata, Languages and Programming, ICALP 2006, Part II, LNCS 4052, pp. 180-191, Springer, 2

12. Blahut R.: Transform techniques for error control codes, IBM J. Res. Dev.,vol 23, pp. 299-315,1

13. Braeken A., Preneel В.: On the Algebraic Immunity of Symmetric Boolean Functions, Indocrypt 2005, LNCS 3797, pp. 35-48, Springer 2

14. Carlet C A method of construction of balanced functions with optimum algebraic immunity, Cryptology ePrint Archive: Report 2006/149, http://eprint.iacr.org/2006/149 Courtois N.: Cryptanalysis of SFINKS. Information Security and Cryptology, ICISC 2005, LNCS 3935, pp. 261-269, Springer, 2

15. Courtois N.: Fast Algebraic Attach on Stream Ciphers with Linear Feedback, Crypto 2003, LNCS 2729, pp. 177-194, Springer, 2003 Courtois N.: The security of Hidden Field Equations (HFE), Cryptographers Track at RSA Conference 2001, LNCS 2020, pp. 266-281, Springer, 2001. 99 [AK03] [AK06] [B179] [BTOl] [BLMPV] [BLP06] [BP05] [C06] [C05] [C03] [COl]

16. Dalai D.K., Gupta K.C., Maitra S.: Results on algebraic immunity for cryptographically significant Boolean functions., Indocrypt 2004, LNCS 3348, pp. 92-106, Springer, 2

17. Didier F., Tillich J.-P.: Computing the Algebraic Immunity Efficiently, Fast Software Encryption 2006, LNCS 4047, pp. 359-374, Springer, 2

18. Hawkes P., Rose G.: Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers, Crypto 2004, LNCS 3152, pp. 390-406, Springer, 2004 [DGM04] [DM06] [DMS05] [D05] [DT06] [HR04] 100

19. Zhang X.M., Pieprzyk J., Zheng Y.: On Algebraic Immunity and Annihilators, International Conference on Information Security and Cryptology ICISC 2006, LNCS 4296, pp. 65-80, Springer, 2006. [LQ06] [MPC04] [MOV] [MI02] [M97] [NG05] [ISfGG06] [QFL05] [SDGMO] [ZPZ06] 101