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

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

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

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

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

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

АппЦ) {де?п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) = {heFnf^h}. В 2004 г. в работе [МРС04] было введено понятие алгебраической иммунности булевой функции / е Тп. Значение алгебраической иммунности.

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

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

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

Заметим, что если мы имеем алгоритм вычисления базисов линейных пространств Ad (f) и Ad (ff1), то мы можем вычислить значение 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—wL 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).

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П), для функции /(х) = Тгп (а-х имеет место оценка А1(/) ^ 2л/га + 4.

— 4.

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

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

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

6^(2П), для числа т = 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.

Теорема 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) примет вид Я.

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

4) Нелинейные (по битам выходной последовательности) динамические соотношения. N > 0, функция д имеет вид g (x, y0,., yN)= 9и (х)-Уо° •••••уУ, wt («) 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), образует линейное пространствоnjv, 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.

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

• д (Ь^х),!(Ь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 при п —> оо. Найденные классы задаются в виде параметрических семейств трэйс представлений. [BaTFOo].

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 для фильтрующей функции fVG фильтрующего генератора 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 Singleand 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.