Алгоритм функционирования криптографической системы на основе дискретного логарифмирования в метрике эллиптических кривых

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

Рассмотрим особенности методов математической формализации на эллиптических кривых. Эллиптической кривой называется кривая третьего порядка Z, задаваемая следующим уравнением Z: Y² = X³ + aX + b. Для вычисления характерных точек, принадлежащих эллиптической кривой, для детерминирования множеств открытых К_О и закрытых К_З ключей в соответствии с преобразованием Кардана (аналогично преобразованиям Виета для решения уравнения второго порядка Z: Y = aX² + bX + C) прежде всего необходимо определить условие ограничения. Таким условием в прикладных аспектах криптографии являются требования к задаваемым параметрам «а» и «в» эллиптических кривых, эти параметры для построения криптографических систем должны удовлетворять следующим позициям. Прежде всего, эти параметры должны быть такими, чтобы уравнение эллиптической кривой имело три различных корня. Это условие достигается тогда и только тогда, когда дискриминант уравнения Z: Y² = X³ + aX + b не будет равен нулю D ≠ 0. Случай, когда дискриминант уравнения эллиптической кривой равен нулю D = 0, определяет задаваемую эллиптическую кривую как сингулярную, т.е. в точке сингулярности имеются две касательные, такой случай характеризует неопределенность решений и в прикладной криптографии, в настоящее время, исключается из рассмотрения.

Таким образом, при задании эллиптической кривой с параметрами «а» и «в» обязательным условием является неравенство нулю дискриминанта задаваемого уравнения. В свою очередь, в соответствии с преобразованием Кардана, дискриминант уравнения эллиптической кривой определяется как:

D = ( ³ + ( ².

Исходя из представленной зависимости, необходимым условием применимости параметров «а» и «в» к задачам прикладной криптографии, является условие:

+ ≠ 0; 4 а³ + 27 b² ≠ 0.

Весьма важным условием в решении криптографических задач в метрике эллиптических кривых является вычисление операции удвоения исходной генераторной точки в решении уравнения и удвоения полученных последующих точек [2]G; [4]G; … [2ⁿ]G и операции вычисления их композиций. Это условие необходимо для определения любой точки принадлежащей заданной эллиптической кривой, в этом случае полное множество точек эллиптической кривой может быть построено на основании только одной точки той же кривой, называемой генераторной точкой. Так, например, для определения пятой точки необходимо выполнить две операции удвоения генераторной точки и одну операцию композиции между исходной генераторной точкой и результатом процесса ее учетверения, т.е.

[5]G₁ = G₁ + [4]G₁; G₂ = [2]G₁; [4]G₁ = [2]G₂;

Для криптографических преобразований в уравнении эллиптической кривой Z: Y² = (X³ + aX + b) mod P переменными величинами являются параметры X и Y и коэффициенты «а» и «в», все вычисления выполняются по модулю Р, в свою очередь на параметры «а» и «в» накладываются дополнительные ограничения - их значения должны принимать только целочисленные значения и значение дискриминанта, полученного с их помощью по заданному модулю, не должно равняться нулю:

D = (4a³ + 27b²) mod P ≠ 0.

Необходимо отметить, что все процессы алгоритма дискретного логарифмирования переносятся на эллиптические кривые, и основной операцией такого соответствия является операция замены функционального преобразования дискретного логарифмирования К_ОВ = mod P при вычислении открытого ключа К_ОВ по случайно выбранному закрытому (секретному) ключу К_ЗВ на замену числа К_ОВ на точку К_ОВ заданной эллиптической кривой. Переход от числа К_ОВ к точке К_ОВ на эллиптической кривой заключается в представлении точки К_ОВ в сетке координат (x_i; y_i) и использовании при расчетах значения абсциссы выбранной точки – x_i.

В соответствии с ГОСТ Р34.10-2001 на средства аутентификации электронных сообщений (ЭЦП) параметры уравнения эллиптической кривой в практической криптографии определяются следующим образом:

Р – модуль криптографических преобразований является большим простым числом размером 256 бит;

Значение коэффициент «в» составляет 32 бит;

Значение коэффициент «а» составляет 16 бит;

Коэффициенты «а» и «в» - целые числа.

Общее количество точек на заданной эллиптической кривой с заданными параметрами определяется в соответствии с теоремой Хассе и обозначается как #Z_P (a, b):

P + 1 - 2 ≤ #Z_P (a, b) ≤ P + 1 + 2

Значения параметров «а» и «в» выбираются случайным образом при следующих условиях ограничения:

- числовые значения коэффициентов «а» и «в» по выбранному параметру Р не должны равняться нулю:

(а; в) mod P ≠ 0 mod P

- дискриминант уравнения Y² = X³ + aX + b, определяемый как было указано выше также не должен быть равен нулю по заданному модулю Р:

D = (4a³ + 27 b²) mod P ≠ 0.

Поиск по сайту: