ДСТУ 4145-2002

ДСТУ 4145-2002 (полное название: «ДСТУ 4145-2002. Информационные технологии. Криптографическая защита информации. Цифровая подпись, основанная на эллиптических кривых. Формирование и проверка») — украинский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи, основанные на свойствах групп точек эллиптических кривых над полями [math]\displaystyle{ GF(2^m) }[/math]и правилах применения этих правил к сообщениям, которые пересылаются по каналами связи и/или обрабатываются в компьютеризованных системах общего назначения.

Принят и введён в действие приказом государственного комитета Украины по вопросам технического регулирования и потребительской политики от 28 декабря 2002 года № 31. Текст стандарта есть в открытом доступе.

В стандарте по умолчанию используется хеш-функция ГОСТ 34.311-95, и генератор случайных последовательностей с использованием алгоритма ДСТУ ГОСТ 28147:2009.

Согласно приказу Минцифры Украины от 30 сентября 2020 года № 140/614, с 1 января 2021 года стандарт должен использоваться совместно с ДСТУ 7564:2014 (хеш-функция «Купина»), но использование стандарта совместно с ГОСТ 34.311-95 разрешено до 1 января 2022 года.

Основной алгоритм

Основными процедурами алгоритма цифровой подписи, установленными ДСТУ 4145-2002 являются вычисление предподписи, вычисление подписи, и проверка цифровой подписи.

Общие параметры цифровой подписи

• степень расширения [math]\displaystyle{ m }[/math] - простое число (параметр поля [math]\displaystyle{ GF(2^m) }[/math])
• неприводимый полином [math]\displaystyle{ f(t) }[/math] степени [math]\displaystyle{ m }[/math], определяющий операции в [math]\displaystyle{ GF(2^m) }[/math]
• коэффициенты эллиптической кривой вида [math]\displaystyle{ y^2+xy = x^3 + Ax^2 + B }[/math], где [math]\displaystyle{ A, B \in GF(2^m), B \neq 0, A \in \{0, 1\} }[/math]. Рекомендованные для использования эллиптические кривые для полиномиального базиса и оптимального нормального базиса указаны в Приложении к стандарту
• базовая точка эллиптической кривой [math]\displaystyle{ P }[/math], порождающая подгруппу [math]\displaystyle{ E_n }[/math] группы [math]\displaystyle{ E }[/math]
• порядок [math]\displaystyle{ n }[/math] базовой точки [math]\displaystyle{ P }[/math] (простое число)
• длина представления числа [math]\displaystyle{ n }[/math] в двоичном виде [math]\displaystyle{ L(n) }[/math]
• идентификатор используемой хеш-функции [math]\displaystyle{ iH }[/math]
• длина цифровой подписи [math]\displaystyle{ L_D }[/math]

Дополнительные условия на параметры

• порядок циклической подгруппы [math]\displaystyle{ n }[/math] должен удовлетворять условию [math]\displaystyle{ n \geq \max(2^{160}, 4[\sqrt{2^m}] + 1) }[/math]
• должно выполняться MOV условие (условие Менезеса-Окамото-Венстоуна): [math]\displaystyle{ 2^{mk} \neq 1 (mod n) }[/math] для [math]\displaystyle{ k=1, 2,..., 32 }[/math]

Формирование цифровой подписи

Цифровая подпись вычисляется на основе сообщения и предподписи.

Входные данные

• общие параметры цифровой подписи
• личный ключ цифровой подписи [math]\displaystyle{ d }[/math]
• сообщение [math]\displaystyle{ T }[/math] длины [math]\displaystyle{ L_T \gt 0 }[/math]
• хеш-функция [math]\displaystyle{ H(T) }[/math] с длиной хеш-кода [math]\displaystyle{ L_H }[/math] и идентификатором [math]\displaystyle{ iH }[/math]
• длина цифровой подписи [math]\displaystyle{ L_D }[/math], которая выбирается для группы пользователей: [math]\displaystyle{ L_D \geq 2L(n), L_D \equiv 0 \ (mod \ \ 16) }[/math]

Вычисление цифровой предподписи

Вычисление предподписи состоит в выборе первой координаты секретной, случайно выбранной точки из орбиты точки [math]\displaystyle{ P }[/math]. После использования цифровой предподписи её сразу уничтожают вместе с соответствующим рандомизатором.

Входные данные

• общие параметры цифровой подписи

Алгоритм вычисления предподписи

