Пост-квантовый алгоритм электронно-цифровой подписи на основе дерева Меркла и ГОСТ РФ 34.11–12 «Стрибог» | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Информатика

Опубликовано в Молодой учёный №23 (157) июнь 2017 г.

Дата публикации: 11.06.2017

Статья просмотрена: 410 раз

Библиографическое описание:

Батенко К. Е., Прокудин А. Н. Пост-квантовый алгоритм электронно-цифровой подписи на основе дерева Меркла и ГОСТ РФ 34.11–12 «Стрибог» // Молодой ученый. — 2017. — №23. — С. 100-103. — URL https://moluch.ru/archive/157/44376/ (дата обращения: 21.02.2019).



Исследование алгоритмов пост-квантовой криптографии, основанных на хэш-функциях, и последующая разработка алгоритма, в основу которого берётся ГОСТ РФ 34.11–12 «Стрибог» и дерево Меркла.

Ключевые слова: пост-квантовая криптография, хэш-функция, электронно-цифровая подпись, дерево Меркла

Алгоритмы электронно-цифровой подписи являются одним из важнейших инструментов криптографии и обеспечивают целостность электронного документа, аутентификацию и неотказуемость автора документа. Электронно-цифровая подпись в настоящее время применяется для обеспечения безопасности банковских транзакций, в государственных закупках, электронном документообороте, налоговой отчетности, в сетевых протоколах и т. д.

Те алгоритмы ЭЦП, которые используются в настоящее время, основываются на односторонней функции, а также на криптографической хэш-функции. Односторонняя функция в свою очередь основана на определенной сложной математической проблеме, для которой неизвестно эффективных алгоритмов решения. Например, алгоритм ЭЦП ECDSA использует проблему вычисления дискретного логарифма в группе точек эллиптической кривой, а другой широко известный алгоритм ЭЦП — RSA берёт в свою основу проблему факторизации больших целых чисел. Все перечисленные алгоритмы ЭЦП являются стойкими, поскольку для решения лежащих в их основе математических проблем известны лишь неэффективные, а именно, в лучше случае субэкспоненциальные алгоритмы. Следует отметить, что речь идет об алгоритмах, предназначенных для исполнения на классическом электронном компьютере. Однако еще в 1980-х годах была предложена идея использовать явления квантовой суперпозиции и квантовой запутанности для передачи и обработки данных. Вычислительное устройство, основанное на этих принципах, называется квантовым компьютером. В 1994 г. Питер Шор разработал полиномиальный алгоритм факторизации для квантового компьютера. Небольшая модификация этого алгоритма позволяет решать также задачу дискретного логарифма. Высокая эффективность алгоритма Шора означает, что криптографические алгоритмы, использующие проблемы факторизации и дискретного логарифма, потенциально являются нестойкими при наличии полноценного квантового компьютера.

Появление алгоритма Шора способствовало созданию новой области криптографии — пост-квантовой криптографии, которая изучает алгоритмы, стойкие ко взлому на квантовом компьютере. Стоит заметить, что на сегодняшний день такого компьютера ещё не существует. Однако, учитывая скорость современного технического прогресса, появление такого компьютера не стоит считать слишком отдалённым будущим, поэтому пост-квантовая криптография является актуальной областью исследований в настоящее время.

Одним из наиболее перспективных направлений пост-квантовой криптографии является криптография, основанная на хэш-функциях. Алгоритмы этого направления применяются для формирования и проверки ЭЦП и используют только криптографически стойкую хэш-функцию. В России существует ГОСТ РФ 34.11–12, другое его название — «Стрибог» [1]. На данный момент уже есть множество работ по криптоанализу данного алгоритма, но почти все они смогли привести лишь теоретически реализуемые атаки. На практике же количество вычислений для нахождения коллизий будет огромным и ресурсозатратным, поэтому алгоритм Стрибог считается безопасным алгоритмом.

Предлагаемый алгоритм подписи основан на следующих компонентах:

− Односторонняя криптографически стойкая хэш-функция «Стрибог»;

− Одноразовая подпись;

− Дерево Меркла.

Примерами одноразовых подписей являются подпись Лампорта и Винтерница [2]. Стоит учитывать, что при использовании подписи Винтерница открытый ключ будет намного короче за счет того, что одновременно подписывается бит.

Основные преимущества схемы одноразовой подписи как Лампорта, так и Винтерница заключаются в том, что они могут быть построены на любой стойкой криптографической хэш-функции. В качестве этой функции в нашем пост-квантовом алгоритме мы будем использовать хэш-функцию «Стрибог». В то же время схема имеет ряд недостатков. Во-первых, недостатком является одноразовость ключей. То есть, при подписи каждого нового сообщения приходиться генерировать новую пару, что приводит к усложнению системы. Во-вторых, схема имеет недостаток в виде большого размера подписи и пары из открытого и закрытого ключей.

