Александр Цихилов - Блокчейн. Принципы и основы

целым остатком. Подобную арифметическую операцию проходят в младших

классах школы, непосредственно перед изучением дробей. После чего про

деление с остатком благополучно забывают и не вспоминают до

университетского курса высшей математики. Где неожиданно выясняется, что

деление с остатком на самом деле играет довольно важную роль в теории

чисел и алгебре. В нашем примере мы должны определить, в какую степень

нам надо возвести тройку, чтобы потом, разделив полученный результат по

модулю на 17, получить число 13 в качестве остатка от деления. Правильный

ответ: x = 4. То есть 34 = 81, 81/17 = 4 + остаток 13 (проверка: 4 x 17 = 68 + 13 =

81). Довольно просто, не правда ли? Возводя тройку в различные степени x от

единицы и более, а затем деля по модулю полученный результат на 17, мы

будем каждый раз получать различные остатки от деления. Однако у них будет

одно общее свойство — все эти остатки будут находиться в диапазоне от 1 до

16 включительно, но выстраиваться отнюдь не по порядку (по мере

последовательного возрастания степени x). Множество этих чисел называется

кольцом вычетов. Кольцом, потому что остатки будут постоянно повторяться

для разных показателей степени, в которую возводится базовое число. А

теперь представим, что мы оперируем не одно-двухразрядными, а очень

большими числами. В этих случаях, если степень заданного числа нам заранее

неизвестна, то задача ее нахождения для конкретных величин остатков

становится очень и очень сложной. Именно эта сложность и лежит в основе

алгоритма DSA.

Как уже упоминалось выше, все подобные алгоритмы шифрования построены

на принципе, при котором задача в одну сторону решается очень быстро и

просто, а в обратную — исключительно сложно. И алгоритм DSA — не

исключение. Если мы будем решать задачу для больших чисел путем простого

перебора различных значений, то данный метод будет работать очень

медленно. Поэтому вместо обычного перебора были разработаны алгоритмы, которые решают эту задачу гораздо эффективнее. Настолько эффективно, что, принимая во внимание постоянное увеличение производительности

современных компьютеров, математики вынуждены были задуматься о

необходимости повышения сложности алгоритма шифрования. В противном

случае они могли бы столкнуться с проблемой массового взлома шифров уже в

относительно недалеком будущем.

Чтобы придать задаче существенное усложнение, в 1985 году был разработан

алгоритм дискретного логарифмирования на базе эллиптических кривых

(алгоритм ECDSA). О чем в данном случае идет речь и что это за кривая?

Эллиптическая кривая — это множество точек, описываемое уравнением y2 =

x3 + ax + b. То есть, по сравнению с алгоритмом DSA, операции совершаются

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

открытого. Вот пример обычной эллиптической кривой:

На множестве точек эллиптической кривой могут выбираться такие точки, для

которых возможно совершить операцию сложения самих с собой и получить

результат в виде другой точки на этой же кривой. То есть решить

уравнение X = nP, где n = 2 и более, а X и P являются точками на данной

кривой с координатами по осям x и y. Умножение на константу n есть не что

иное, как операция последовательного сложения n раз. Таким образом, мы

начинаем с того, что нам необходимо сложить начальную точку с ней же самой

и получить результат в виде такой же точки, но уже с новыми координатами.

Геометрически операция сложения точки эллиптической кривой с самой собой

представляет построение касательной к данной точке. Затем мы находим точку

пересечения касательной с графиком кривой и строим от нее вертикальную

прямую, находя таким образом точку ее пересечения на обратной стороне

кривой. Эта точка и будет результатом сложения. Вот как выглядит операция

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

Именно от нее мы строим новую касательную, и так далее — n раз. Сложность

задачи состоит в обратном поиске n для известных точек X и P, и эта задача не

имеет быстрого решения. В данном случае n будет закрытым ключом, а X —

открытым. Понятно, что компьютер при расчетах осуществляет операцию