ДСТУ 4145-2002

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

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

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

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

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

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

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

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

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

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

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

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

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

• общие параметры цифровой подписи
• личный ключ цифровой подписи $d$
• сообщение $T$ длины $L_T>0$
• хеш-функция $H(T)$ с длиной хеш-кода $L_H$ и идентификатором $iH$
• длина цифровой подписи $L_D$, которая выбирается для группы пользователей: $L_D\ge 2L(n),L_D\equiv 0(mod16)$

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

Вычисление предподписи состоит в выборе первой координаты секретной, случайно выбранной точки из орбиты точки $P$. После использования цифровой предподписи её сразу уничтожают вместе с соответствующим рандомизатором.

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

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

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

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

Результат

• цифровая предподпись $F_e\in GF(2^n)$

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

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

Результат

• подписанное сообщение в виде ($iH$, $T$, $D$), где $D$ - цифровая подпись

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

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

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

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

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

Результат

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

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

Криптостойкость цифровой подписи основывается на сложности дискретного логарифмирования $R=eP,Q=-dP$ в циклической подгруппе группы точек эллиптической кривой.

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

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

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

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

Результат

• целое число $a=(a_{L-1},...,a_0)$, удовлетворяющее условию $L=L(a)<L(n)$

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

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

Ссылки

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Додаток до Вимог до формату посиленого сертифіката відкритого ключа. Опис генератора випадкових послідовностей

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

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