ДСТУ 4145-2002

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

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

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

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

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

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

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

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

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

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

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

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

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

общие параметры цифровой подписи
личный ключ цифровой подписи $d$
сообщение $T$ длины $L_{T}>0$
хеш-функция $H(T)$ с длиной хеш-кода $L_{H}$ и идентификатором $iH$
длина цифровой подписи $L_{D}$ , которая выбирается для группы пользователей: $L_{D}\geq 2L(n),L_{D}\equiv 0\ (mod\ \ 16)$

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

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

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

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

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

выбор рандомизатора $e$ на основе криптографического генератора псевдослучайных чисел
вычисление точки эллиптической кривой $R=eP=(x_{R},y_{R})$
проверка значения координаты $x_{R}$ ( если $x_{R}=0$ , то повторить процедуру выбора рандомизатора)
иначе принять $F_{R}=x_{R}$ . (иное обозначение: $F_{e}=\pi (R)$ )

Результат

цифровая предподпись $F_{e}\in GF(2^{n})$

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

проверка корректности общих параметров, ключей, и выполнения условий и ограничений относительно значений промежуточных величин в соответствии с определенными стандартом процедурами
вычисление хеш-кода $H(T)$ на основе сообщения $T$
получение элемента основного поля $h$ из хеш-кода $H(T)$ по установленной стандартом процедуре. Если при этом получается $h=0$ , то принимают $h=1$
выбор рандомизатора $e$
вычисление цифровой предподписи $F_{e}$
вычисление элемента основного поля $y=hF_{e}$ (произведение является элементом $GF(2^{m})$ ) (фактически, $r=y=h\pi (R)$ )
получение целого числа $r$ из элемента основного поля $y$ по установленной стандартом процедуре (в случае $r=0$ выбирается новый рандомизатор)
вычисление целого числа $s=(e+dr)\ mod\ n$ (если $s=0$ , выбирается новый рандомизатор)
на основе пары целых чисел $(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)$

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

проверка корректности общих параметров, ключей, и выполнения условий и ограничений относительно значений промежуточных величин в соответствии с определенными стандартом процедурами
проверка идентификатора хеш-функции $iH$ : если данный идентификатор не используется в заданной группе пользователей, то принимается решение "подпись недействительна" и проверка завершается
на основании $iH$ определяется длина хеш-кода $L_{H}$
проверка условий $L_{D}\geq 2L(n),L_{D}\equiv 0\ (mod\ \ 16)$ . Если хотя бы одно из них не выполняется, то принимается решение "подпись недействительна" и проверка завершается
проверка наличия текста сообщения и его длины $L_{T}=L-L(iH)-L_{D}$ . В случае отсутствия текста либо при $L_{T}\leq 0$ принимается решение "подпись недействительна" и проверка завершается
вычисление хеш-кода $H(T)$ на основе сообщения $T$
получение элемента основного поля $h$ из хеш-кода $H(T)$ по установленной стандартом процедуре. Если при этом получается $h=0$ , то принимают $h=1$
выделение пары чисел $(r,s)$ из двоичной записи цифровой подписи $D$
проверка условий $0<r<n$ и $0<s<n$ . Если хотя бы одно из них не выполняется, то принимается решение "подпись недействительна" и проверка завершается
вычисление точки эллиптической кривой $R=sP+rQ,R=(x_{R},y_{R})$
вычисление элемента основного поля $y=hx_{R}$
получение целого числа ${\tilde {r}}$ из элемента основного поля $y$ по установленной стандартом процедуре
если $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)$

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

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

Ссылки

Текст ДСТУ 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

Примечания

↑ ¹ ² Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевіряння (неопр.). shop.uas.org.ua. Дата обращения: 13 декабря 2019. Архивировано 5 мая 2019 года.
↑ ¹ ² Національні стандарти на які є посилання у нормативно-правових актах | ДП «УкрНДНЦ» (неопр.). uas.org.ua. Дата обращения: 13 декабря 2019. Архивировано 14 мая 2019 года.
↑ Приказ Минцифры Украины от 30 сентября 2020 года № 140/614 (неопр.). Дата обращения: 11 января 2020.

[:1-1] ¹ ² Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевіряння (неопр.). shop.uas.org.ua. Дата обращения: 13 декабря 2019. Архивировано 5 мая 2019 года.

[:0-2] ¹ ² Національні стандарти на які є посилання у нормативно-правових актах | ДП «УкрНДНЦ» (неопр.). uas.org.ua. Дата обращения: 13 декабря 2019. Архивировано 14 мая 2019 года.

[3] Приказ Минцифры Украины от 30 сентября 2020 года № 140/614 (неопр.). Дата обращения: 11 января 2020.

[1]

[2]

[3]