Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/4

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

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

A nonlinear decomposition method in analysis of some encryption schemes using group automorphisms.pdf Введение В данной работе рассматривается применение метода нелинейного разложения, предложенного первым автором в [1], на примере двух схем: схемы передачи ключа Махалонобиса [2], являющейся алгебраическим аналогом классической схемы Масси - Омуры, и алгебраического аналога классического протокола Эль-Гамаля, использующего автоморфизмы [3, 4] (относительно классических версий см., например, [5]). В отличие от метода линейного разложения, теоретические основы которого изложены в [6] (см. также [7, 8]), метод нелинейного разложения не предполагает наличия структуры векторного пространства у платформы, на которой строится схема. В [2] А. Махалонобис предложил два протокола распределения ключа, один из которых является алгебраической версией протокола Диффи - Хеллмана, другой - алгебраической версией протокола Масси - Омуры. В качестве платформы шифрования предлагались конечно порождённые нильпотентные группы и их автоморфизмы специального вида. Оба протокола проанализированы в [6] в предположении, что используемая группа линейна. Методом линейного разложения установлено, что в этом случае протоколы уязвимы. Конечно порождённые нильпотентные группы всегда допускают точное представление матрицами, но размерность матриц может оказаться слишком большой для проведения такого анализа. Поэтому возникла потребность поиска других методов. В [1] первым автором дан криптографический анализ первого из этих протоколов (аналога протокола Диффи - Хеллмана), показана его уязвимость. При этом не была использована детализация групп и автоморфизмов из [2]. Применён новый метод нелинейного анализа, основанный на эффективной разрешимости в группе проблемы вхождения элемента в подгруппу. Отмечено, что такая проблема эффективно разрешима в полициклических, а значит, и в конечно порождённых нильпотентных группах. В последнем классе большинство основных алгоритмических проблем разрешаются алгоритмами с низкой сложностью. Об этом говорится далее более подробно. В том числе существует алгоритм низкой сложности, решающий проблему поиска вхождения элемента в подгруппу. В настоящей работе представлен криптографический анализ второго из протоколов работы [2] - алгебраической версии протокола Масси - Омуры. В предположениях автора протокола он оказывается уязвимым относительно анализа методом нелинейного разложения. Аналогичный анализ проведён также для алгебраической версии протокола Эль-Гамаля. Метод нелинейного разложения используется также для криптографического анализа алгебраической версии протокола Эль-Гамаля и алгебраической версии системы MOR, предложенной в [3, 4]. Доказано, что эти версии также уязвимы. Через ($1,..., gn) будем обозначать подгруппу рассматриваемой группы, порождённую элементами g1,... , gn. Выражение H ^ G означает, что H - подгруппа группы G. Напомним, что проблема поиска, соответствующая классической проблеме вхождения (поиска вхождения элемента в подгруппу), ставится следующим образом: для данной группы G, её подгруппы H = (h1,... ,hk) и заданного элемента g Е H найти слово u(x1,... ,xk), такое, что g = u(h1,... , hk). Если подгруппа H фиксирована, рассматриваем соответствующую проблему поиска вхождения элемента g Е H в H. Здесь и далее предполагается, что используется язык комбинаторной теории групп, в котором группы задаются своими представлениями через порождающие элементы и определяющие соотношения, элементы записываются словами от порождающих элементов. Допустимы также матричные задания групп и их подгрупп над полями, в которых основные операции эффективно выполнимы. Почти во всех известных случаях группы, предлагаемые как платформы для криптографических схем, задаются именно таким способом. Как правило, требуется наличие в группах нормальных форм записи элементов, операции над которыми также должны быть эффективными. Пусть G - алгебраическая система (группа, полугруппа, кольцо и т.п.), Aut(G)- её группа автоморфизмов. Через ga будем обозначать образ элемента g £ G относительно автоморфизма а £ Aut(G). Другими словами, ga = a(g). В данной работе мы ограничиваемся рассмотрением групп, но предлагаемый метод криптографического анализа при соответствующих условиях может быть применён и к произвольным алгебраическим системам. Если A - подгруппа группы автоморфизмов Aut(G) группы G и v £ G, то vA = = {va|a £ A} обозначает орбиту относительно A, порождённую элементом v. 1. Лемма о построении порождающего множества Пусть G - группа, A = (а1,... , an) -подгруппа группы автоморфизмов Aut(G). Лемма 1. Если в группе G эффективно разрешима проблема поиска вхождения элемента в подгруппу (gA) и подгруппа (gA) конечно порождена, то существует алгоритм построения её конечного порождающего множества. Доказательство. Считаем для простоты, что множество {а1,..., an} замкнуто относительно взятия обратных элементов. Упорядочим все конечные наборы вида ai1 ... ait, t = 0,1,..., в соответствии с длиной и лексикографическим порядком. Полученная последовательность содержит записи всех элементов множества gA. Элемент 1 соответствует набору длины 0. Через Li обозначим часть полученной последовательности, соответствующую наборам длины i; Mj = gLi -индуцированно упорядоченный набор элементов вида ga, а £ Lj. Последовательность множеств Mj, i = 0,1,..., очевид- A но, содержит все элементы множества g , а значит, и какое-то конечное порождающее множество подгруппы (gA). Опишем процесс построения конечного порождающего множества. Положим K0 = = M0 = {g}. Добавляем к K0 по очереди элементы gaj £ M1, для которых gaj £ £ (g,gai,... , gaj-1). Другими словами, добавляем элементы, не принадлежащие подгруппе, порождённой ранее выбранными элементами. Шаг заканчивается, когда будут просмотрены все элементы из M1 . В результате получим эффективно построенное подмножество K1 = {g,ga;i , ...,g"is : /1 < ... < Zs} множества K0 U M1. При этом оо (gA) = (K1, U мг). i=2 Если K0 = K1, то алгоритм завершает свою работу, констатируя, что (gA) = = (Ko) = (g) -циклическая группа. Действительно, в этом случае подгруппа (g) очевидно инвариантна относительно любого автоморфизма aj, i = 1,...,n, значит, и любого автоморфизма из A. Если K0 = K1, продолжаем описанный процесс, добавляя к K1 поочередно элементы из M2, не входящие в подгруппу, порождённую уже выбранными элементами. При этом можно сразу убрать из рассмотрения элементы вида gaiQj, где gai не является выбранным элементом. Это может значительно ускорить процесс. В итоге построим множество K2, равное объединению K1 с выбранными на этом шаге элементами из M2. Если ни один элемент не выбран, то (gA) = (K1). Это также следует из того, что группа (K1) в этом случае инвариантна относительно действия A. Далее аналогично строим множества Kr для r = 3,..., просматривая и поочередно добавляя элементы из соответствующего множества Mr. Заметим, что на каждом шаге и (gA) = (Kr, и Mi). i=r+1 На каком-то шаге получим Kt = Kt+1, так как группа (gA) по сделанному предположению конечно порождена. Тогда получаем равенство (gA) = (Kt). Заметим также, что если подгруппа (gA) имеет s порождающих, то процесс обязательно закончится не позднее чем при рассмотрении Ks. Описанный процесс находит наименьшее по мощности множество порождающих элементов группы (gA). Это позволяет в ряде случаев дать очевидную оценку сверху на число шагов алгоритма. ■ Замечание 1. Если A - коммутативная подгруппа, как далее в протоколе из [2], то рассматриваем не все конечные наборы вида ai1... ait, t = 0,1,..., а только те, для которых индексы не убывают. 2. Эффективность метода Метод нелинейного разложения применим, если в группе G, используемой в качестве платформы шифрования, эффективно решается проблема поиска вхождения элемента в подгруппу, соответствующая классической проблеме вхождения, а также если можно эффективно построить порождающие множества элементов для некоторых конечно порождённых подгрупп, использующихся при шифровании. Пример такого построения указан в лемме 1. Метод хорошо работает на ряде схем, построенных на полициклических группах, которые сейчас часто предлагаются в качестве платформ [9-11]. В полициклических группах любая подгруппа конечно порождена, причем количество её порождающих элементов оценивается сверху длиной полициклического ряда всей группы. Это позволяет дать верхнюю оценку времени работы алгоритма, описанного в лемме 1. В [12] показано, что основные алгоритмические проблемы (построения нормальной формы элемента, определения сопряжённости двух элементов, проблемы вхождения и др.) могут быть решены алгоритмами, работающими в логарифмическом пространстве за квазилинейное время. Более того, если рассматривать постановку проблемы в сжатом виде, причем каждое вхождение слова представлять как strait-line программу, то эти проблемы решаются за полиномиальное время. В [13] использование так называемых ТС0-схем позволило авторам понизить оценки сложности проблем. Наконец, в [14] авторы расширили список алгоритмических проблем для конечно порождённых нильпотентных групп, решаемых алгоритмами с низкой сложностью, включив в него ряд проблем для подгрупп. 3. Примеры криптографического анализа алгебраических схем с использованием метода нелинейного разложения 3.1. Пример 1 Опишем протокол распределения ключа Махалонобиса [2] - аналога классического протокола Масси - Омуры. Пусть G - группа и g Е G. Предположим, что Ф и Ф - два конечных подмножества группы автоморфизмов Aut(G), причём элементы из Ф попарно перестановочны с элементами из Ф. Пусть A и B - подгруппы группы Aut(G), порождённые множествами Ф и Ф соответственно. Алгоритм распределения ключа работает следующим образом: 1) Алиса выбирает случайный автоморфизм a Е A, вычисляет ga и посылает результат Бобу. 2) Боб выбирает случайным образом автоморфизм в Е B, вычисляет и посылает (ga)e Алисе. 3) Затем Алиса вычисляет a-1 и получает ((ga)e)а = ge. После этого она выбирает еще один случайный автоморфизм y Е A, вычисляет (ge )Y и передаёт его Бобу. 4) Боб находит в-1 и получает ключ K = ((ge)Y)в = gY. 5) Алиса в свою очередь, зная g и y, тоже вычисляет ключ K. Криптографический анализ. Заметим, что в алгоритме подгруппы A, B ^ ^ Aut(G) конечно порождены. Предположим, что для группы G эффективно решается проблема поиска вхождения элемента в подгруппу (vA), где v = (ga)e. Пусть известно, что подгруппа (vA) s-порождена для некоторого s. Замечание 2. В [2] в качестве платформы шифрования предлагается использовать конечно порождённую р-группу, более того, конечную р-группу специального вида. Приведённые условия криптографического анализа в этом случае выполнены. Значение оценочного параметра в оригинальном протоколе очевидно (в общем случае s не больше, чем полициклический ранг группы). Заметим также, что выше приведён несколько более общий вариант оригинального протокола: автор брал в качестве A и B общую коммутативную подгруппу S группы автоморфизмов Aut(G). Мы не даём и не используем детали выбора групп и автоморфизмов из [2], так как криптоанализ от них не зависит. Детали только упрощают его реализацию. Перейдём непосредственно к криптографическому анализу. По лемме 1 можно эффективно найти порождающее множество элементов для группы (vA). Обозначим эти элементы как (va1,... , vat). Далее отметим, что (ge)Y Е vA, поэтому можно найти его представление вида ge-Y = V (va1 ,...,vat), где V(x1,... , xt) -групповое слово от t переменных. Затем в правую часть данного представления вместо v = (ga)e подставим ga = (ga^e)e . Получим V ((ga)a1,..., (ga)at) = V ((ve-1 )a1,..., (ve-1 )at) = = V ((va1 )e-1,..., (vat )e-1) = (V (va1 ,...,vat ))e-1 = gY. Таким образом, не вычисляя ни один из закрытых элементов a, в и y, можно эффективно найти распределяемый (передаваемый) секретный элемент (ключ или сообщение) gY. Это означает, что данная схема является уязвимой. 3.2. П р и м е р 2 В качестве второго примера рассмотрим алгебраический аналог классического протокола Эль-Гамаля, использующий автоморфизмы. Имеется несколько алгебраических версий как самого протокола Эль-Гамаля, так и его обобщения - так называемой системы MOR, относительно которых см. [3, 4]. Алгебраическая версия системы Эль-Гамаля. Соглашения о группе G, элементе g e G и подгруппах A,B ^ Aut(G) те же, что и в предыдущем примере. Алгоритм работает следующим образом: 1) Алиса случайным образом выбирает автоморфизм a e A, вычисляет элемент ga и отправляет его Бобу. 2) Боб хочет послать сообщение m Алисе. Для этого он выбирает случайный автоморфизм в e B и посылает по сети сообщение (ge,m • ga'e). 3) После этого Алиса вычисляет элемент (ge)a = ga'e, находит к нему обратный и получает сообщение m = m • ga'e(g^e)-1. Криптографический анализ. Пусть для группы G эффективно решается проблема поиска вхождения элемента в подгруппу (gA). Тогда по лемме 1, аналогично примеру 1, найдём порождающее множество для группы (gA), скажем, {gai,... ,gak}. Из того, что Алиса выбирала автоморфизм a e A, следует, что ga e gA, а значит, можно найти представление этого элемента через порождающие: ga = V(gai ,...,gak). Заменив в правой части g на ge, получим V((ge)ai,..., (ge)ak) = V((gai)e,..., (gak)e) = (V(gai,... ,gak))e = . Далее, действуя аналогично Алисе, вычисляем обратный элемент к ga'e и расшифровываем сообщение m = m • ga'e (g"^)-1. Алгебраическая версия системы MOR. Пусть G = (g1,..., gn) - конечно порождённая группа. Алгоритм распределения ключа работает следующим образом: 1) Алиса выбирает случайный автоморфизм ^ e Aut(G) и случайное натуральное k число k, вычисляет значения gf и gf для i = 1,...,n, которые считаются открытыми. Другими словами, Алиса объявляет открытыми автоморфизмы ^ и . При этом k - закрытый параметр. 2) Боб хочет послать Алисе сообщение m, закодированное как элемент группы G. Для этого Боб выбирает случайное натуральное число /, вычисляет и посылает Алисе набор значений gf для i = 1,...,n, а также элемент mfkl. Другими словами, Боб посылает Алисе пару (^k,mf ). 3) Затем Алиса, зная k, вычисляет )-1 и раскрывает сообщение m, подействовав этим автоморфизмом на mf . Криптографический анализ. Повторяем рассуждения предыдущего криптоk l kl fk fl fkl графического анализа, позволяющие вычислить по значениям gi и gi значение gi для любого i = 1,... ,n. Тем самым мы найдём автоморфизм

