ДСТУ 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}+Ax^{2}+B$, где $A,B\in GF(2^{m}),B\neq 0,A\in \{0,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$. После использования цифровой предподписи её сразу уничтожают вместе с соответствующим рандомизатором.

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

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

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

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=hF_{e}$ (произведение является элементом $GF(2^{m})$) (фактически, $r=y=h\pi (R)$)
7. получение целого числа $r$ из элемента основного поля $y$ по установленной стандартом процедуре (в случае $r=0$ выбирается новый рандомизатор)
8. вычисление целого числа $s=(e+dr)\ mod\ n$ (если $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}\geq 2L(n),L_{D}\equiv 0\ (mod\ \ 16)$. Если хотя бы одно из них не выполняется, то принимается решение "подпись недействительна" и проверка завершается
5. проверка наличия текста сообщения и его длины $L_{T}=L-L(iH)-L_{D}$. В случае отсутствия текста либо при $L_{T}\leq 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=hx_{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 0\ \ \ L=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$ является двоичным представлением выходного числа алгоритма

Ссылки

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