Участник:Kosean97/Метод встречи посередине в решении задачи дискретного логарифмирования в группе точек эллиптической кривой

Алгоритм: Применение метода встречи посередине в решении задачи дискретного логарифмирования в группе точек эллиптической кривой
Автор описания: Конюхов Сергей

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования. Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем и Виктором Миллером в 1985 году.

1 Свойства и структура алгоритма

Задача дискретного логарифмирования в общем виде заключается в поиске решения [math]g^x=a[/math] в некоторой конечной абелевой группе [math]G[/math].

Мы же рассмотрим группу точек эллиптической кривой над полем [math]{\mathbb Z}_p[/math] характеристики [math]p \gt 3[/math]:

[math]E( {\mathbb Z}_p ) = {\mathcal O} \cup \{ (x, y) \in {\mathbb Z}_p^2 \enspace|\enspace y^2 \equiv x^3 + Ax + B \enspace (mod \thinspace p) \}[/math], где [math]A, B \in {\mathbb Z}_p[/math] - константы, удовлетворяющие условию [math]4A^3+27B^2 \ne 0 \enspace (mod \thinspace p)[/math].

В качестве группы [math]G[/math] возьмём циклическую подгруппу группы [math]E( {\mathbb Z}_p )[/math] порождённую элементом [math]Q[/math], то есть [math]G=\langle Q \rangle[/math].

Стоит отметить, что группа [math]G[/math] является аддитивной, и задачу DLOG стоит переформулировать: в уравнении [math]nQ=P[/math] требуется найти [math]n[/math].

1.1 Общее описание алгоритма

Метод "встречи посередине" является вероятностным и основан на так называемом парадоксе дней рождений - для того, чтобы при выборке с возвратом из множества мощности [math]r[/math] получить совпадение двух элементов с достаточно большой вероятностью, требуется произвести [math]\sqrt{r}[/math] попыток.

Eсли мы найдем совпадение точек вида: [math]lQ = kP[/math], то мы можем получить решение задачи как [math]n=lk^{-1}\enspace (mod \thinspace r)[/math].

1.2 Математическое описание алгоритма

[math]G = \langle Q \rangle[/math], [math]|G| = r[/math] - циклическая подгруппа группы точек эллиптической кривой. Уравнение [math]nQ = P[/math].

Дано: [math]E, Q, P, r[/math] - эллиптическая кривая, образующая группы [math]G[/math], логарифмируемый элемент, порядок группы.

Найти: [math]n[/math] - искомый логарифм.

Алгоритм:

1. Случайно выбрать [math]\sqrt{r}[/math] чисел [math]l_i \in {\mathbb Z}_r[/math] и сохранить точки вида [math]l_iQ[/math].
2. Отсортировать полученные на предыдущем этапе точки по координате [math]x[/math].
3. Для случайных [math]k_j \in {\mathbb Z}_r[/math] вычислить точки [math]k_jP[/math] и осуществить поиск на совпадение в сохранённом массиве.
4. В случае успеха вычислить [math]n=l_ik_j^{-1}\enspace (mod \thinspace r)[/math]. В случае провала перейти к пункту 3.

1.3 Вычислительное ядро алгоритма

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

1. Генерация базы данных.
   Выбирается некоторый "квант" - число точек - степеней образующей, которые будут генерироваться за одну итерацию. До тех пор пока не наберётся достаточное количество точек, генерируем "квант" случайных точек. Генерация точек осуществляется следующим образом: выбирается псевдослучайное число, после чего образующая умножается на него.
2. Сортировка базы данных.
   Полученная база точек - степеней образующей сортируется по икс-координате (точка А больше точки Б, если икс-координата точки А больше икс-координаты точки Б). Алгоритм сортировки, например, быстрая сортировка.
3. Генерация и поиск.
   Генерируется "квант" точек - степеней изучаемой точки. После чего производится поиск в базе данных точки, обладающую той же икс-координатой, что и выбранная. Поиск осуществляется, например, бинарным поиском.

1.4 Макроструктура алгоритма

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

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

1.5 Схема реализации последовательного алгоритма

В качестве описания схемы реализации последовательного алгоритма можно привести данный фрагмент программы на языке С++.

int main( int argc, char** argv )
{
     // Определяем группу, исследуемый элемент,
     // а так же объем базы данных точек и количество точек,
     // генерируемых за один раз, цель исследования.
     DLogConfig config( "config.txt" );
     DLogSolver solver( &argc, &argv, config );

     do
     {
          // Сгенерировать некоторое количество точек - степеней образующей.
          solver.GenerateDatabase();
     }
     // До тех пор, пока нужное количество точек не будет создано.
     while( !solver.DatabaseFull() );
     // Сортировка полученной базы данных.
     solver.PrepareDatabase();
     
     do
     {
          // Сгенерировать некоторое количество точек - степеней исследуемого элемента.
          solver.GeneratePoints();
          // Поиск совпадений в базе данных.
          solver.LookThrowDatabase();
     }
     // Повторять до тех пор, пока совпадение не будет найдено.
     while( !solver.SolutionFound() );
     // Вывести ответ.
     solver.PrintAnswer();

     return EXIT_SUCCESS;
}

1.6 Последовательная сложность алгоритма

Будем считать генерацию точки за элементарную операцию. Сложность этапа генерации базы точек есть [math]\sqrt{r}[/math], так как точки хранятся в связном списке, добавление составляет константную сложность. Сортировка производится алгоритмом Q-Sort, тем самым будет выполнено порядка [math]\sqrt{r}\log r[/math] операций. Поиск по созданной базе точек осуществляется алгоритмом бинарного поиска, таким образом, проверка на вхождение нужного элемента производится за [math]\log r[/math] операций.

Таким образом:

• временная сложность алгоритма есть [math]\sqrt{r}\log r[/math],
• оценка используемой памяти есть [math]\sqrt{r}[/math],

где [math]r[/math] - это порядок группы [math]G[/math] точек эллиптической кривой.

1.7 Информационный граф

Рис.1. Информационная структура алгоритма дискретного логарифмирования методом встречи посередине.

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