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

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

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов<ref name="VASYA">Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. Изд. 2-е. доп. - М.: МЦНМО, 2006. - 336 с.</ref> решения задачи дискретного логарифмирования. Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем и Виктором Миллером в 1985 году.

= Свойства и структура алгоритма =
Задача дискретного логарифмирования<ref name="PRIM">Применко Э.А. Алгебраические основы криптографии: Учебное пособие. Изд. 2-е, испр. - М.: ЛЕНАНД, 2015. - 288 с.</ref> в общем виде заключается в поиске решения <math>g^x=a</math> в некоторой конечной абелевой группе <math>G</math>.

Мы же рассмотрим группу точек эллиптической кривой над полем <math>{\mathbb Z}_p</math> характеристики <math>p > 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>.

== Общее описание алгоритма ==
Метод "встречи посередине"<ref name="BABE">Бабенко Л.К., Ищукова Е.А., Сидоров И.Д. Параллельные алгоритмы для решения задач защиты информации. - М.: Горячая линия - Телеком, 2014. - 304 с. </ref> является вероятностным и основан на так называемом парадоксе дней рождений - для того, чтобы при выборке с возвратом из множества мощности <math>r</math> получить совпадение двух элементов с достаточно большой вероятностью, требуется произвести <math>\sqrt{r}</math> попыток.

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

== Математическое описание алгоритма ==
<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> - искомый логарифм.

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

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

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

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

== Схема реализации последовательного алгоритма ==
В качестве описания схемы реализации последовательного алгоритма можно привести данный фрагмент программы на языке С++.
<source lang="c">
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;
}
</source>

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

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

[[file:dlog_graph.jpg|thumb|right|300px|Рис.1. Информационная структура алгоритма дискретного логарифмирования методом встречи посередине.]]

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

== Ресурс параллелизма алгоритма ==
<!-- Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах. 

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне  может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения. -->

== Входные и выходные данные алгоритма ==
<!-- В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие. -->

== Свойства алгоритма ==

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
<!-- Задача данного раздела - показать пределы [[глоссарий#Масштабируемость|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость|''сильной'']] и [[глоссарий#Слабая масштабируемость|''слабой'']] масштабируемости алгоритма и его реализаций.

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

Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи <ref>Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.</ref>. При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.

На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.
[[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рис.5 Масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи]] -->

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

= Литература =
<references />

[[en:Description of algorithm properties and structure]]