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

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

• степень расширения ${\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\}}$ . Рекомендованные для использования эллиптические кривые для полиномиального базиса и оптимального нормального базиса указаны в Приложении к стандарту
• базовая точка эллиптической кривой ${\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)}$
• должно выполняться (условие Менезеса-Окамото-Венстоуна): ${\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}$ является двоичным представлением выходного числа алгоритма

Ссылки

• (укр.) .
• (неопр.) . — Технические спецификации форматов криптографических сообщений. Защищённые данные. Архивировано из 26 мая 2012 года.
• (укр.) .

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

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

Примечания

1. ↑ (неопр.) . shop.uas.org.ua. Дата обращения: 13 декабря 2019. 5 мая 2019 года.
2. ↑ (неопр.) . uas.org.ua. Дата обращения: 13 декабря 2019. 14 мая 2019 года.
3. (неопр.) . Дата обращения: 11 января 2020.