В [3] Меркл представил свою схему подписи Меркла в которой один открытый ключ используется для того, чтобы подписать множество сообщений, что и решает проблему с вынужденной постоянной генерацией пары ключей для каждого нового сообщения.

Опишем принцип генерации ключа. Во-первых, стоит заметить, что схема подписи Меркла может использоваться только для подписи ограниченного числа сообщений одним открытым ключом . Обозначим возможное количество сообщений как . Первым шагом в генерации этого единственного открытого ключа pub будет генерацией ключевых пар открытых и закрытых ключей в количестве, как и сообщений, . Затем для каждого открытого ключа , где высчитывается хэш-значение . С высчитанными хэш-значениями строится дерево Меркла (его также называют хэш-деревом). Обозначим узел дерева как , где – число, означающее уровень узла дерева. Уровень узла определяется расстоянием от узла до листа. Следовательно, уровень листа дерева , при этом уровень корня определяется как . Мы пронумеруем все узлы одного уровня слева на право так, чтобы было самым левым узлом уровня. В дереве Меркла хэш-значения – это листья бинарного дерева такие, что Каждый внутренний узел дерева - это хэш-значение конкатенации двух дочерних хэшей этого узла. Так и . Пример дерева Меркла для высоты иллюстрировано на рисунке 1.

C:\Users\Carolina\AppData\Local\Microsoft\Windows\INetCache\Content.Word\меркл.png

Рис. 1. Пример дерева Меркла с 8-мью листьями

Таким образом, строится дерево с листьями и узлами в количестве . Корень дерева – это и есть тот самый открытый ключ pub схемы подписи Меркла.

Чтобы подписать сообщение при помощи подписи Меркла, это сообщение сперва подписывается односторонней ЭЦП, при этом, конечно же, вычисляется подпись . Это делается при помощи одной ключевой пары которая выбирается из дерева. Лист хэш-дерева, соответствующий открытому ключу является хэш значением данного ключа и представляется, как . Путь в хэш-дереве от до корня назовём . Путь состоит из узлов. Обозначим их как , где это лист и это корень дерева. Чтобы вычислить этот путь , нам нужны все «дети» узлов . Мы знаем, что является дочерним узлом узла . Чтобы высчитать этот самый следующий узел нужно знать всех обоих «детей» этого самого узла. Следовательно, нам нужен смежный узел c узлом . Назовём этот узел , так что:

.

Поэтому можно сказать, что для того, чтобы высчитать все узлы, из которых состоит путь , нам понадобятся узлов, которые можно представить, как . Высчитаем эти узлы и сохраним их в памяти. Эти узлы, плюс односторонняя подпись сообщения есть искомая подпись Меркла, которая обозначается, как

.

Пример аутентификационного пути представлен на рисунке 2.

C:\Users\Carolina\AppData\Local\Microsoft\Windows\INetCache\Content.Word\Меркл путь до А.PNG

Рис. 2. Дерево Меркла с путём и путём аутентификации для

Теперь опишем подтверждение подписи. Получателю известен открытый ключ , сообщение и подпись . Получатель подтверждает одноразовую подпись сообщения . Если подпись верна для сообщения , получатель вычисляет путём хэширования открытого ключа одноразовой подписи. Для , узлы пути вычисляются по формуле:

.

Если получится равным открытому ключу подписи Меркла, то подпись верна.

Основным недостатком алгоритмов на деревьях Меркла является проблема хранения большого количества закрытых ключей и их последующая передача. Чтобы решить данную проблему, можно на основе одного секретного ключа небольшого размера создать криптографически стойкий генератор псевдослучайных чисел (КСГПСЧ), который будет заполнять все массивы закрытых ключей. Тогда этот один ключ можно будет передавать быстрее и сам он не будет таким требовательным к памяти.

Данный генератор даст нам возможность передавать хранить в памяти небольшой закрытый ключ вместо внушительного количества закрытых ключей. Будем использовать в качестве односторонней ЭЦП алгоритм Винтерница. Введём обозначения:

– счётчик для количества ключей в дереве Меркла;

– счётчик для алгоритма Винтерница.

Процесс генерации секретных и открытых ключей выглядит следующим образом:

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

Далее:

Этот вариант алгоритма можно считать более приемлемым, поскольку, введя счётчики мы повышаем вероятность случайного выпадения бита, а также уменьшаем вероятность того, что в открытых ключах будут повторы битов из закрытых ключей.

Литература:

  1. ГОСТ РФ 34.11–2012. Информационная технология. Криптографическая защита информации. Функция хеширования. — Введ. 2012–07–08. — М.: Стандартинформ, 2012. — 38 с.
  2. Bernstein D. J. Post-Quantum Cryptography / D. J. Dernstein, J. Buchman, E. Duchman — Ch.: Springer, 2008. — 248 p.
  3. Ralph Merkle. Secrecy, authentication and public key systems/ A certified digital signature. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University. – 1979 – 193 с.