1. выбор рандомизатора [math]\displaystyle{ e }[/math] на основе криптографического генератора псевдослучайных чисел
2. вычисление точки эллиптической кривой [math]\displaystyle{ R = eP = (x_R, y_R) }[/math]
3. проверка значения координаты [math]\displaystyle{ x_R }[/math] ( если [math]\displaystyle{ x_R=0 }[/math], то повторить процедуру выбора рандомизатора)
4. иначе принять [math]\displaystyle{ F_R=x_R }[/math]. (иное обозначение: [math]\displaystyle{ F_e=\pi(R) }[/math])

Результат

• цифровая предподпись [math]\displaystyle{ F_e \in GF(2^n) }[/math]

Алгоритм вычисления подписи

1. проверка корректности общих параметров, ключей, и выполнения условий и ограничений относительно значений промежуточных величин в соответствии с определенными стандартом процедурами
2. вычисление хеш-кода [math]\displaystyle{ H(T) }[/math] на основе сообщения [math]\displaystyle{ T }[/math]
3. получение элемента основного поля [math]\displaystyle{ h }[/math] из хеш-кода [math]\displaystyle{ H(T) }[/math] по установленной стандартом процедуре. Если при этом получается [math]\displaystyle{ h = 0 }[/math], то принимают [math]\displaystyle{ h = 1 }[/math]
4. выбор рандомизатора [math]\displaystyle{ e }[/math]
5. вычисление цифровой предподписи [math]\displaystyle{ F_e }[/math]
6. вычисление элемента основного поля [math]\displaystyle{ y = hF_e }[/math] (произведение является элементом [math]\displaystyle{ GF(2^m) }[/math]) (фактически, [math]\displaystyle{ r=y=h\pi(R) }[/math])
7. получение целого числа [math]\displaystyle{ r }[/math] из элемента основного поля [math]\displaystyle{ y }[/math] по установленной стандартом процедуре (в случае [math]\displaystyle{ r=0 }[/math] выбирается новый рандомизатор)
8. вычисление целого числа [math]\displaystyle{ s=(e+dr)\ mod\ n }[/math] (если [math]\displaystyle{ s=0 }[/math], выбирается новый рандомизатор)
9. на основе пары целых чисел [math]\displaystyle{ (r, s) }[/math] записывается цифровая подпись [math]\displaystyle{ D }[/math] как двоичный ряд длины [math]\displaystyle{ L_D }[/math]: в младших разрядах левой половины битов размещается значение [math]\displaystyle{ s }[/math], в младших разрядах правой половины битов размещается значение [math]\displaystyle{ r }[/math], оставшиеся разряды заполняются нулями

Результат

• подписанное сообщение в виде ([math]\displaystyle{ iH }[/math], [math]\displaystyle{ T }[/math], [math]\displaystyle{ D }[/math]), где [math]\displaystyle{ D }[/math] - цифровая подпись

Проверка цифровой подписи

Входные данные

• общие параметры цифровой подписи
• открытый ключ цифровой подписи [math]\displaystyle{ Q }[/math], [math]\displaystyle{ Q=-dP }[/math]
• подписанное сообщение ([math]\displaystyle{ iH }[/math], [math]\displaystyle{ T }[/math], [math]\displaystyle{ D }[/math]) длины [math]\displaystyle{ L = L(iH)+L_T+L_D }[/math]
• хеш-функция [math]\displaystyle{ H(T) }[/math]

Алгоритм вычисления подписи

