Контрольные задания

1. Перечислите различия между собственноручной подписью и ЭЦП.

2. Укажите основное отличие российского и американского стандартов ЭЦП.

3. Пусть порядок кривой является произведением маленьких простых чисел. Предложите атаку на алгоритм подписи для этого случая.

Глава3 . Аспекты практической реализации криптографических алгоритмов на эллиптических кривых

§ 1. Эффективная реализация элементарных операций

Рассмотрим основной подход, обычно необходимый для эффективной реализации операций на эллиптической кривой. Как уже говорилось, вычисление кратной точки kP (k – большое число) осуществляется с помощью тех же методов, которые используются для возведения в степень по модулю (умножение в них заменяется сложением точек). Здесь для конкретности мы все же опишем наиболее простой алгоритм, использующий разложение k по степеням числа 2 (т. е. его побитовое представление). В литературе описаны более эффективные методы возведения в степень, которые с успехом могут быть применены и для вычисления композиций на эллиптических кривых. Эти методы обычно дают несущественный выигрыш во времени (порядка 25 %), и их описание выходит за рамки нашей книги.

Алгоритм 1. Вычисление кратной точки kP.

Вход: Точка P, число (двоичное представление числа k).

Выход: Q = kР.

Шаг 1. Q ← 0;

Шаг 2. FOR i = DO

Q ← 2Q;

IF THEN Q ← Q + P END;

END;

Шаг 3. RETURN Q.

Здесь и далее стрелка ← означает операцию присваивания переменной определенного значения.

Данный алгоритм требует не более t сложений и t удвоений точек (в среднем t удвоений и t/2 сложений).

Пример 21. Проиллюстрируем работу алгоритма на примере вычисления точки 29Р. Здесь 29 = (11101)₂, t = 5. Покажем, что происходит на каждой итерации цикла алгоритма:

[i = 5 m₅ = 1] : Q ← 0, Q ← Q + P = P;

[i = 4m₄ = 1] : Q ← 2Q = 2P, Q ← Q + P = 3P;

[i = 3m₃ = 1] : Q ← 2Q = 6P, Q ← Q + P = 7P;

[i = 2m₂ = 0] : Q ← 2Q = 14P;

[i = 1m₁ = 1] : Q ← 2Q = 28P; Q← Q + P = 29P.

Кратная точка вычислена с применением 5 умножений и 4 сложений точек.

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

Удвоенная точка вычисляется с помощью формул

Говорят, что при вычислениях по данным формулам используется аффинное представление для точек, т. е. точка P представлена в виде . Точка в бесконечности 𝒪 не имеет такого представления. Фактически в алгоритме 1 она является просто «флажком», показывающим, что нужно пропустить операции удвоения Q ← 2Q до первого сложения Q ← Q + P, которое выполняется как простое присваивание Q ← P.

Обозначим через М и I стоимость (время) умножения и ин­версии по модулю р. Тогда из приведенных формул сложения и удвоения точки следует, что при аффинном представлении стоимость сложения точек равна I + 3М, а стоимость удвоения равна I + 4М (операции сложения и умножения на маленькие коэффициенты заметного влияния на время вычисления не оказывают).

Соотношение стоимости инверсии и умножения может быть раз­личным в зависимости от реализации, но I всегда больше М. Если умножение реализуется за счет сложений и сдвигов, то оно, вероятнее всего, будет незначительно (в 2–3 раза) опережать инверсию. В этом случае использование аффинного представления для точек на кривой вполне оправдано. Однако если процессор, на котором выполняются вычисления, имеет встроенный параллельный умножитель (как большинство современных процессоров общего назначения), то инверсия будет вычисляться существенно медленнее произведения. Можно дать грубую оценку стоимости соответствующих вычислений. Если t – длина чисел в битах, то умножение потребует порядка машинных операций (в данном случае 32 бита – размер машинного слова). С другой стороны, количество итераций в обобщенном алгоритме Евклида, вычисляющем инвер­сию, пропорционально t по своей природе. Даже если мы сможем на каждой итерации реализовать линейные по t вычисления с помощью 32-битовых машинных операций (что возможно), мы получим общую трудоемкость порядка , т. е. одна инверсия будет соответствовать тридцати двум умножениям. В действительности на каждой итерации алгоритма Евклида нужно делать несколько операций, а умножение может быть реализовано более быстрыми методами, так что I > 32М.

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

В этом случае точка на кривой представляется тройкой и говорят о переходе к взвешенному проективному представлению (далее для простоты будем опускать слово «взвешенное»). Переход от аффинной точки к проективной делается очень просто:

После этого все вычисления проводятся в проективных координатах (без вычисления инверсий). Обратный переход от проективного к аффинному представлению осуществляется следующим образом:

и «стоит» оно I + 4М (одно вычисление инверсии , два умножения для получения и и, наконец, два умножения и .

Получим формулы для сложения точек в проективном представ­лении. Вначале в формуле сложения для произведем замену пере­менных. После приведения к общему знаменателю и сокращения дроби получим

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

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

На основании выражений для и запишем следующий алгоритм.

Алгоритм 2. Сложение точек в проективном представлении.

Вход:

Выход:

Все вычисления выполняются по модулю p.

.

Как видно из описания алгоритма, трудоемкость сложения в проективных координатах равна 16М. Мы не учитываем простые операции сложения, вычитания, а также умножения и деления на 2. Чтобы пояснить, как вычисляется , заметим, что если четное, то (сдвиг вправо на один бит); если нечетное, то , четное, поэтому . Если одна из точек, скажем , задана в аффинных координатах, т. е. , то стоимость сложения снижается до 11M. Это называется смешанным сложением. Алгоритм 1 построен таким образом, что он всегда использует смешанные сложения, т. е. стоимость сложения в нем равна 11M.

Пример 22. Рассмотрим вычисление суммы (5,1) + (4,6) в проективных координатах для кривой

Все вычисления проводятся по модулю 7.

Для проверки переведем точку в аффинное представление. Для этого произведем следующие вычисления:

В итоге получаем

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

Заметим, что условие эквивалентно , а условие эквивалентно . Если вычисления на кри­вой проводятся, как это предполагалось нами, в подмножестве точек мощности q, причем q – простое число и , то условия для сложения в алгоритме 1 автоматически выполняются (за исключением самого первого сложения, которое заменяется присваиванием).

Для удвоения точки в проективных координатах делаем аналогичную замену переменных в соответствующей формуле:

что приводит к следующему алгоритму.

Алгоритм 3. Удвоение точки в проективном представлении.

Вход:

Выход:

Мы видим, что стоимость удвоения в проективных координатах в общем случае равна 10М. Однако если параметр кривой , то и стоимость удвоения уменьшается до 8М.

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