Русская Википедия:ДСТУ 4145-2002

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результат

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

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

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

Результат

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

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

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

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

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

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

Результат

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

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

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

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

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

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

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

Результат

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

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

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

Ссылки

• Шаблон: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