Efficient methods of algebraic cryptanalysis and protection against them.pdf 1. Методы криптоанализа алгебраической криптографии 1.1. Метод линейного разложения Метод введён в рассмотрение автором в [1, 2], получил дальнейшее развитие в [3-5] и ряде других публикаций, подробно освещён в монографии [6]. Метод детерминированный и доказуемый, применим как к конечным, так и к бесконечным объектам. Его отличительной особенностью является то, что построенный по этому методу алгоритм криптографического анализа находит распределяемый ключ или передаваемое сообщение, не вычисляя секретных параметров, использованных при зашифровании. Алгоритм не решает алгоритмической проблемы, лежащей в основе криптографических построений, обходя тем самым построенную авторами защиту и не преодолевая трудностей, заложенных при построении криптографической схемы. Метод использован для криптографического анализа криптографических алгоритмов Маркова - Михалева и др., Грибова - Золотых и др., Росошека, Харли, Мегрели-швили, Шпильрайна - Ушакова, Кахроби - Шпильрайна и др., Ко - Ли и др., Ванга и др., Курта, Хехта и ряда других авторов. Метод работает в тех случаях, когда платформа шифрования G является частью линейного пространства V, например группой матриц над некоторым конструктивным полем F (конечным или бесконечным), рассматриваемой как подмножество линейного пространства M(n, F) матриц размера п х п. Типичными элементами метода являются: построение базиса линейного подпространства, порождённого подмножеством из G опредёленного вида в пространстве V; использование свойств этого подпространства для определения секрета. В криптографии с открытым ключом хорошо известна проблема Диффи - Хелл-мана: для группы G и её элемента g G G определить по двум значениям gk и g1, где k,l - натуральные числа, значение gk1. В алгебраической криптографии рассматриваются следующие её некоммутативные аналоги: - Аналог с сопряжениями: для группы G и её элемента g G G определить по двум сопряжённым к g элементам ga = aga-1 и gb = bgb-1, где a, b G G, ab = ba, элемент gab = abga-1b-1 = bagb-1a-1. - Аналог с двусторонними домножениями: для группы G и её элемента g G G определить по двум элементам вида aga' и bgb', где a, b G G, ab = ba, a'b' = b'a', элемент abga'b' = bagb'a'. - Аналог с автоморфизмами: для группы G и её элемента g G G определить по двум элементам вида a(g) и в(g), где а, в G Aut(G), ав = ва, элемент a(e(g)) = e(a(g)). Метод линейного разложения при некоторых естественных условиях на группу G (прежде всего это существование эффективного вложения в конечномерное линейное пространство) эффективно решает каждую из этих проблем. 1.2. Span-метод Б. Тсабана В [7] (см. также [8]) Б. Тсабан и др. ввели в рассмотрение полиномиальный по времени вероятностный метод алгебраического криптоанализа, названный ими линейным span-методом. Метод позволяет разрабатывать способы эффективного решения вычислительных проблем в группах матриц над конечными полями, значит, и в группах, допускающих эффективные представления матрицами над конечными полями. Метод улучшает более ранние методы, описанные в [9, 10]. Как и в методе линейного разложения, span-метод предполагает построение базисов некоторых линейных подпространств, определяемых матричной группой G над конечным полем Fq порядка q. Приведём типичный пример использования метода. Допустим, нужно решить проблему поиска сопрягающего элемента X для данных матриц A и B = XAX-1 из группы GL(n, Fq). Данное уравнение заменяется на систему линейных однородных уравнений, соответствующую матричному уравнению XA = BX. Строится базис s E = {e1,... ,es} пространства решений и записывается общее решение X = а^. i=1 Теперь нужно, варьируя коэффициенты а^, i = 1,... , s, найти среди решений невырожденную матрицу X. Нам известно, что невырожденное решение существует. Тогда можно воспользоваться следующей леммой. Лемма 1 (лемма обратимости [7, Lemma9]). Пусть элементы e1,...,es кольца s матриц M(n, Fq) таковы, что некоторая их линейная комбинация У] а^ с коэффиi=1 циентами из Fq является обратимой матрицей. Если коэффициенты выбираются в соответствии с равномерным распределением на Fq, то вероятность получения невырожденного решения будет не меньше чем p =1 - n/q. Метод эффективен, если n существенно мало по отношению к q. 1.3. Метод нелинейного разложения Данный метод введён автором в [11] как дополнение к методу линейного разложения. Он работает в тех случаях, когда группа не допускает представления матрицами или это представление имеет слишком большой размер для возможного использования. Конечно, здесь также предполагается выполнение ряда условий, связанных с разрешимостью проблемы вхождения в конечно порождённые подгруппы группы, выбранной в качестве платформы для криптографической схемы. Эти условия, как правило, выполняются в конечно порождённых нильпотентных и полициклических группах, часто предлагаемых для такого применения в последние годы. Относительно соответствующей теории см. [6], приложения можно найти в [4, 5, 12]. Метод нелинейного разложения при некоторых естественных предположениях о группе G (прежде всего, они касаются эффективной разрешимости проблемы представления элемента конечно порождённой подгруппы в виде слова от её порождающих элементов) эффективно решает перечисленные выше три проблемы, аналогичные проблеме Диффи - Хеллмана. 1.4. Примеры использования методов линейного и нелинейного разложения Рассмотрим общую схему, под которую подпадает большое число алгоритмов, использующих двусторонние домножения. Далее приведены два примера конкретных протоколов, показывающие широкую применимость методов линейного и нелинейного разложения для построения алгоритмов криптографического анализа. Общая схема алгоритмов, использующих двусторонние домножения Данный раздел основан на работе автора [13]. Большинство известных схем алгебраической криптографии, использующих двусторонние домножения, являются частными случаями одной общей схемы (см. описание ниже). Часто такие схемы строятся на группах, являющихся подгруппами линейных пространств, например на матричных группах. Метод линейного разложения позволяет эффективно вычислять в данном случае распределяемый ключ или передаваемое сообщение без вычисления секретных параметров [1-4, 14-17]. Далее описаны некоторые основные элементы такого вычисления и приведены примеры его использования. Некоторые такие схемы предложены М. Андрекутом [18], Л. Гу и др. [19, 20], Б. и Т. Харли [21, 22], В. Шпильрайном и А. Ушаковым [23], Е. Стикелем [24], Х. Вангом и др. [25]. Ряд схем описан в [26, 27]. Схемы, использующие сопряжения, например известная схема Ко - Ли и др. [28], рассматриваемая как некоммутативный аналог классической схемы Диффи - Хеллмана [29], также могут анализироваться указанным способом. Пусть G - группа, выбранная в качестве платформы для схемы распределения ключа. Предположим, что G - подмножество конечномерного линейного пространства V. Два корреспондента, Алиса и Боб, соглашаются относительно элемента h Е G и двух конечно порождённых подгрупп A и B группы G, заданных конечными множествами порождающих элементов. Предположим, что любой элемент a Е A перестановочен с любым элементом b Е B. Все эти данные открыты. Корреспонденты, начиная с h, попеременно публикуют элементы вида

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