Ключевые слова

криптография, криптоанализ, 'распределение ключа, нелинейное разложение, проблема поиска вхождения, cryptography, cryptanalysis, key exchange, nonlinear decomposition, membership search problem

Авторы

ФИООрганизацияДополнительноE-mail
Романьков Виталий АнатольевичОмский государственный университет им. Ф. М. Достоевскогодоктор физико-математических наук, профессор, заведующий кафедрой компьютерной математики и программированияromankov48@mail.ru
Обзор Анастасия АлександровнаОмский государственный университет им. Ф. М. Достоевскогостудентка кафедры компьютерной математики и программированияobzor2503@gmail.com
Всего: 2

Ссылки

Roman'kov V. A. A nonlinear decomposition attack // Groups Complexity Cryptology. 2017. V. 8. P. 197-207.
Mahalanobis A. The Diffie - Hellman key exchange protocol and non-abelian nilpotent groups // Israel J. Math. 2008. V. 165. P. 161-187.
Mahalanobis A. A simple generalization of El-Gamal cryptosystem to non-abelian groups // Communications in Algebra. 2008. V. 36. P. 3878-3889.
Mahalanobis A. A simple generalization of El-Gamal cryptosystem to non-abelian groups II // Communications in Algebra. 2012. V. 40. P. 171-186.
Романьков В. А. Введение в криптографию. Курс лекций. М.: Форум, 2012. 240 с.
Романьков В. А. Алгебраическая криптография. Омск: Изд-во ОмГУ, 2013. 135 с.
Романьков В. А. Криптографический анализ некоторых известных схем шифрования, использующих автоморфизмы // Прикладная дискретная математика. 2013. №3(21). С. 35-51.
Myasnikov A. G. and Roman'kov V. A. A linear decomposition attack // Groups Complexity Cryptology. 2015. V.7. P. 81-94.
Eick B. and Kahrobaei D. Polycyclic groups: A new platform for cryptology? arXiv math.: 0411.077v1 [math.GR].
Gryak K. J. and Kahrobaei D. The status of polycyclic group-based cryptography: A survey and open problems // Groups Complexity Cryptology. 2017. V. 8. P. 171-186.
Cavallo B. and Kahrobaei D. A family of polycyclic groups over which the conjugacy problem is NP-complete. arXiv math.: 1403.4153v2 [math. GR], 19 Mar 2014. P. 1-14.
Macdonald J., Miasnikov A., Nikolaev A., and Vassileva S. Logspace and compressed-word computations in nilpotentgroups. arXiv math.:1503.03888 [math.GR]. 2015.
Macdonald J., Miasnikov A., and Ovchinnikov D. Low-complexity computations for nilpotent subgroup theorem. arXiv math.: 1706.01092v2 [math. GR] 4 Jul 2017. 23 p.
Miasnikov A. and Weift A. TC0 circuits for algorithmic problems in nilpotent groups // 42nd Intern. Symp. MFCS. 2017. Article No. 23.
 Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/4

Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/4