ро-метод Полларда для дискретного логарифмирования

Не следует путать с ро-алгоритмом Полларда.

ρ-Метод Полларда для дискретного логарифмирования ($\rho$-метод) — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Предложен британским математиком Джоном Поллардом (англ. John Pollard) в 1978 году, основные идеи алгоритма очень похожи на идеи ро-алгоритма Полларда для факторизации чисел. Данный метод рассматривается для группы ненулевых вычетов по модулю $p$, где $p$ — простое число, большее $3$.

Постановка задачи дискретного логарифмирования

Для заданного простого числа $p$ и двух целых чисел $a$ и $b$ требуется найти целое число $x$, удовлетворяющее сравнению:

$a^{x}\equiv b\;{\pmod {p}},$

(1)

где $b$ является элементом циклической группы $G$, порождённой элементом $a$.

Алгоритм ро-метода

Рассматриваются последовательность пар $\{u_{i},\ v_{i}\}$ целых чисел по модулю $p-1$ и последовательность $\{z_{i}\}$ целых чисел по модулю $p$, определённые следующим образом:

$\{u_{i}\},\{v_{i}\},\{z_{i}\},\ i\in N,$

(2)

$u_{0}=v_{0}=0,\ z_{0}=1;$

$u_{i+1}={\begin{cases}u_{i}+1\;{\bmod {\;}}(p-1),&0<z_{i}<{\frac {p}{3}};\\2u_{i}\;{\bmod {\;}}(p-1),&{\frac {p}{3}}<z_{i}<{\frac {2}{3}}p;\\u_{i}\;{\bmod {\;}}(p-1),&{\frac {2}{3}}p<z_{i}<p;\end{cases}}$

(3)

$v_{i+1}={\begin{cases}v_{i}\;{\bmod {\;}}(p-1),&0<z_{i}<{\frac {p}{3}};\\2v_{i}\;{\bmod {\;}}(p-1),&{\frac {p}{3}}<z_{i}<{\frac {2}{3}}p;\\v_{i}+1\;{\bmod {\;}}(p-1),&{\frac {2}{3}}p<z_{i}<p;\end{cases}}$

(4)

$z_{i+1}\equiv b^{u_{i+1}}a^{v_{i+1}}{\pmod {p}}={\begin{cases}bz_{i}\;{\bmod {\;}}p,&0<z_{i}<{\frac {p}{3}};\\z_{i}^{2}\;{\bmod {\;}}p,&{\frac {p}{3}}<z_{i}<{\frac {2}{3}}p;\\az_{i}\;{\bmod {\;}}p,&{\frac {2}{3}}p<z_{i}<p.\end{cases}}$

(5)

Замечание 1: во всех выражениях рассматривается наименьшие неотрицательные вычеты.

Замечание 2: в более общем случае возможно разбиение на 3 подмножества несколько иным способом: разбиваем группу $G$ на три примерно равных по мощности подмножества $S_{1},S_{2},S_{3}$ так, чтобы $1$ не принадлежала подмножеству $S_{2}$.

Поскольку каждая треть отрезка, которой принадлежит элемент, вероятно, никак не связана с элементами последовательностей $\{u_{i},v_{i}\}$, полученная последовательность — псевдослучайная. Поэтому могут существовать такие числа $j$ и $k$, что $z_{k}=z_{j}$. Если удастся найти такую пару чисел, то получится:

$b^{u_{j}}a^{v_{j}}\equiv b^{u_{k}}a^{v_{k}}{\pmod {p}}.$

(6)

Если число $u_{j}-u_{k}$ взаимно простое с числом $p-1$, то это сравнение можно решить и найти дискретный логарифм:

$b^{u_{j}-u_{k}}\equiv a^{v_{k}-v_{j}}{\pmod {p}}.$

$x\equiv \log _{a}{b}\equiv (u_{j}-u_{k})^{-1}(v_{k}-v_{j}){\pmod {p-1}}.$

(7)

Если же наибольший общий делитель чисел $u_{j}-u_{k}$ и $p-1$ равен числу $d>1$, то существует решение этого сравнения для $x$ по модулю $(p-1)/d$. Пусть $x=x_{0}$ $(mod(p-1)/d)$, тогда искомое число $x=x_{0}+m(p-1)/d$, где $m$ может принимать значения $0,1,...,d-1$. Поэтому если $d$ — достаточно небольшое число, то задача решается перебором всех возможных значений для $m$. В худшем случае — когда $d=p-1$ — метод оказывается ничем не лучше полного перебора всех возможных значений для дискретного логарифма.

