Combinatorics-algebraic models in cryptography.pdf 1. Математические основыХарактерной чертой современной криптологии (как любого научного направления,предназначенного для решения практических задач, определяемых современнымсостоянием технических средств) является использование широкого спектра, частонедостаточно проработанных именно с позиции решения задач криптологии, моделейи методов из различных разделов математики. К ним относятся классические разделыматематики со своей сложившейся тематикой исследований (комбинаторный анализ,теория булевых функций, теория автоматов, теория алгоритмов, конечные алгебраическиесистемы), а также формируемые в настоящее время разделы математики (теорияквантовых алгоритмов, теория хаоса динамических систем, теория фракталов).Именно широкий спектр недостаточно теоретически проработанных с позициикриптологии, часто плохо сравнимых друг с другом моделей и методов приводит ктому, что одним из основных методов анализа криптографических алгоритмов являетсястатистический анализ их качества. Упущения, допускаемые при этом, в совокупностис интенсивным развитием средств вычислительной техники являются основнойпричиной достаточно частого пересмотра криптографических стандартов во всеммире. Осознание этой ситуации и стимулировало разработку математических основсовременной криптологии. Цель настоящего раздела - попытка охарактеризовать дескриптивные,метрические и алгоритмичесие аспекты комбинаторно-алгебраическихмоделей и методов, предназначенных для решения задач современной криптологии,систематически изложенные в [1].1.1. Буле вы функцииВ течение последних 20 лет наблюдается интенсивное развитие теории булевыхфункций, обусловленное именно исследованием проблем, связанных с криптологией.Математический анализ этих достижений, основанный на моделях и методах современнойконечной алгебры, комбинаторного анализа и теории вероятностей, систематическипредставлен в [2].Изложенные в [2] методы исследования криптографических примитивов могутбыть эффективно применены на практике (безусловно, с использованием компьютеров)для анализа булевых вектор-функцийf : En ^ Em (n, m G N),гдеE = {0,1},при относительно небольших значениях числа 2n m. Существование эффективныхметодов «хорошей» декомпозиции (с точки зрения криптографии) графиков булевыхвектор-функций f : En ^ Em при больших значениях чисел n и m вызывает сомнение.Тем не менее представленные в [2] методы исследования булевых функций имеютогромное методологическое значение прежде всего потому, что они устанавливаютнетривиальные глубокие внутренние связи между теорией булевых функций и современнойалгеброй. Сказанное может быть проиллюстрировано следующим образом.При исследовании свойств булевой вектор-функции всегда можно перейти к булевойвектор-функции f : En ^ Em, сохраняющей константу нуль. Для этого достаточнозаменить исходную булеву вектор-функцию g(x) булевой вектор-функциейf(x) = g (x) 0 g (0).Обозначим график такой булевой вектор-функции f через graph(f), а множество всехмаксимальных по включению подпространств линейного пространства En+m, содержащихсяво множестве graph(f), обозначим через Lin(graph(f)). В [3] показано, чтоимеет место равенствоgraph(f) = У V. (1)V€Lin(graph(f))Следовательно, синтез булевой вектор-функции, обладающей заданными свойствами,по своей сути, сводится к построению множества Lin(graph(f)) с соответствующимихарактеристиками.Отметим, что представление булевой вектор-функции, сохраняющей константунуль, в виде системы полиномов Жегалкина также основано на использовании подпространствлинейного пространства En+m. Однако такое представление по своейструктуре значительно сложнее, чем представление (1), так как построение полиномаЖегалкина, фактически, представляет собой вариант применения метода включения-исключения. Отсюда вытекает, что любые методы построения системы полиномов Же-галкина для булевых вектор-функций, обладающих заданными значениями криптографическихпримитивов, заведомо требуют учета нетривиальных соотношений междуподпространствами пространства En+m, а также нетривиальных свойств преобразованийпространства En+m.По-видимому, одной из наиболее значимых для анализа и синтеза блочных шифровявляется парадигма управляемой подстановочной операции (УПО), для представлениякоторой используется язык схемных реализаций, основанный на использованиикомбинаторно-алгебраических конструкций. Попытка систематического исследованияэтой парадигмы предпринята в [4].Соответствующая математическая модель представляет собой такую булевувектор-функциюf : En+m ^ E1 ( m,n,1 G N; I ^ n),представленную в виде f : En х Em ^ E1, т. е. в видеy = f(x, v) (x Е En, v Е Em),что для каждого v0 Е Em инъекцией является вектор-функция gv0 : En ^ E1, определяемаяравенствомgvo (x) = f(x, vo) (x Е En).Вектор x Е En - информационный, а вектор v Е Em - управляющий. При этом управляющийвектор формируется из сеансового ключа.Специальным случаем УПО является блок управляемых перестановок (БУП), характеризуемыйтем, что:1) l = n;2) для каждого фиксированного v0 Е Em вектор-функция gVo представляет собойперестановку компонент информационного вектора;3) если v0 = v 1 (v0, v 1 Е Em), то gV0 и gV1 -различные перестановки компонентинформационного вектора.Для основных типов БУП и УПО в [4] исследованы эффективность и сложностьсхемных реализаций, принципы синтеза схем с заданными алгебраическимии вероятностно-статистическими свойствами, а также принципы, эффективность исложность криптоанализа этих схем.Тем не менее в настоящее время остается много нерешенных задач, связанных с анализоми синтезом как БУП и УПО, так и шифров, основанных на использовании этихпарадигм.Во-первых, задачи обнаружения и локализации неисправности схем, применяемыхпри построении шифров, остаются вне поля зрения криптографов (криптоаналитик,имея активный доступ к некоторым входам или выходам элементов таких схем, можетуспешно имитировать их неисправность, что существенно усложнит работу легальногопользователя). Ясно, что эти задачи могут быть решены стандартными методамитехнической диагностики. Однако такие тесты будут значительно сложнее, чем оптимальныетесты, так как они не учитывают существенные характеристики соответствующихсхем (в частности, свойство БУП и УПО «быть инъекцией при фиксированномуправляющем векторе»). В [1] показано, что для основных типов БУП сложность такихтестов является полиномом не более третьей степени от сложности БУП. В этихтестах используется «бегущая единица» или «бегущий нуль». Поэтому криптоаналитик,даже имея только пассивный доступ к выходам некоторых элементов этих схем(т. е. производя пассивный эксперимент), может идентифицировать соответствующиеподстановки или фрагменты ключа методами, отличными от линейного криптоанализа.Отсюда вытекает ряд нерешенных задач анализа вычислительнойстойкости иустойчивости блочных шифров в условиях, когда криптоаналитик имеет доступ к входамили выходам УПО, на основе которых построен исследуемый шифр.Во-вторых, наличие дешифратора в матричном БУП предполагает реализациюкаждой из используемых перестановок в явном виде. Это обстоятельство существенноусложняет схемную реализацию БУП. Если же убрать дешифратор, то мы получимпредставление используемого семейства перестановок в неявном виде (что существенноупрощает схемную реализацию и усложняет криптоанализ), а именно в видеS = [1Г о - - - о fmm N Е E (г = 1 ,.. .,m ) } ,где f 1 = fi (i = 1,... , m) -заданная в явном виде перестановка, f 0 (i = 1,... , m) -тождественная перестановка, а о - операция суперпозиции. При этом возникает ряднерешенных задач, связанных с выбором порождающих перестановок / 1,... , /m, обеспечивающихзаданные алгебраические и вероятностно-статистические свойства семействаS.1.2. Ко не ч ные а в т ома тыОсознание значимости теории конечных автоматов для математического анализаинъективных дискретных преобразователей информации относится к третьей четвертиХХ века [5-7]. Эти и аналогичные им исследования оперировали с абстрактнымавтоматом, т. е. модельюA = (Q,X,Y,8,A),где Q,X, Y - соответственно конечные множество состояний, входной и выходной алфавиты;8 : Q х X ^ Q - функция переходов; а A : Q х X ^ Y - функция выходов.Так как на практике эффективно могут быть использованы абстрактные автоматытолько при относительно небольших значениях числа |Q| |X|, то результаты исследованийтаких автоматов не оказали существенного влияния на разработку поточныхшифров.Высокая сложность решения задач анализа и синтеза для абстрактных автоматов(а также сетей, построенных из них) стимулировала исследование достаточно узкихклассов автоматов, для которых решение этих задач существенно проще. К такимклассам относится класс линейных автоматов над полем GF(pk) (p - простое число,k G N). Систематический анализ этого класса автоматов с позиции классической теориисистем представлен в [8, 9]. Однако эти исследования практически ничего не далидля решения задач криптологии, так как в них не рассматривались задачи исследованиявычислительной стойкости поточных шифров, построенных на основе такихавтоматов. Такие задачи, по своей сути, сводятся к задачам идентификации параметрическинастраиваемых автоматов и к задачам теории экспериментов с автоматаминад конечными полями. Этот пробел частично ликвидирован в [10-12].Исследованная в [13] связка (посредством обратной связи)операционный автомат - управляющий автоматявляется теоретической основой возможности успешного применения конечных автоматовв процессе построения управляющих систем. При таком подходе естественновозникает проблема синтеза автомата по его внешнему поведению. Эта проблема являетсяодной из центральных проблем теории конечных автоматов. В [14] выделеныследующие четыре подхода приближенногопостроения (по своей сути, идентификации)конечного автомата по его внешнему поведению.Первый подход к построению модели автомата основан на том, что на множествевсех автоматов с одним и тем же входным и выходным алфавитами вводится функцияблизости, использующая расстояние Хемминга между выходными словами. Предполагается,что задано число состояний искомого автомата. Функция близости применяетсяв процессе поиска наилучшего приближения искомого автомата во множестве всехавтоматов с меньшим числом состояний. Известно, что эта задача решена для классаперестановочных автоматов, которые находят широкое применение в современнойкриптографии.При втором подходе к построению модели автомата также предполагается, чтозадано число состояний искомого автомата. Построение модели A = (Q,X, Y, 8, A) искомогоавтомата основано на построении его статистического аналога, т. е. такогоавтомата A' = (Q,X, Y, 5', Л'), что для любого состояния q Е Q вероятности событий5(q,x) = 5'(q,x) (x Е X )иЛ(q,x) = X(q,x) (x Е X )больше соответственно величин |Q|-1 и |Y|-1.При третьем подходе к построению модели автомата предполагается, что имеетсядискретный преобразователь, являющийся черным ящиком, обеспечивающий приидеальных условиях требуемое поведение. Из-за отсутствия идеальных условий (шумы,воздействия внешней среды и т. д.) поведение дискретного преобразователя можетотличаться от эталонного поведения. Построение модели автомата основано напостроении его следствия, т. е. автомата, на который поступает входная и выходнаяпоследовательности исследуемого дискретного преобразователя и который, на основеповедения эталона на подмножестве входных слов фиксированной длины, корректируетвыход дискретного преобразователя.Четвертый подход к построению модели искомого автомата основан на полученииследствий из соотношений, описывающих его функционирование. Для абстрактныхавтоматов такие следствия получаются в терминах обобщенных гомоморфизмов автоматови построении обобщенного образа автомата (т. е., по сути, некоторого классаавтоматов). Обобщение понятия гомоморфизма состоит в рассмотрении (вместо отображений)бинарных отношений, определенных на прямых произведениях автоматныхмножеств. В случае, когда автомат представлен системой уравнений над конечной алгебраическойсистемой, построение модели исследуемого автомата сводится к решениюзадачи параметрической идентификации соответствующей дискретной динамическойсистемы.Задачи анализа и синтеза поточных шифров оказались мощным катализатором появленияновых направлений дискретного анализа, в которых переплетаются модели иметоды теории конечных автоматов, современной алгебры и комбинаторного анализа.Рассмотрим кратко некоторые из таких направлений.Первым типом модели структурного конечного автомата, часто применяемого прирешении задач криптографии, является специальным образом подобранная комбинаторнаяструктура, находящаяся под управлением псевдослучайного генератора. Основнаясложность построения таких моделей конечного автомата связана именно свыбором комбинаторной структуры, так как здесь переплетаются все три аспекта исследованиязадач математической кибернетики:1) дескриптивный аспект, состоящий в формальном определении класса возможныхкандидатов;2) алгоритмический аспект, состоящий в построении соответствующих алгоритмови доказательстве их корректности;3) метрический аспект, состоящий в анализе сложности предложенных алгоритмови, в силу специфики криптографии, анализе вычислительной стойкости некоторыхиз них.Проиллюстрируем сказанное на примере.Пример 1. Естественным обобщением парадигмы УПО является регулярнаякомбинаторная структура (РКС), являющаяся, по своей сути, представленнымв неявном виде управляемым бинарным отношением. РКС, по-видимому, впервые введенав [15] и предназначена для математического анализа решения задачи разрушениячастот букв - модельной задачи криптографии. Рассмотрим кратко эти построения.Пусть L С E+ - заданный язык; L(k) = {u G L|d(u) ^ k} (k G N), где d(u) -длинаслова u; n(u, a) (u G E+, a G E) -число вхождений буквы a в слово u иЕ n(u,a)v(L(k),a) = .. . (k G N, a G E).E d(u)uEL(k)Предполагается, что для каждого a G E существует пределlim v(L(k),a) = a(a) > 0,откуда вытекает, что для любого фиксированного положительного числа е для каждогоa G E существует такое число k0(a, е) G N, что для всех k > k0(a,е) (k G N)|v(L(k),a) - a(a)| < e.Зафиксируем такое положительное число е, чтоa(a) - е > 0для всех a G E, и положим k0(е) = max k0(a, е)aES .Относительной частотой появления буквы a E в словах языка L назовем число/rqnc(L, a) = v^ (^ (е )), a).Отметим, что из приведенных построений вытекает, что:1) /rqnc(L, a) > 0 для всех a G E;2) Е / rqnc(L,a) = 1.ст€ЕПредположим, что каждое число /rqnc(L, a) (a G E) представлено двоичной дробью,вычисленной с точностью до 2-r (r G N), причем выполнены оба приведенныхвыше условия.Алгоритмом побуквенного кодирования назовем алгоритм, вычисляющий значенияфиксированного инъективного отображенияcdng : E ^ E11 (h = [log |E|])с временной и емкостной сложностью, соответственно равнойO(li) (|E| ^ to),O(|E| li) (|E|^to).Ясно, что для всех a G E/rqnc(cdng(L), cdng(a)) = /rqnc(L,a),т. е. относительные частоты букв в словах языков L и cdng(L) совпадают. Отсюда вытекаеткорректность построения комбинаторных структур в терминах языка cdng(L)и относительных частот букв в словах языка L. В дальнейшем, для краткости, вместозаписи /rqnc(L,a) будем использовать запись /rqnc(a).Зафиксируем число h Е N (h ^ г) и такое число l2 Е N, что l2 ^ l1 + h. Регулярнаякомбинаторная структура для языка L определена в [1, 16] как бинарное отношениеД С E11 х Ei2, удовлетворяющее следующим пяти условиям:1) рг1Д = cdng('E);2) Д(с^пд(а)) = 2r ■ frqnc(a) для всех а Е Е;3) Д(с^пд(а\)) П Д(с^пд(а2)) = 0 для всех а1,а2 Е Е (а\_ = а2);4) каждое множество Д(с^пд(а)) (а Е Е) представлено в неявном виде с емкостнойсложностью O(l2) (l2 ^ то);5) существует алгоритм A, который при фиксированной начинающейся с нуля нумерацииэлементов любого множества Д(с^пд(а)) (а Е Е) порождает 0-й элементмножества Д(с^пд(а)) и по j -му элементу (j = 0 ,1,... , 1Д(сйпд(а))1 - 1) множестваД(сАпд(а)) порождает (j + 1)(mod 1Д(сАпд(а))\)-й элемент множества Д(сАпд(а)) с временнойи емкостной сложностью, равной O(l2) (l2 ^ то).В [1, 16] доказано, что множество регулярных комбинаторных структур для языкаL непусто. Этот результат является, по своей сути, аналогом доказательства непротиворечивостипостроенного фрагмента теории и обосновывает исследование возможностипостроения математической модели дискретного преобразователя, основанногона использовании таких структур и предназначенного для разрушения частот букв вязыке L. Такой дискретный преобразователь автоматного типа построен в [1, 16]. Псевдослучайныйгенератор применяется для инициализации значений элементов множествД(с^пд(а)) (а Е Е). Доказана корректность предложенных алгоритмов. Показано,что при выполнении ряда предвычислений разрушение частот букв в языкеL осуществляется с линейным замедлением. Исследована вычислительная стойкостьреализуемого построенным дискретным преобразователем алгоритма (при его интерпретациив качестве поточного шифра).Второй тип модели структурного конечного автомата, применяемого при решениизадач криптографии, основан на использовании представленного в неявном виде семействалегко вычислимых перестановок заданного конечного множества, выбор элементовкоторого управляется посредством заданного быстрого алгоритма. Рассмотримобщую схему построения таких моделей.Перестановка f Е S элементов конечного множества S называется легко вычислимой,если существует алгоритм A f , реализующий эту перестановку с временной иемкостнойсложностью, соответственно равнойVf = O(\og IS|) (IS 1^то),Tf = O(log2ISI) (|SI ^ то).Перестановка f элементов конечного множестваS = Sl х ■ ■ ■ х Siназывается легко вычислимой разложимой перестановкой, если существуют такие легковычислимые перестановкиf l , . . . , f iэлементов соответственно множеств Sl,... , Si, что для любого s = (s1, ... , si) Е Sf(s) = ( f l (sl) , . . . , f i(si))(несложно показать, что если f 1, ... , fi -легко вычислимые перестановки, то f -легковычислимая перестановка множества S, так что это определение корректно).Пусть в неявном виде задано такое семейство легко вычислимых разложимых перестановокF = {fi = (f1i), - - - , f l i))}ieLm,что:1) генерация алгоритма Afo осуществляется за время O(log |S|) (|S|) ^ то);2) преобразование алгоритма A . (j Е Zm) в алгоритм Af(j.+1)(modm) осуществляетсяза время O(log2|S|) (|S|) ^ то).Обозначим через B быстрый алгоритм, который (по заданному входу) генерируеттакую последовательность натуральных чиселП0,П1,П2 . . . , (2)что для всех i Е Nni < < m.Соответствующий дискретный преобразователь автоматного типа преобразует любуюпоследовательностьs0 , s1 , s2 , . . .элементов множества S в последовательностьfno (s0) , fno+nl (s1) , frao+rai+ra2 (s2) , . . .Проиллюстрируем сказанное на примере.Пример 2. В [1, 17, 18] предложен следующий подход к построению поточныхшифров. Шифруемая входная последовательность разбивается на тройки байтов, которыеинтерпретируются как RGB-компоненты bmp-файла. Шифрование каждой такойтройки байтов (по своей сути, изменение цвета соответствующего пикселя) осуществляетсяпосредством семейства легко вычислимых перестановокF {fi} i€Z266 ,определяемого соотношениямигп = (г0 + n ■ 1а'П ■ a1 - а'П ■ a2 - а'П ■ a3|) (mod 25)6),дп = (д0 + n ■ 1аП ■ a2 - а'П ■ a1 - а'П ■ a3|) (mod 256),bn = (b0 + n ■ 1аП ■ a3 - а'П ■ a1 - а'П ■ a2\) (mod 256),где г0,д0,Ь0 и гп,дп,Ьп - соответственно исходные и преобразованные компоненты цветапикселя, а аг, ai Е Z (i = 1, 2, 3) -параметры, играющие роль секретного сеансовогоключа.Последовательность натуральных чисел (2) вычисляется на основе номеров итерацийпостроения на дисплее точек выбранного псевдофрактала.Третий тип модели структурного конечного автомата, применяемого при решениизадач криптографии, основан на представлении обратимых автоматов системами уравненийнад конечной алгебраической системой. Значимость таких моделей обусловленатем, что в последнее десятилетие в криптографии наметилась устойчивая тенденцияперехода от чисто комбинаторных конструкций к конечным алгебраическим системам.Эта тенденция проявляется в том, что практически во всех современных стандартахшифрования присутствует фрагментарное применение теории конечных полей, азначительное число схем поточного шифрования, представленных в рамках реализуемыхв настоящее время европейского и японского проектов (соответственно NESSIE иCRYPTREC), основано на использовании автоматов над полем GF(2k). Известно, чтополе - это специальный случай кольца. При этом наличие в кольце делителей нуля даетвозможность охарактеризовать сложность поиска в терминах сложности решенияуравнений над кольцом. Конечные автоматы над конечным кольцом, применяемыедля решения задач криптографии, будут рассмотрены в последующих разделах. Сейчасотметим только, что исследование таких автоматов актуально для современнойкриптографии по следующим причинам.Во-первых, при соответствующих ограничениях на параметры автоматы над конечнымкольцом определяют класс поточных шифров, вычислительная стойкость которыхможет быть теоретически охарактеризована в терминах сложности решенияуравнений над кольцом.Во-вторых, устанавливается нетривиальная внутренняя связь между современнойкриптологией и теорией систем, так как сложность и эффективность успешных атакдля криптоаналитика естественно характеризуется в терминах сложности решениятаких классических задач теории динамических систем, как управляемость, наблюдаемость,параметрическая идентификация.В-третьих, устанавливается нетривиальная внутренняя связь между современнойкриптологией, теорией автоматов и современной алгеброй, что дает возможность прирешении задач криптографии систематически и комплексно использовать модели иметоды этих разделов математики, а также стимулировать формирование некоторыхнаправлений исследований этих разделов математики, предназначенных именно длянужд криптографии.1.3. К о м б и н а т о р н ы й а н а л и зОб исключительной роли, которую комбинаторные конструкции играли и играютв криптографии, прежде всего свидетельствуют многочисленные примеры шифров икриптографических протоколов, основанных на их использовании (см., напр., [19]).По-видимому, для современной криптографии важными являются следующие особенности,связанные с применением комбинаторного анализа.Во-первых, это переосмысление известных комбинаторных конструкций в контекстезадач современной криптографии.Пример 3. В качестве регулярных комбинаторных структур, предназначенныхдля разрушения частот букв, в [15] использовались:1) грани куба En, которые, как известно, являются стандартной комбинаторнойконструкцией в теории минимизации ДНФ;2) система попарно непересекающихся шаров в пространстве En, которая, как известно,применяется в теории кодов, контролирующих ошибки.Во-вторых, это анализ возможности применения экстремальных и близких к нимкомбинаторных объектов для решения задач криптографии.Пример 4. В [20] было построено и исследовано семейство связных графов, удовлетворяющихследующим трем условиям:1) граф имеет почти регулярную структуру (откуда вытекает возможность егоэффективного представления в неявном виде);2) число гамильтоновых путей между двумя фиксированными вершинами являетсясубэкспонентой от числа ребер;3) существует такой алгоритм, который порождает субэкспоненциальное число гамильтоновыхпутей на графе между этими фиксированными вершинами, причем каждыйиз этих путей порождается за время O(n) (n ^ то), где n - число вершин графа.В [15] показано, что такие графы могут быть эффективно применены при решениизадачи диффузии информации - модельной задачи криптографии.В-третьих, это необходимость метрического анализа комбинаторных конфигураций,определяемых в терминах модульной арифметики, в отличие от классическогоподхода комбинаторного анализа, основанного на использовании линейно или частичноупорядоченных множеств (см., напр., [21, 22]).Пример 5. В [23] исследована следующая комбинаторная конфигурация.Пусть S - непустое конечное множество, а а1, ... , an G N - взаимно простые числа.Положим(S) = { f |f : S ^ } (i = 1,... , m),F(S) = { f |f : S ^ Z m }.Пi=1Определим отображение fmodOi ( f G F(S); i = 1,... ,m) равенствомfmodoi = f (s)(moda*) (s G S).Зафиксируем подмножества Fai (S) С Fai (S) (i = 1,... ,m) и положимFOi (S) = { f G F (S) | fmod Oi G FOi (S)} (i = 1,... ,m).В [23] доказано, чтоm mIП FOi (S )l = П |FOi (S). (3)i=1 i=1Нетривиальность равенства (3) обусловлена хотя бы тем, что оно дает возможностьнайти точное число обратимых матриц над кольцом Zn (n G N), его следствиямиявляются китайская теорема об остатках и формула Эйлера для количества чисел,взаимно простых с данным числом.1.4. Алг е б р аК стандартному аппарату алгебры, применяемому в современной криптологии, относятся(см., напр., [24]) ряд разделов теории чисел (методы решения сравнений, использованиепервообразных корней, сведение задачи к поиску индекса (дискретногологарифма), применения цепных и подходящих дробей), ряд разделов теории конечныхалгебр (конечные группы, конечные поля и векторные пространства над ними,кольца и модули линейных форм над ними), теория эллиптических кривых, а такжетеория алгебраических систем.Формирование проблематики этих разделов математики осуществлялось без учетапотребностей криптологии, и только в настоящее время начинают выделяться те ихнаправления, которые существенно опираются на теорию алгоритмов и компьютернуюматематику и действительно могут стать мощным инструментом при исследованиизадач защиты информации.По-видимому, одним из самых тонких и сложных моментов, связанных с использованиемсистем уравнений над конечными алгебраическими системами в криптографии,является теоретическое исследование сложности их решения. Именно эта сложность,в конечном итоге, характеризует сложность идентификации сеансового ключадля шифра, определяемого этими системами уравнений.Пример 6. В [25] исследовано семейство легко вычислимых перестановокF = {fi = f , . . . , f l ^ U z , , ,которое является нетривиальным обобщением семейства перестановок из [17, 18]. Компонентыэтих перестановок определяются уравнениями над кольцомZ = (Zpk , ф, о) ,где р - простое число. Показано, что параметрическая идентификация этого семействаперестановок сводится к решению системы высокостепенных уравнений над конечнымкольцом, при этом необходимо решить l задач поиска дискретного логарифма.По-видимому, заслуживает внимания исследование возможности применения длярешения задачи выбора секретного ключа средней длительности для двух пользователейпараметрических диофантовых уравнений (как известно, проблема поиска решениядиофантовых уравнений алгоритмически неразрешима). На примерах простейшихпараметрических диофантовых уравнений нетрудно убедиться, что структура множестваих решений может существенно варьироваться в зависимости от значений параметров.Поэтому даже передача открытым текстом номера решения, определяющегосекретный сеансовый ключ, мало что даст криптоаналитику для идентификации этогоключа.Одним из наиболее перспективных методов генерации ключей для электронноцифровойподписи является применение эллиптических кривых над конечным полем.Это направление исследований в настоящее время интенсивно развивается (см.,напр., [26, 27]). Однако в настоящее время отсутствует систематизация полученныхрезультатов и системная характеристика тонких мест этого направления именно с позициисовременной криптологии.Наконец, следует отметить, что в последнее время при исследовании различных аспектоврешения задачи защиты информации фрагментарно используются те или иныеварианты многоосновных алгебраических систем. К таким исследованиям относятсяанализ структуры гомоморфизмов универсальных многоосновных алгебр, применяемыхпри минимизации сложности решения уравнений, связанных с анализом блоковшифрования [28], попытка теоретической проработки основ построения системыкомпьютерного моделирования системы защиты информации (с применением системыавтоматического вывода), предпринятая в [29], а также исследования формальныхмоделей систем компьютерной безопасности (см., напр., [30]).Рассмотренные особенности комбинаторно-алгебраических моделей далеко не исчерпываютвсего круга проблем, возникающих при их применении для исследованиязадач современной криптографии.Во-первых, вне внимания криптографии остаются многочисленные комбинаторноалгебраическиеконструкции, успешно применяемые в теории кодов, контролирующихошибки [31]. Применение таких конструкций (после соответствующей их модификации)дает возможность автоматически обнаруживать и исправлять некоторые случайноили преднамеренно внесенные ошибки, что повышает эффективность использованияшифрсистем.Во-вторых, как показал печальный опыт с ранцевым алгоритмом шифрования,требует самого тщательного теоретического обоснования сужение множества исходныхданных NP-полных задач, которые естественно возникают при их применениив криптографии. Сложность такого теоретического обоснования весьма велика, таккак оно, по своей сути, эквивалентно доказательству утверждения о том, что не существуетэффективная атака того или иного типа. По-видимому, единственным эвристическимвыходом из этой ситуации является использование семейства однотипных,имеющих различные размеры, комбинаторных конструкций, определяемых применяемойNP-полной задачей. Такой подход дает возможность в процессе сеанса шифрованиядинамически варьировать применяемые конструкции (и их размеры) с помощьюпсевдослучайного генератора. При таком подходе, по крайней мере, есть надежда, чтокриптоаналитик столкнется с трудной проблемой тождества слов.В-третьих, в настоящее время интенсивно развивается теория квантовых вычислений[32]. Существенной особенностью этой теории является то, что она в корне изменяетвзгляд на прикладную теорию алгоритмов, так как, во-первых, ее эффективныминструментом являются методы, осуществляющие построение решения с заданной вероятностью,а, во-вторых, в ее рамках возможно эффективно реализовать ряд методовпоиска, имеющих экспоненциальную сложность в классической прикладной теорииалгоритмов. По-видимому, серьезным предупреждением для криптографии являетсясуществование полиномиального квантового алгоритма для разложения числа на двапростых сомножителя. Поэтому исследование комбинаторно-алгебраических моделей,для анализа которых не существует эффективных квантовых алгоритмов, являетсяактуальным для современной криптографии.Все сказанное выше, наряду с интенсивным развитием средств вычислительнойтехники, обосновываетактуальность теоретической проработки математическихоснов, обеспечивающих адекватное и эффективное применение комбинаторноалгебраическихмоделей в процессе решения задач современной криптографии.2. Модели хаотической динамики в анализе шифровНа протяжении последнего двадцатилетия усилия многочисленных коллективовученых различных стран привели к значительным успехам в области исследованиясвойств детерминированного хаоса динамических систем (см., напр., [33, 34]).Говоря неформально, динамическая система представляется таким наборомиз n динамических переменных, характеризующих состояние системы, что их значенияв любой последующий момент времени получаются из набора исходных значенийпо определенному правилу, называемому оператором эволюции системы. Динамику(иными словами, эволюцию) такой системы можно представить как движениеточки по траектории в n-мерном фазовом пространстве. Динамическую систему,представленную системой дифференциальных уравнений, часто называют потоком, апредставленную системой рекуррентных соотношений - отображением (отметим, чтопри компьютерном моделировании динамических систем всегда происходит переход отпотока к отображению). Динамическая система называется хаотической, если скольугодно малое изменение начального состояния системы быстро нарастает во времени.Это означает, что сколь угодно малая неточность в задании начального состояниясистемы делает невозможной предсказуемость ее эволюции на достаточно большихинтервалах времени.Выделим в фазовом пространстве динамической системы некоторую область (еечасто называют облаком) и рассмотрим эволюцию облака. Если с течением времениобъем облака остается постоянным, то динамическая система называется консервативной(с физической точки зрения консервативность означает сохранение энергии).Если же с течением времени объем облака изменяется, то динамическая система называетсядиссипативной. Для диссипативных систем характерно то, что с течениемвремени облако съеживается и концентрируется на одном или нескольких аттракторах,т. е. подмножествах фазового пространства, обладающих, как правило, нулевымфазовым объемом (наиболее известные примеры аттракторов - это положениеравновесия и предельный цикл, т. е. замкнутая фазовая траектория, к которой с течениемвремени стремятся все близкие траектории). Множество всех точек фазовогопространства, из которых траектории приходят к одному и тому же аттрактору, называетсябассейном этого аттрактора.В диссипативных системах хаос часто связан с наличием странных аттракторов,представляющих собой фрактальные множества (или, кратко, фракталы), т. е.множества, имеющие сложную самоподобную структуру и притягивающие к себе всетраектории, принадлежащие бассейнам этих аттракторов.В процессе исследования хаотических динамических систем большое внимание уделялось(и уделяется в настоящее время) применениям таких систем к решению задачпреобразования информации. Здесь следует особо отметить исследования, связанныес разработкой методов записи и восстановления информации, основанные на использованииустойчивых циклов [35-38], которые, в конечном счете, привели к парадигмехаотического процессора [39], т. е. к математической модели, позволяющей работатьс информацией как с траекторией в фазовом пространстве и управлять характеромдинамических явлений с целью осуществления базовых операций хаотического процессинга.Именно представление информации траекториями, а также обработка информациипосредством хаотических динамических систем и составляют основу применениямоделей и методов хаотической динамики в криптографии.Подчеркнем, что применение любой схемы представления информации циклами,порождаемыми в фазовом пространстве хаотической динамической системой, по сути,приводит к шифрованию исходной информации, причем вычислительная стойкостьтакого шифра заведомо не меньше, чем вычислительная стойкость шифра замены,переводящего элементы исходной информации в циклы.Цель настоящего раздела - проиллюстрировать основные из подходов, применяемыхпри использовании моделей и методов хаотической динамики для решения задачсовременной криптографии.2.1. Мо д е ль х а о т и ч е с к о й динамики в к р и п т о г р афи ис о т к рытым к люч омВ [40-42] предложен следующий подход к разработке шифрсистем с открытымключом, основанный на неоднозначности обращения кусочно-линейных хаотическихотображений.В качестве кусочно-линейного хаотического отображения выбрано отображениетент, рекуррентное уравнение которого имеет вид- , если 0 ^ xn < а,xn+i = { 1а- xn (n . Z+^ (4)если а < xn ^ , ---- - ^ ,vn 1, 1 - агде а . (0; 1) -параметр.В случае когда а = 0,5, решение рекуррентного уравнения (4) имеет видxn = -п ■ arccos(cos(2n ■ п ■ xo)) (n . Z+), (5)где xo - начальное значение.Равенство (5) представляет собой подсемейство однопараметрического семействаотображенийTk(x) = -п ■ arccos(cos(k ■ п ■ xo)) (k . N). (6)В дальнейшем рассматривается именно семейство отображений (6), что совершенноне влияет на общность рассуждений.Отметим, что семейство отображений (6) удовлетворяет полугрупповому свойствуTr.s = Tr О Ts (r, s . N), (7)где о - операция суперпозиции отображений. Из (7), в свою очередь, вытекает, чтосемейство отображений (6) удовлетворяет также свойству коммутативности, т. е.Tr о Ts = Ts о Tr (r, s . N).Предполагается, что подлежащее шифрованию сообщение - это m-битовая последовательность,а M - целое число, представляющее эту последовательность.В [41, 42] исследована следующая математическая модель шифрсистемы с открытымключом.Формирование ключей пользователем A осуществляется следующим образом:1) генерируются такие натуральные числа p и q, что n = p ■ q > 2m;2) ищется неустойчивая неподвижная точка xo . (0; 2-m) отображения Tn;3) вычисляется открытый ключ yo = Tp(xo).Пара (xo, q) - личный секретный ключ пользователя A.Для того чтобы отправить пользователю A сообщение M, пользователь B вычисляети отправляет пользователю A шифртекст c = Tm (yo).Для того чтобы расшифровать сообщение, пользователь A вычисляет значениеM =xoДействительно, с учетом того, что M ■ xo ^ 1, получимTq(c) _ Tq(Tm (yo)) _ Tq(Tm (Tp(xo))) _ Tm (Tn(xo))xo xo xo xoTM(xo) arccos(cos(n ■ M ■ xo)) п ■ M ■ xoxo п ■ xo п ■ xoM.В [41] исследована вычислительная стойкость рассмотренного шифра, а в [42] -точность вычислений, при которых процесс шифрование - расшифрование корректен.Ясно, что рассмотренный выше подход к построению шифрсистемы с открытымключом применим для любых кусочно-линейных хаотических отображ

Скачать электронную версию публикации