1. проверка корректности общих параметров, ключей, и выполнения условий и ограничений относительно значений промежуточных величин в соответствии с определенными стандартом процедурами
2. проверка идентификатора хеш-функции [math]\displaystyle{ iH }[/math]: если данный идентификатор не используется в заданной группе пользователей, то принимается решение "подпись недействительна" и проверка завершается
3. на основании [math]\displaystyle{ iH }[/math] определяется длина хеш-кода [math]\displaystyle{ L_H }[/math]
4. проверка условий [math]\displaystyle{ L_D \geq 2L(n), L_D \equiv 0 \ (mod \ \ 16) }[/math]. Если хотя бы одно из них не выполняется, то принимается решение "подпись недействительна" и проверка завершается
5. проверка наличия текста сообщения и его длины [math]\displaystyle{ L_T = L - L(iH)-L_D }[/math]. В случае отсутствия текста либо при [math]\displaystyle{ L_T \leq 0 }[/math] принимается решение "подпись недействительна" и проверка завершается
6. вычисление хеш-кода [math]\displaystyle{ H(T) }[/math] на основе сообщения [math]\displaystyle{ T }[/math]
7. получение элемента основного поля [math]\displaystyle{ h }[/math] из хеш-кода [math]\displaystyle{ H(T) }[/math] по установленной стандартом процедуре. Если при этом получается [math]\displaystyle{ h = 0 }[/math], то принимают [math]\displaystyle{ h = 1 }[/math]
8. выделение пары чисел [math]\displaystyle{ (r, s) }[/math] из двоичной записи цифровой подписи [math]\displaystyle{ D }[/math]
9. проверка условий [math]\displaystyle{ 0 \lt r \lt n }[/math] и [math]\displaystyle{ 0 \lt s \lt n }[/math]. Если хотя бы одно из них не выполняется, то принимается решение "подпись недействительна" и проверка завершается
10. вычисление точки эллиптической кривой [math]\displaystyle{ R=sP+rQ, R=(x_R, y_R) }[/math]
11. вычисление элемента основного поля [math]\displaystyle{ y = hx_R }[/math]
12. получение целого числа [math]\displaystyle{ \tilde{r} }[/math] из элемента основного поля [math]\displaystyle{ y }[/math] по установленной стандартом процедуре
13. если [math]\displaystyle{ r = \tilde{r} }[/math], то принимается решение "подпись действительна", иначе - "подпись недействительна"

Результат

• принятое решение: "подпись действительна" либо "подпись недействительна"

Криптостойкость

Криптостойкость цифровой подписи основывается на сложности дискретного логарифмирования [math]\displaystyle{ R=eP, Q=-dP }[/math] в циклической подгруппе группы точек эллиптической кривой.

Используемые вспомогательные алгоритмы

Получение целого числа из элемента основного поля

Входные данные

• элемент основного поля [math]\displaystyle{ x \in GF(2^m), x=(x_{m-1}, ..., x_0) }[/math]
• порядок базовой точки эллиптической кривой [math]\displaystyle{ n }[/math]

Результат

• целое число [math]\displaystyle{ a=(a_{L-1}, ..., a_0) }[/math], удовлетворяющее условию [math]\displaystyle{ L = L(a) \lt L(n) }[/math]

Алгоритм вычисления

1. если элемент [math]\displaystyle{ x }[/math] основного поля равен 0, то [math]\displaystyle{ a \leftarrow 0\ \ \ L = L(a) \leftarrow 1 }[/math], конец алгоритма
2. нахождение целого числа [math]\displaystyle{ k = L(n) - 1 }[/math]
3. принимается [math]\displaystyle{ a_i = x_i \ \ i=0,...k-1 }[/math] и находится [math]\displaystyle{ j }[/math], соответствующий наибольшему индексу [math]\displaystyle{ i }[/math], при котором [math]\displaystyle{ a_i = 1 }[/math]. Если такого индекса нет, принимают [math]\displaystyle{ a \leftarrow 0 }[/math] и заканчивают выполнение алгоритма
4. двоичный ряд [math]\displaystyle{ (a_j, ..., a_0) }[/math] длины [math]\displaystyle{ L = L(a) = j + 1 }[/math] является двоичным представлением выходного числа алгоритма

Ссылки

• Текст ДСТУ 4145:2002 на сайте ДП «УкрНДНЦ» (укр.).
• dsszzi.gov.ua (неопр.) (недоступная ссылка). — Технические спецификации форматов криптографических сообщений. Защищённые данные. Архивировано 26 мая 2012 года.
• Про затвердження вимог до форматів, структури та протоколів, що реалізуються у надійних засобах електронного цифрового підпису (укр.).
• Додаток до Вимог до формату посиленого сертифіката відкритого ключа. Опис генератора випадкових послідовностей

Программные реализации

• Проект ДСТУ 4145-2002 на сайте SourceForge.net — Библиотека с открытым исходным кодом для генерации ключей, создания и проверки ЭЦП по стандарту ДСТУ 4145-2002.
• Bouncy Castle — Библиотека с открытым исходным кодом на языке Java. Реализует JCA интерфейс
• cryptonite - библиотека, принадлежащая акционерному обществу Приватбанк с открытым программным кодом на C (язык), имеет экспертный вывод UA.14360570.00001-01 90 01-1 по результатам государственной экспертизы в области криптографической защиты информации
• Jkurwa - библиотека с открытым исходным кодом на языке JavaScript
• ТОВ НВЦ "Бітіс" — лицензированная реализация стандарта на Java, C++, Object Pascal