Для поиска индексов $j$ и $k$ используется алгоритм поиска циклов Флойда. При использовании данного алгоритма на $i$-м шаге имеются значения $(z_{i},\ u_{i},\ v_{i},\ z_{2i},\ u_{2i},\ v_{2i})$ и ищется номер $i$, для которого $z_{i}=z_{2i}$. Наименьшее значение $i$, при котором выполняется данное условие, называется епактой. Если при этом $(u_{2i}-u_{i},\ p-1)=1$, то

$x\equiv \log _{a}{b}\equiv (u_{2i}-u_{i})^{-1}(v_{i}-v_{2i}){\pmod {p-1}}.$

(8)

Pо-метод для группы точек эллиптической кривой

Пусть задана группа точек эллиптической кривой (ЭК) $E(F_{p})$. Не ограничивая общности, можно предположить, что $p>3$ и $p$ — простое число. Обозначим подгруппу $E(F_{p})$ порядка $n$ через $G$ и зафиксируем порождающий элемент $P$. Для произвольного элемента группы $Q=xP$ задача дискретного логарифмирования заключается в нахождении элемента $1<x<n.$

Группа $G$ представляется в виде объединения $G=S_{1}\cup S_{2}\cup S_{3}$, где $S_{i}$ — произвольные множества приблизительно одинаковой мощности. Функция итерирования $f\colon G\to G$ определяется как

$R_{i+1}=f(R_{i})={\begin{cases}Q+R_{i},&R_{i}\in S_{1};\\2R_{i},&R_{i}\in S_{2};\\P+R_{i},&R_{i}\in S_{3}.\end{cases}}$

(9)

Таким образом, $R_{i}=a_{i}P+b_{i}Q$, где коэффициенты определяются следующим образом

$a_{i+1}={\begin{cases}a_{i},&R_{i}\in S_{1};\\2a_{i},&R_{i}\in S_{2};\\a_{i}+1,&R_{i}\in S_{3};\end{cases}}$

(10)

$b_{i+1}={\begin{cases}b_{i}+1,&R_{i}\in S_{1};\\2b_{i},&R_{i}\in S_{2};\\b_{i},&R_{i}\in S_{3}.\end{cases}}$

(11)

Выбирая произвольное начальное значение $R_{0}$, строим две последовательности $R_{i}$ и $R_{2i}$, пока не будет обнаружена коллизия при некотором $m:R_{m}=R_{2m}$. Исходя из формул (10) и (11), решается задача дискретного логарифмирования:

$x={\frac {a_{2m}-a_{m}}{b_{m}-b_{2m}}}.$

(12)

Важно то, что полученное значение при коллизии $m$ зависит от начального значения $R_{0}$ и определяет вычислительную сложность метода Полларда.

Сложность алгоритма

Основная работа алгоритма состоит в вычислении последовательностей $\{x_{i}\},\{x_{2i}\}$. Данные вычисления требуют трех умножений по модулю для перехода к следующей итерации. Размер необходимой памяти при этом минимален, поскольку нет необходимости хранения информации о всех предыдущих элементах последовательностей. Таким образом, сложность алгоритма сводится к сложности задачи нахождения епакты, которая, в свою очередь, имеет эвристическую оценку сложности $O({\sqrt {p}})$, причем для разных случаев значения константы $C{\sqrt {p}}$ могут довольно сильно отличаться, но, как правило лежат в пределах $[1;3]$.

Сравнение с другими алгоритмами

По сравнению с другими алгоритмами дискретного логарифмирования алгоритм $\rho -$Полларда является менее затратным как по отношению к бинарным операциям, так и по отношению к необходимому количеству памяти. Например, при достаточно больших значениях числа $p$ данный алгоритм является более эффективным по сложности, чем алгоритм COS и алгоритм Адлемана, имеющие сложность $O(exp{((\log {p}\log {\log {p}})^{1/2})})$. В сравнении с алгоритмом Шенкса, также имеющим сложность $O({\sqrt {p}})$, алгоритм Полларда является более выгодным по отношению к используемой памяти — для алгоритма Шенкса требуется $O(p)$ памяти, в то время как для данного алгоритма размер требуемой памяти постоянен (при условии использования алгоритма поиска циклов Флойда).

Распараллеливание метода

Системы с распределённой памятью

Идея метода $\rho -$Полларда для систем с распределённой памятью состоит в разделении итерирования точек между клиентскими рабочими станциями и поиска коллизии сервером. Пусть задано множество клиентских рабочих станций $S=\left\{S_{i}\mid i=1...r\right\}.$ Сервер определяет параметры, общие для системы, некоторое подмножество$D\subset G$ и выполняет инициализацию рабочих станций. Клиентская рабочая станция $S_{i}$ строит последовательность точек $R_{ij}\subset D$ и отправляет поэлементно точки на сервер. Если точка не содержится в базе данных, сервер добавляет точку в базу данных, иначе вычисляет значение дискретного логарифма.

Системы с общей памятью

Идея такого метода состоит в распараллеливании отдельно функции итерирования и алгоритма обнаружения коллизии. Функция итерирования распараллеливается на этапе вычисления последовательностей $R_{i}$ и $R_{2i}$. Следует отметить, что параллельное вычисление$R_{i_{0}}$ и $R_{2i_{0}}$ для фиксированного значения $i_{0}$ и последующее сравнение является неэффективным. Это объясняется тем фактом, что накладные расходы, связанные с использованием потоков, являются вычислительно более затратными, чем вычисление $R_{2i_{0}}=f(R_{2i_{0}-2})$.Таким образом, целесообразно вычислять последовательности так, чтобы накладные расходы нивелировались. Это может быть достигнуто организацией вычислений последовательностей вида $\left\{R_{iw+j}\right\}_{i=0}^{l}$ и $\left\{R_{2(iw+j)}\right\}_{i=0}^{l}$, где $w$ — размер блока вычислений, $0\leqslant j<w,l=\left\lceil {\frac {m}{w}}\right\rceil$. Функция обнаружения коллизии в методе $\rho -$Полларда сравнивает значения $R_{m}$ и $R_{2m}$. Такое сравнение можно распараллелить, если использовать алгоритм итерирования для систем с общей памятью. Результатом выполнения функции итерирования точек являются два множества точек $\left\{R_{i}\right\}_{i=0}^{w}$ и $\left\{R_{2i}\right\}_{i=0}^{w}$,сравнение которых осуществляется по блокам, то есть $R_{i}=R_{2i},i=1...{\frac {w}{2}}$ и $R_{i}=R_{2i},i={\frac {w}{2}}...w$ в случае с двумя ядрами.

Комбинированный метод

Метод $\rho -$Полларда для систем с распределённой памятью может быть расширен для использования на многоядерных рабочих станциях. Идея метода состоит в том, что итерирование точек клиентскими рабочими станциями происходит в соответствии с определенным алгоритмом, суть которого в том, что есть клиентская рабочая станция $S_{i}$ строит последовательность точек $\left\{R_{ij}\right\}_{j=0}^{w}$. Далее рабочая станция $S_{i}$ выбирает подмножество точек $\left\{R_{ij}\right\}_{j=0}^{w}\cap D$ и отправляет его серверу. Проверка на принадлежность подмножеству осуществляется в параллельном режиме: $R_{ij}\in D,i=1...{\frac {w}{2}}$ и $R_{ij}\in D,i={\frac {w}{2}}...w$ (в случае с двумя ядрами). Сервер добавляет точки и $\left\{R_{ij}\right\}_{j=0}^{w}\cap D$ в базу данных до тех пор, пока не найдет уже существующую точку.

Модификации и оптимизации

Существует несколько значительных улучшений алгоритма, основанных на различных приемах.

Одно из улучшений описано в работе [Teske 1998]. Отличие приведенного в работе метода заключается в усложненной итерационной функции — она содержит 20 различных веток вместо описанных выше трех. Численные эксперименты показывают, что такое улучшение приводит к ускорению работы алгоритма случайного блуждания в среднем на 20 %.

Λ-метод Полларда

В работе по вычислению дискретных логарифмов Поллардом также был предложен $\lambda -$метод, названный так потому, что форма греческой буквы напоминает изображение двух путей, соединяющихся в один. Идея метода состоит в том, чтобы идти сразу двумя путями: одним от числа $b$, чей дискретный логарифм надо найти, другим от числа $B$, чей дискретный логарифм уже известен. Если эти два пути сойдутся, появляется возможность найти дискретный логарифм числа $b$. Поллард предложил рассматривать шаги на каждом пути как прыжки кенгуру, поэтому этот алгоритм иногда называют «методом кенгуру». Если известно, что искомый дискретный логарифм лежит в некотором коротком интервале, то можно адаптировать метод кенгуру, а именно, использовать кенгуру с более короткими прыжками.

