Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Общая концепция решения указанной задачи состоит в сведении ее к более простым задачам, решаемым известными (“базовыми”) алгоритмами.

Ниже дается краткое описание базовых алгоритмов и методов сведения к ним.

Базовые алгоритмы: алгоритмы поиска, алгоритмы решения систем линейных и нелинейных уравнений над различными алгебраическими структурами (поля, кольца и т.д.), итерационные методы.

Каждый базовый алгоритм, как и метод сведения к нему содержит широкий круг разнообразных методов, связанных собственной “иерархией”. Ниже приводится их краткая характеристика.

Алгоритмы поиска. Любой алгоритм нахождения решения c` уравнения

Ф(c)=y

представляет собой последовательность действий на основе системы тестов и может быть описан как алгоритм поиска элемента c` в массиве К. В криптографической литературе под алгоритмами поиска нередко понимают узкий класс алгоритмов поиска - метод последовательного перебора (метод тотального опробования), в соответствии с которым опробуются поочередно в некотором порядке элементы c множества К. Для каждого опробуемого варианта c вычисляется y^c=Ф(c) и сравнивается c y по критерию на совпадение. При принятии решения о несовпадении y^c с y опробуемый вариант c отбраковывается. При известной структуре (частичной структуре) множества К применяют “упорядоченный”, “направленный” перебор элементов из К. Так, например, при структуре множества “больше - меньше”:

у₁<у₂<...<у_|К|

для нахождения номера заданного элемента y сравнивают y с со средней точкой у[|W|/2] массива и выбирают ту половину его, в которой лежит y, затем сравнивают y со “средней точкой” выбранного “половинного массива” и так далее до идентификации элемента y. Число операций такого способа оценивается величиной log₂К. Иногда удается сгруппировать элементы массива в “легко различимые” между собой группы и вначале определять номер группы, в которой лежит y, а затем определять номер y, ведя поиск y в этой выделенной группе. Сократить число операций при структуре ключей «больше – меньше» возможно, если использовать предварительную кодировку у-ов и «удобно» расположить у-ки в соответствии с их адресами (см. Зубков А.М., Клыкова Н.В. Построение баз данных с ограниченным временем поиска. Симпозиум по прикладной и промышленной математике. Тезисы доклада. 2001г. стр. 185-186).

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

Алгоритмы решения систем линейных и нелинейных уравнений над различными алгебраическими структурами (поля, кольца и т.д.). Для решения систем линейных уравнений в этих структурах существует широкий круг известных “стандартных” алгоритмов, таких как - алгоритмы Гаусса, Штрассена, Коновальцева для решения общих систем линейных уравнений над конечными полями и кольцами; - алгоритмы решения некоторых специальных систем линейных уравнений, например, ганкелевых систем или систем с разреженной матрицей. Из алгоритмов решения систем нелинейных уравнений отметим алгоритм Лазера.

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

Методы частичного опробования. В методах этого класса пытаются «разбить» ключ c на две части c₁,c₂ и представить его в виде c=(c₁,c₂) таким образом, чтобы при каждом варианте c₁ уравнение Ф(c₁,c₂)=y относительно c₂ решалось достаточно «просто», например, с трудоемкостью меньшей чем полный перебор возможных значений c₂. При выполнении этих условий решают уравнение Ф(c₁,c₂)=y перебором возможных вариантов c`<sub>1</sub> с последующим решением уравнения Ф(c`₁,c₂)=y для каждого опробуемого варианта c`₁. Примером такого метода служит метод решения нелинейных булевых уравнений путем линеаризации за счет опробования части переменных.

Методы последовательного опробования. Этот метод является развитием метода частичного опробования. В этом методе так же пытаются «разбить» ключ c на две части c₁,c₂ и представить его в виде c=(c₁,c₂) таким образом, чтобы при каждом варианте c₁ для уравнения Ф(c₁,c₂)=y относительно c₂ достаточно «просто», устанавливалось разрешимо оно или нет. Если при варианте c`<sub>1</sub> оно неразрешимо относительно c<sub>2</sub>, то вариант c`₁ отбраковывается и опробуется следующий вариант. В случае же положительного ответа уравнение Ф(c`₁,c₂)=y пытаются решить всеми возможными средствами, например, пытаются применить метод частичного опробования для части c₂, всего ключа c. В последнем случае и говорят о применении метода последовательного опробования.

