ДСТУ 4145-2002

ДСТУ 4145-2002 (полное название: «ДСТУ 4145-2002. Информационные технологии. Криптографическая защита информации. Цифровая подпись, основанная на эллиптических кривых. Формирование и проверка») — украинский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи, основанные на свойствах групп точек эллиптических кривых над полями ${\displaystyle 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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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