Одним важным свойством лямбда-метода является тот факт, что он легко распределяется на несколько компьютеров. Каждый участник распределённых вычислений выбирает случайное число $r$ и начинает делать псевдослучайные шаги от числа $b^{r}$, где $b$ — элемент группы, для которого ищется дискретный логарифм. Каждый участник использует одну и ту же легко вычислимую псевдослучайную функцию $f\colon G\to S$, где $S$ — относительно небольшое множество чисел со средним значением, сравнимым с размером группы $G$, имеющей порядок $n$. Степени $a^{s}$ для $s\in S$ вычисляются заранее. Тогда «блуждание», начиная с элемента $b^{r}$, принимает вид: $w_{0}=b^{r},w_{1}=w_{0}a^{f(w_{0})},w_{2}=w_{1}a^{f(w_{1})},...$

Пусть другой участник, выбрав начальное число $r^{\prime }$ , получил последовательность $w_{0}^{\prime },w_{1}^{\prime },w_{2}^{\prime },...$ Если она пересекается с последовательностью $w_{0},w_{1},w_{2},...$, то есть $w_{i}^{\prime }=w_{j}$ при некоторых $i,j$, то, учитывая, что $b=a^{x}$, выполняется:

$b^{r^{\prime }}a^{f(w_{0}^{\prime })+f(w_{1}^{\prime })+...+f(w_{i-1}^{\prime })}=b^{r}a^{f(w_{0})+f(w_{1})+...+f(w_{j-1})},$

(13)

$(r^{\prime }-r)x\equiv \sum _{\mu =0}^{j-1}{f(w_{\mu })}-\sum _{\nu =0}^{i-1}{f(w_{\nu }^{\prime })}{\pmod {n}}.$

(14)

Обычно этот метод используется, когда порядок группы $n$ является простым. Так как тогда, если все выбираемые в начале вычислений числа $r$ различны по модулю $n$, то сравнение $(14)$ может быть легко решено для нахождения дискретного логарифма $x$. Небольшая трудность заключается в том, что совпадение может произойти внутри одной последовательности, это означает, что $r=r^{\prime }$. Однако, если количество участников вычислений достаточно велико, то вероятность совпадения между последовательностями больше, чем вероятность совпадения внутри одной последовательности.

Возможно использование псевдослучайной функции (5). В таком случае будут полезны все совпадения: совпадение внутри одной последовательности также может быть использовано для вычисления дискретного логарифма. В случае такого совпадения $\Lambda -$метод просто превращается в $\rho -$метод. Однако, если известно, что искомый дискретный логарифм лежит в коротком интервале, то можно использовать первоначальный метод. Тогда время работы будет около квадратного корня из длины интервала. В этом случае среднее значение целых чисел из множества $S$ должно быть меньше для того, чтобы «кенгуру» прыгали только по интервалу нужной длины.

Центральный компьютер должен отслеживать все последовательности от всех участников для выявления совпадений. Согласно парадоксу дней рождения, совпадение ожидается, когда количество элементов во всех последовательностях будет порядка $O({\sqrt {n}})$. Очевидно, что в описанном виде этот метод требует больших затрат памяти центрального компьютера. Следующая идея, описанная в работе ван Оршотом, сильно уменьшает требования к памяти и, таким образом, делает этот метод применимым к решению сложных проблем. Идея состоит в рассмотрении так называемых выделенных точек. Предполагается, что элементы группы представляются целыми числами (или, возможно, наборами целых чисел). Выделенное двоичное поле длины $k$ в таком числе будет состоять из одних нулей примерно $1/2k$-ю часть всего времени. Случайное блуждание будет проходить через такие выделенные точки в среднем через каждые $2^{k}$ шагов. Если две случайные последовательности где-нибудь пересекутся, то они будут пересекаться и дальше и вместе попадут в следующую выделенную точку. Итак, идея состоит в отправке на центральный компьютер только этих выделенных точек, что уменьшит необходимый размер памяти в $2^{k}$ раз.

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 328. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты. — М.: УРСС, 2011 — С.664. — ISBN 978-5-453-00016-6
• Pollard J. M. Monte Carlo methods for index computation (mod p). Mathematics of Computation — 32 (143), 1978—918—924 — JSTOR 2006496
• Teske, Speeding up Pollard’s rho method for computing discrete logarithms. Algorithmic Number Theory Symposium (ANTS IV), 1998—541—553
• Горбенко И. Д., Качко Е. Г. Методы распараллеливания алгоритма Полларда решения задачи дискретного логарифмирования для систем с общей памятью — 2012
• van Oorschot P.C., Wiener M.J. Parallel collision search with cryptanalytic applications — Journal of Cryptology 12 (1) — 1-28 — 1999