Методы сведения к базовым алгоритмам основаны:

- на преобразовании как уравнений, так и множества неизвестных; на использовании различных моделей алгебраических структур (гомоморфные образы автоматов, алгебр, их приближенные модели и т.д.);

- на использовании частичного и последовательного опробования.

Неизвестные параметры c₁,c₂,…,c_n - части ключа c, относительно которых решается уравнение, могут быть заданы в различной форме, влияющей как на выбор способов решения уравнения так и на их сложность. Так, например, подстановка может быть задана в обычной двухстрочной форме, или в матричной форме; двоичная функция может быть задана таблично, в виде многочлена Жегалкина, в виде вектора ее коэффициентов Фурье по любому базису n-мерного векторного пространства над полем вещественных чисел или над конечным полем и т.д. Собственно сам метод сведения к базовым алгоритмам и состоит в выборе способа представления, «кодирования» частей ключа.

Преобразования уравнений шифрования. Многие методы преобразования системы уравнений шифрования нацелены на получение уравнений – следствий, которые могут быть решены известными способами. Например, подбирают множество У` совместно с отображением j: Y®Y`, так чтобы новое уравнение - следствие

j(Ф(c))=j(y)

решалось достаточно просто. Найдя все множество М решений этого уравнения, решают, относительно cÎМ, начальное уравнение Ф(c)=y, например, опробуя элементы множества М. К таким методам относятся так называемые “методы сведения”: выделение из системы уравнений

Ф_t(c₁,c ₂,…,c _n)=y_t, tÎ{1,…,T}

«хороших уравнений», например линейных, или выделение уравнений, из которых можно составить систему уравнений «треугольного типа» и т.д.

Преобразование неизвестных. Один из способов преобразования неизвестных состоит в поиске нового множества К` и отображений j: К®К`, y: К`®Y, так чтобы Ф(c)=y(j(c)). В этом случае задача поиска решения уравнения Ф(c)=y сводится к решению двух уравнений

y(c`)=y,

j(c)=c`.

При таком сведении задачи поступают следующим образом. Находят все решения c` первого уравнения, а затем решают второе уравнение для каждой правой части c`, найденной ранее. Типичным примером преобразования неизвестных при решении системы нелинейных уравнений является введение новых переменных, приводящих систему уравнений относительно этих новых переменных к системе линейных уравнений.

Методы использования гомоморфизмов. Итак, мы изучаем возможности

определения прообраза c отображения Ф: К®У по известному образу у=Ф(c).

Ищутся такие подходящие множества К` и У` и отображения j: К®К`, y:Y®Y`, f:К`®Y`, чтобы была коммутативна следующая диаграмма:

Ф

К ® У

j ¯ ¯ y

К` ® Y`

f

Сначала решается уравнение f(c`)=y`, относительно c`ÎК` при у`=y(y). Это уравнение называют гомоморфным образом уравнения Ф(c)=y.

Затем для каждого найденного решения c` решается уравнение j(c)=c`. Обозначим через М все найденные таким образом решения (объединение всех решений уравнения j(c)=c` по всем решениям c` уравнения f(c`)=y`). Далее решают начальное уравнение Ф(c)=y относительно cÎM.

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

Наряду с использование базисных алгоритмов и методов сведения к ним при решении задачи определения ключа нередко используют и дополнительные предположения, облегчающие расчет параметров эффективности используемого метода решения. Например, предполагают, что решение уравнения Ф(c)=y единственно, в частности, используемый шифр не имеет эквивалентных ключей, объем T материала больше расстояния единственности шифра.