Discrete logarithm problem in subgroups of prime order.pdf Во многих криптосистемах, например в протоколах идентификации Окамото,Шнорра, в протоколе цифровой подписи Шаума - ван-Антверпена, в хэш-функцииCvHP, в американском стандарте цифровой подписи DSS и других, вычисления выполняютсяв некоторой подгруппе (как правило, простого порядка) мультипликативнойгруппы Z*. Соответственно стойкость таких криптосистем полагается на сложностьзадачи дискретного логарифмирования в подгруппах.Пусть p - простое число, q - простой делитель p - 1, G - циклическая подгруппапорядка q группы Z*, а - порождающий элемент G. Тогда задача дискретногологарифмирования в G заключается в следующем: для данных p, q, а и элементаb Е G требуется найти единственное целое х, 0 ^ х ^ q - 1, такое, что ax = b(modp).Обсудим возможности применения известных алгоритмов логарифмирования [1] длярешения этой задачи.Алгоритм Гельфонда (baby-step giant-step algorithm) и p-метод Полларда особенностигруппы никак не учитывают; их работоспособность зависит только от того, наскольковелик её порядок, и время работы составляет O(^/q). Таким образом, эти алгоритмымогут применяться для логарифмирования в группе G без каких-либо измененийи с тем же успехом, что и в других группах порядков, приблизительно равных q. АлгоритмПолига - Хеллмана совершенно неприменим для логарифмирования в группепростого порядка, так как в этом случае его работа сводится к полному перебору всехвозможных значений логарифма. Алгоритм Адлемана (index calculus algorithm) имеетсложность O(c(lnp)1/2); одним из его шагов является решение системы сравнений помодулю порядка группы. Поэтому алгоритм Адлемана кажется наиболее пригоднымдля логарифмирования в группе простого порядка, так как в этом случае приходитсярешать систему уравнений над полем, а не над кольцом, что много проще. Основнаяидея алгоритма состоит в том, что в группе G выбирается некоторое подмножествоэлементов S , называемое факторной базой, и сначала определяются логарифмы элементовэтого подмножества. Затем с их помощью вычисляется искомый логарифм.Алгоритм 1 (Адлемана)Вход: G = < а >, |G| = n, b Е G.Выход: х = loga b.1. Выбираем факторную базу S = {p1,p2, ... ,pt}.2. Ищем значения ak, разложимые в базе S; для этого:2.1. Выбираем случайное k, 0 < k < n, и вычисляем у = ak.t2.2. Ищем разложение у = П p^; в случае успеха составляем линейное сравнениеj=1te ■ Xj = k(mod n).i=12.3. Шаги 2.1 и 2.2 повторяем до тех пор, пока не получим систему сравнений,имеющую единственное решение.3. Решая полученную на шаге 2 систему сравнений, находим значения xi для всехi = 1 ,..., t.4. Ищем х = loga b; для этого:4.1. Выбираем случайное k, 0 ^ k < n, и вычисляем у = b ■ ak.t4.2. Ищем разложение у = П p^; в случае успеха находимi=1 itх = YI e ■ Xj - k(mod n), иначе возвращаемся к п. 4.1.i=15. Ответ: х.Нетрудно видеть, что если S С G, то получаемые в шаге 3 значения хг - это иесть логарифмы элементов факторной базы S: хг = logapj; корректность вычислениях = loga b в этом случае очевидна. Если G = Zp, то в качестве S рекомендуется братьмножество из t первых простых чисел. Если же G С Zp, то выбор факторной базыс условием S С G представляет собой определённую проблему, ведь не обязательно всепервые простые числа принадлежат G. В работе [2] предлагается выбирать факторнуюбазу S С Zp, не обязательно S С G. При условии p = q ■ s + 1, где (q, s) = 1, алгоритм 1остаётся работоспособным, даже если S С G.Утверждение 1. Пусть p = q ■ s + 1, где p простое и (q, s) = 1, G - подгруппаZp порядка q. Алгоритм 1 корректно решает задачу дискретного логарифмированияв группе G при выборе любого непустого подмножества Zp\{1} в качестве факторнойбазы.Доказательство. Заметим, что группа G есть множество всех вычетов степениs по модулю p, т. е. множество тех и только тех элементов группы Zp, логарифмыкоторых по основанию g кратны s.tРассмотрим разложение akmodp = П p^. Пусть s' = s-1 mod q. Тогда as^s =i=1 ( t V s/ t , e . = a(modp) и ak = as^ k = I П p? ) = П (pfs') * (modp). Поскольку p| G G, то\i=1 J i=1и pfs G G. Следовательно, существует xi = loga pfs ; именно это значение и будетнайдено в шаге 3 алгоритма Адлемана при решении системы сравнений. Для шага 4' ( t \ s проведём те же рассуждения: y G G, откуда ys^s = y(modp), b ■ ak = I П p? ) s/ =t / t t= П (pfs ) " (mod p). Тогда loga b = ^ ei ■ loga pfs - k(mod q) = ^ ei ■ xi - k(mod q). ■i=1 i=1 i=1Присмотримся к элементу pfs , логарифм которого вычисляется в шаге 3 алгоритма.Составим и решим сравнениеys = ps (mod p).Получаем s ■ log y = s ■ log pi (mod p - 1),log y = log pi(mod q),log y G {log pi, log pi + q,... , log pi + (s - 1) ■ q},y G Y = {pi,pi ■ gq,. . . ,pi ■ g(s-1>q} = {glogpi+q4 : t = 0, . . . , s - 1}.Множество Y - это все корни s-й степени из p|. Здесь t пробегает полную системувычетов по модулю s и (q, s) = 1, значит, и logpi + q ■ t также пробегает полнуюсистему вычетов по модулю s. Поскольку единственный из показателей logpi + q ■ t кратенs, то один и только один элемент из Y , а именно pfs , принадлежит G. Другимисловами, при решении системы сравнений в шаге 3 алгоритма 1 в качестве значенияпеременной xi будет вычислен логарифм того корня s-й степени из p|, который принадлежитG. В случае, если s = 2k (в частности, если p - надёжное простое число; тогдаs = 2), можно расширить факторную базу S без увеличения количества переменных.А именно: для каждого pi G S вычисляем все корни s-й степени из p| по модулю p(это можно сделать, так как вычисление квадратных корней по простому модулю -лёгкая задача) и включаем их в факторную базу, сопоставляя всем им одну и ту жепеременную.Для сравнения заметим, что, например, «Handbook of Applied Cryptography» [1]предлагает решать задачу дискретного логарифмирования в подгруппе простого порядкаследующим образом.Пусть Zp = < g >, p = q ■ s + 1, q простое, G = < a > - подгруппа Zp порядка qи b G G. С помощью алгоритма Адлемана найдём y = logg a и z = logg b в Zp. В силуравенств aq = g^q = 1(mod p) и Op(g) = p - 1 = q ■ s выполняется условие (q ■ s)|(y ■ q),т. е. s|y. Аналогично, ввиду b G G, верно, что s|z. Пусть y = s ■ y1, z = s ■ z1. Запишем:aZl = g^zi = gyr^zi = gyrz = byi(modp), откуда получаем х = logab = z1 ■ y - 1modq.Здесь y - 1mod q всегда существует в силу условия 0 < у1 < q.При таком подходе нужно дважды решать задачу логарифмирования в Z*, чтопредполагает решение двух систем линейных уравнений над кольцом, в то время какв методе [2] решается одна система линейных уравнений над полем. Что касается ограничения(q, s) = 1, то это условие автоматически выполнено, если простое p построенометодом Маурера (так как в этом случае s < q), и выполнено с вероятностью (q - 1)/q,если p построено по алгоритму ГОСТ (поскольку s - случайное число в некоторомдиапазоне, в котором каждое q-е число кратно q). Таким образом, в большинстве случаевзадачу логарифмирования в числовой группе G простого порядка можно решатьметодом Адлемана, не требуя выбора факторной базы как подмножества G.

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