Основные термины (генерируются автоматически): открытый ключ, алгоритм, пост-квантовая криптография, дерево, узел, ключ, одноразовая подпись, квантовый компьютер, дискретный логарифм, электронно-цифровая подпись.


Похожие статьи

Способ хранения закрытого ключа криптосистемы цифровой...

цифровая подпись, хранения закрытого ключа, облачные системы, криптография, защита информации.

Пост-квантовый алгоритм электронно-цифровой подписи на основе дерева Меркла и ГОСТ РФ 34.11–12 «Стрибог».

Актуальный метод криптографий, основанный на квантовых...

Квантовая криптография обеспечивает возможность относительно быстрой смены ключей и определения попыток злоумышленника вторгнуться в канал связи.

Известно несколько протоколов распределения ключей на основе дискретных квантовых состояний.

Криптография. Основные методы и проблемы. Современные...

криптография, RSA, ключ, квантовая криптография, канал связи, алгоритм, электронная подпись, защита информации, мировая война, симметричное шифрование.

Выбор эффективного метода подбора эллиптической кривой для...

Ключевые слова: криптографические методы защиты информации, электронно-цифровая подпись, эллиптическая криптография

Известно, что в основе ассиметричной криптографии лежит использование двух ключей — для шифрования и дешифрования данных...

Оценка стойкости криптосистемы Эль-Гамаля | Статья в сборнике...

Секретный ключ криптографии, также известный как секретный ключ или симметричный ключ шифрования, имеет

криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма.

Способ хранения закрытого ключа криптосистемы цифровой подписи.

Теория чисел в криптографии | Статья в журнале...

Так как дискретное логарифмирование и факторизация целых чисел [4, с. 21] являются

Алгоритм шифрования. – Сообщение. – A вычисляет, взяв данные открытого ключа абонента B

Применения: Электронная цифровая подпись. Пример: Подтверждение авторства.

Генераторы случайных и псевдослучайных чисел

Алгоритмы формирования электронно-цифровых подписей используют случайные числа для формирования ключей. При чём требования к этим числам крайне строгие, ведь от их выполнения зависит криптостойкость всей системы шифрования.

Реализация квантовых вычислений в программе Excel

кубит, квантовый компьютер, квантовый гейт, алгоритм Гровера.

Похожие статьи. Актуальный метод криптографий, основанный на квантовых свойствах фотонов.

Электронная почта.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Способ хранения закрытого ключа криптосистемы цифровой...

цифровая подпись, хранения закрытого ключа, облачные системы, криптография, защита информации.

Пост-квантовый алгоритм электронно-цифровой подписи на основе дерева Меркла и ГОСТ РФ 34.11–12 «Стрибог».

Актуальный метод криптографий, основанный на квантовых...

Квантовая криптография обеспечивает возможность относительно быстрой смены ключей и определения попыток злоумышленника вторгнуться в канал связи.

Известно несколько протоколов распределения ключей на основе дискретных квантовых состояний.

Криптография. Основные методы и проблемы. Современные...

криптография, RSA, ключ, квантовая криптография, канал связи, алгоритм, электронная подпись, защита информации, мировая война, симметричное шифрование.

Выбор эффективного метода подбора эллиптической кривой для...

Ключевые слова: криптографические методы защиты информации, электронно-цифровая подпись, эллиптическая криптография

Известно, что в основе ассиметричной криптографии лежит использование двух ключей — для шифрования и дешифрования данных...

Оценка стойкости криптосистемы Эль-Гамаля | Статья в сборнике...

Секретный ключ криптографии, также известный как секретный ключ или симметричный ключ шифрования, имеет

криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма.

Способ хранения закрытого ключа криптосистемы цифровой подписи.

Теория чисел в криптографии | Статья в журнале...

Так как дискретное логарифмирование и факторизация целых чисел [4, с. 21] являются

Алгоритм шифрования. – Сообщение. – A вычисляет, взяв данные открытого ключа абонента B

Применения: Электронная цифровая подпись. Пример: Подтверждение авторства.

Генераторы случайных и псевдослучайных чисел

Алгоритмы формирования электронно-цифровых подписей используют случайные числа для формирования ключей. При чём требования к этим числам крайне строгие, ведь от их выполнения зависит криптостойкость всей системы шифрования.

Реализация квантовых вычислений в программе Excel

кубит, квантовый компьютер, квантовый гейт, алгоритм Гровера.

Похожие статьи. Актуальный метод криптографий, основанный на квантовых свойствах фотонов.

Электронная почта.

Задать вопрос