Устройство обработки информации, способ обработки информации и программа

Устройство обработки информации, способ обработки информации и программа

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Настоящее изобретение относится к устройству обработки информации, способу обработки информации и программе.

Уровень техники

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

Цифровая подпись используется для идентификации автора электронного документа. Соответственно, эта цифровая подпись должна быть такой, чтобы ее мог генерировать только автор электронного документа. Если какая-либо злонамеренная третья сторона сможет генерировать такую же самую цифровую подпись, такая третья сторона сможет выдать себя за автора электронного документа. Иными словами, электронный документ может быть фальсифицирован такой злонамеренной третьей стороной. Были высказаны самые разнообразные точки зрения относительно обеспечения защиты такой цифровой подписи с целью предотвращения подобной фальсификации. Сегодня широко используются такие алгоритмы цифровой подписи, как, например, RSA-алгоритм подписи и DSA-алгоритм подписи.

Указанный RSA-алгоритм подписи принимает за основу обеспечения безопасности принцип «трудности разложения большого составного числа на простые множители» (в последующем, проблема разложения на простые множители). Кроме того, DSA-алгоритм подписи принимает за основу обеспечения безопасности принцип «трудности решения проблемы дискретного логарифмирования». Эти принципы базируются на том факте, что не существуют алгоритмы, позволяющие эффективно решать проблему разложения на простые множители и проблему дискретного логарифмирования с использованием классического компьютера. Иными словами, упомянутые выше трудности предполагают вычислительные сложности для классического компьютера. Однако считается, что решения проблемы разложения на простые множители и проблемы дискретного логарифмирования могут быть эффективно вычислены с использованием квантового компьютера.

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

Например, в качестве алгоритмов цифровой подписи, использующих проблему многочленов от нескольких переменных в качестве основы безопасности, известны такие алгоритмы, как алгоритмы на основе криптографии Мацумото-Имаи (Matsumoto-Imai (MI)), криптографии с использованием уравнений скрытого поля (Hidden Field Equation (HFE)), алгоритмы подписи типа Oil-Vinegar (OV) signature и криптографии с использованием ручного преобразования (Tamed Transformation Method (TTM)). Например, алгоритм цифровой подписи на основе HFE-криптографии рассмотрен в следующей непатентной литературе 1 и 2.

Список литературы

Непатентная литература

Непатентная литература 1: Жак Патарен, "Асимметричная криптография со скрытым одночленом" (Jacques Patarin, Asymmetric Cryptography with a Hidden Monomial, CRYPTO 1996, pp. 45-60).

Непатентная литература 2: Патарен Ж., Куртуа Н. и Губин Л., "КВАРЦ, Цифровые подписи длиной 128 бит", (Patarin, J., Courtois, N., and Goubin, L., QUARTZ, 128-Bit Long Digital Signatures, In Naccache, D., Ed.). Topics in Cryptology - CT-RSA 2001 (San Francisco, CA, USA, April 2001), vol. 2020 of Lecture Notes in Computer Science, Springer-Verlag., pp. 282-297.

Раскрытие изобретения

Техническая проблема

Как указано выше, задача многочленов от нескольких переменных представляет собой пример так называемой НП-трудной (NP-hard) проблемы, которую трудно решить даже при использовании квантового компьютера. Обычно алгоритм аутентификации с открытым ключом, использующий проблему многочлена от нескольких переменных, описываемую уравнениями HFE или аналогичным способом, использует уравнение множества порядков с несколькими переменными с потайным входом. Например, используют уравнение F(x₁,…,x_n)=y множества порядков с несколькими переменными x₁, …, x_n и линейные преобразования А и В, управляемые секретным образом. В таком случае, уравнение F множества порядков с несколькими переменными и линейные преобразования А и В являются потайными входами.

Объект, знающий потайные входы F, А и В, может решить уравнение B(F(A(x₁,…,x_n)))=y′ относительно переменных x₁, …, x_n. С другой стороны, уравнение B(F(A(x₁,…,x_n)))=y′ относительно переменных xi,..., Хп не может быть решено субъектом, который не знает потайных входов F, А и В. Используя этот механизм, можно реализовать алгоритм аутентификации с открытым ключом и алгоритм цифровой подписи, использующие трудности решения уравнения множества порядков с несколькими переменными в качестве основы для обеспечения безопасности.

Как описано выше, для реализации алгоритма аутентификации с открытым ключом или алгоритма цифровой подписи необходимо подготовить специальную систему уравнений множества порядков с несколькими переменными, удовлетворяющую условию B(F(A(x₁,…,x_n)))=y. Далее, в момент генерации подписи необходимо решить систему уравнений F множества порядков с несколькими переменными. По этой причине совокупность доступных систем уравнений F множества порядков с несколькими переменными до сих пор ограничивалась относительно легко решаемыми системами уравнений. Таким образом, ранее в известных схемах использовались только системы B(F(A(x₁,…,x_n)))=y уравнений множества порядков с несколькими переменными на основе сочетания трех функций (потайных входов) В, F и А, которые можно относительно решить, вследствие чего трудно обеспечить достаточную степень безопасности.

Соответственно, в свете изложенных выше обстоятельств, авторы настоящего изобретения разработали эффективные и в высокой степени защищенные алгоритм аутентификации с открытым ключом и алгоритм цифровой подписи с использованием систем уравнений множества порядков с несколькими переменными, для которых отсутствуют или присутствуют в недостаточном количестве средства для эффективного решения (потайные входы) (Коити Сакумото, Тайдзо Сираи и Харунага Хиватари, «Алгоритмы идентификации с открытым ключом на основе квадратичных полиномов от нескольких переменных» (Koichi Sakumoto, Taizo Shirai and Harunaga Hiwatari, "Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials", CRYPTO 2011, LNCS 6841, pp. 706 to 723,2011.)).

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

Решение проблемы

Согласно одному из вариантов настоящего изобретения предложено устройство обработки информации, содержащее модуль генерации чисел, выполненный с возможностью генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и модуль назначения, выполненный с возможностью назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Модуль назначения группирует коэффициенты членов, имеющих идентичное сочетание переменных, из совокупности коэффициентов многочленов множества порядков с несколькими переменными, составляющими элементами которых является пара многочленов F множества порядков с несколькими переменными, и выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложено устройство обработки информации, содержащее модуль генерации чисел, выполненный с возможностью генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и модуль назначения, выполненный с возможностью назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Модуль назначения группирует матрицу коэффициентов в каждой строке или столбце, когда многочлены множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, выражены в квадратичной форме, при этом модуль назначения выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложено устройство обработки информации, содержащее модуль генерации чисел, выполненный с возможностью генерации чисел, количество которых идентично количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и модуль назначения, выполненный с возможностью назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, в последовательности, заранее определенной между доказывающей стороной и проверяющей стороной.

Согласно другому варианту настоящего изобретения предложен способ обработки информации, содержащий этап генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и этап назначения генерируемых чисел коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. На этапе назначения чисел группируют коэффициенты членов, имеющих идентичное сочетание переменных, из совокупности коэффициентов многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, и выполняют процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложен способ обработки информации, содержащий этап генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и этап назначения генерируемых чисел коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными входит в составляющие элементы. На этапе назначения чисел группируют матрицу коэффициентов в каждой строке или столбце, когда многочлены множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, выражены в квадратичной форме, и выполняют процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложен способ обработки информации, содержащий этап генерации чисел, количество которых идентично количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и этап назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, в последовательности, заранее определенной между доказывающей стороной и проверяющей стороной.

Согласно другому варианту настоящего изобретения предложена программа, вызывающая выполнение компьютером функции генерации чисел для генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и функции назначения для назначения чисел, генерируемых посредством функции генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Функция назначения группирует коэффициенты членов, имеющих идентичное сочетание переменных, из совокупности коэффициентов многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, и выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложена программа, вызывающая выполнение компьютером функции генерации чисел для генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и функции назначения для назначения чисел, генерируемых посредством функции генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Функция назначения группирует матрицу коэффициентов в каждой строке или столбце, когда многочлены множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, выражены в квадратичной форме, при этом функция назначения выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложена программа, вызывающая выполнение компьютером функции генерации чисел для генерации количества чисел, идентичного количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и функции назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, в последовательности, заранее определенной между доказывающей стороной и проверяющей стороной.

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

Полезные результаты изобретения

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

Краткое описание чертежей

Фиг. 1 представляет пояснительную схему для описания структуры алгоритма аутентификации с открытым ключом.

Фиг. 2 представляет пояснительную схему для описания структуры алгоритма цифровой подписи.

Фиг. 3 представляет пояснительную схему для описания структуры алгоритма,

относящейся к n-проходной схеме аутентификации с открытым ключом.

Фиг. 4 представляет пояснительную схему для описания эффективного 3-проходного алгоритма аутентификации с открытым ключом.

Фиг. 5 представляет пояснительную схему для описания параллелизации эффективного 3-проходного алгоритма аутентификации с открытым ключом.

Фиг. 6 представляет пояснительную схему для описания эффективного 3-проходного алгоритма аутентификации с открытым ключом.

Фиг. 7 представляет пояснительную схему для описания примера структуры эффективного 5-проходного алгоритма аутентификации с открытым ключом.

Фиг. 8 представляет пояснительную схему для описания параллелизации эффективного 5-проходного алгоритма аутентификации с открытым ключом.

Фиг. 9 представляет пояснительную схему для описания параллелизации эффективного 5-проходного алгоритма аутентификации с открытым ключом.

Фиг. 10 представляет пояснительную схему для описания способа модификации эффективного 3-проходного алгоритма аутентификации с открытым ключом для преобразования его в алгоритм цифровой подписи.

Фиг. 11 представляет пояснительную схему для описания способа модификации эффективного 5-проходного алгоритма аутентификации с открытым ключом для преобразования его в алгоритм цифровой подписи.

Фиг. 12 представляет пояснительную схему для описания примера структуры хэш-функции.

Фиг. 13 представляет пояснительную схему для описания способа верификации подписи (нормальный способ установки), относящегося к алгоритму цифровой подписи на основе 3-проходной схеме.

Фиг. 14 представляет пояснительную схему для описания способа верификации подписи (способ уменьшения объема памяти), относящегося к алгоритму цифровой подписи на основе 3-проходной схемы.

Фиг. 15 представляет пояснительную схему для описания способа верификации подписи (нормальный способ установки), относящегося к алгоритму цифровой подписи на основе 5-проходной схеме.

Фиг. 16 представляет пояснительную схему для описания способа верификации подписи (способ уменьшения объема памяти), относящегося к алгоритму цифровой подписи на основе 5-проходной схемы.

Фиг. 17 представляет пояснительную схему для описания способа (способ #1 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 18 представляет пояснительную схему для описания способа (способ #2 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 19 представляет пояснительную схему для описания способа (способ #3 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 20 представляет пояснительную схему для описания способа (способ #3 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 21 представляет пояснительную схему для описания способа (способ #3 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 22 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 23 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 24 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 25 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 26 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 27 представляет пояснительную схему для описания способа структурирования данных (способ #2 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

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

Осуществление изобретения

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

Порядок описания

Здесь будет коротко изложен порядок описания вариантов настоящего изобретения, которое будет приведено ниже. Сначала, структура алгоритма аутентификации с открытым ключом будет рассмотрена со ссылками на Фиг. 1. Далее, структура алгоритма цифровой подписи будет рассмотрена со ссылками на Фиг. 2. Затем, n-проходный алгоритм аутентификации с открытым ключом будет рассмотрен со ссылками на Фиг. 3.

Далее, 3-проходный алгоритм аутентификации с открытым ключом будет рассмотрен со ссылками на Фиг. 4-6. Затем, 5-проходный алгоритм аутентификации с открытым ключом будет рассмотрен со ссылками на Фиг. 7-9. Далее, способ модификации эффективных 3-проходных и 5-проходных алгоритмов аутентификации с открытым ключом для преобразования этих алгоритмов в алгоритмы цифровой подписи будет рассмотрен со ссылками на Фиг. 10-11.

Затем, способы уменьшения объемов памяти, необходимых для верификации подписи во время выполнения алгоритмов цифровой подписи, относящихся к описанным здесь вариантам, будут рассмотрены со ссылками на Фиг. 12-16. Далее, способы эффективного выделения троичных случайных чисел из двоичных случайных чисел будут рассмотрены со ссылками Фиг. 17-21. Затем, способы эффективной подстановки коэффициентов многочленов от нескольких переменных будут рассмотрены со ссылками Фиг. 22-27. Далее, пример конфигурации аппаратуры в устройстве для обработки информации, способном реализовать каждый алгоритм согласно вариантам настоящего изобретения будет рассмотрен со ссылками Фиг. 28. Наконец, будет кратко изложено резюме технических принципов вариантов настоящего изобретения и преимуществ, обеспечиваемых этими техническими принципами.

Содержание

1. Введение

1-1: Алгоритм аутентификации с открытым ключом

1-2: Алгоритмы цифровой подписи

1-3: N-проходный алгоритм аутентификации с открытым ключом

2. Структуры 3-проходных алгоритмов аутентификации с открытым ключом

2-1: Пример конкретной структуры алгоритма

2-2: Пример структуры параллелизованного алгоритма

2-3: Пример структуры алгоритма на основе кубического многочлена от нескольких переменных

3: Структура 5-проходного алгоритма аутентификации с открытым ключом

3-1: Пример конкретной структуры алгоритма

3-2: Пример структуры параллелизованного алгоритма

3-3: Пример структуры алгоритма на основе кубического многочлена от нескольких переменных

4: Модификация алгоритма цифровой подписи

4-1: Модификация 3-проходного алгоритма аутентификации с открытым ключом и преобразование его в алгоритм цифровой подписи

4-2: Модификация 5-проходного алгоритма аутентификации с открытым ключом и преобразование его в алгоритм цифровой подписи

5: Способ уменьшения объема памяти, необходимого для верификации подписи

5-1: Структура хэш-функции

5-2: Пример применения 3-проходного алгоритма цифровой подписи

5-3: Пример применения 5-проходного алгоритма цифровой подписи

6: Способ выделения последовательности троичных случайных чисел из последовательности двоичных случайных чисел

6-1: Способ #1 выделения (2-битовое группирование)

6-2: Способ #2 выделения (нет группирования)

6-3: Способ #3 выделения (k-битовое группирование)

6-3-1: Базовая структура

6-3-2: Дополнительный способ выделения

7: Способ эффективной подстановки коэффициентов в многочлены от нескольких переменных

7-1: Базовое определение

7-2: Структурирование данных

7-2-1: Способ #1 структурирования

7-2-2: Способ #2 структурирования

7-2-3: Способ #3 структурирования

8: Пример конфигурации аппаратуры

9: Резюме

1. Введение

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

1-1: Алгоритм аутентификации с открытым ключом

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

Аутентификация с открытым ключом используется, когда человек (доказывающая сторона) подтверждает другому человеку (проверяющей стороне), что это он сам, с использованием открытого ключа pk и секретного ключа sk. Например, открытый ключ ркд доказывающей стороны А делают известным проверяющей стороне В. С другой стороны, доказывающая сторона А сохраняет свой секретный ключ sk_A в секрете. Согласно принципу алгоритма аутентификации с открытым ключом человек, который знает секретный ключ sk_A, соответствующий открытому ключу pk_A, рассматривается как сама доказывающая сторона А.

Для того чтобы доказывающая сторона А доказала проверяющей стороне В, что она действительно является доказывающей стороной А, с использованием процедуры алгоритма аутентификации с открытым ключом, эта доказывающая сторона А предоставляет проверяющей стороне В доказательство, что она знает секретный ключ sk_A, соответствующий открытому ключу pk_A. Тогда проверяющей стороне В представляют доказательство, указывающее, что доказывающая сторона А знает секретный ключ sk_A, и если проверяющая сторона В способна подтвердить это доказательство, достоверность доказывающей стороны А (факт, что она действительно является доказывающей стороной А) считается и является доказанной.

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

Первое условие формулируется так: «уменьшить насколько это возможно вероятность фальсификации со стороны фальсификатора, не имеющего секретного ключа sk, во время выполнения интерактивного протокола». Состояние, когда это первое условие выполняется, называется «корректность» (soundness). Другими словами, корректность означает, что «фальсификатор, с большой вероятностью не обладающий секретным ключом sk, ничего не фальсифицировал во время выполнения интерактивного протокола». Второе условие формулируется так: «даже при выполнении интерактивного протокола совсем не происходит утечки информации о секретном ключе sk_A доказывающей стороны А к проверяющей стороне В». Состояние, когда это второе условие выполняется, называется «нулевое разглашение» (zero knowledge).

Обеспечение безопасности с использованием алгоритма аутентификации с открытым ключом включает применение интерактивного протокола (далее - протокол взаимодействия), обладающего и корректностью, и нулевым разглашением. Если, гипотетически, процедура аутентификации осуществляется с использованием протокола взаимодействия, не обладающего корректностью и нулевым разглашением, появится конечная (ненулевая) вероятность фальшивой верификации и конечная вероятность разглашения информации секретного ключа, так что в результате достоверность доказывающей стороны не будет доказана, даже если сама процедура будет завершена успешно. Следовательно, вопрос о том, как обеспечить корректность и нулевое разглашение сеансового протокола, является очень важным.

Модель

В модели алгоритма аутентификации с открытым ключом присутствуют два субъекта - а именно доказывающая сторона и проверяющая сторона, как показано на Фиг. 1. Доказывающая сторона генерирует пару из открытого ключа pk и секретного ключа sk с использованием алгоритма Gen генерации ключей. Затем доказывающая сторона выполняет протокол взаимодействия с проверяющей стороной с использованием пары из секретного ключа sk и открытого ключа pk, сформированных посредством алгоритма Gen генерации ключей. В этот момент доказывающая сторона выполняет протокол взаимодействия с использованием алгоритма Р доказывающей стороны. Как описано выше, в рамках протокола взаимодействия доказывающая сторона предоставляет проверяющей стороне доказательства, что она обладает секретным ключом sk, с использованием алгоритма Р доказывающей стороны.

С другой стороны, проверяющая сторона выполняет протокол взаимодействия с использованием алгоритма V проверяющей стороны и тем самым проверяет, обладает ли доказывающая сторона секретным ключом, соответствующим открытому ключу, который опубликовала доказывающая сторона. Иными словами, проверяющая сторона представляет собой субъект, проверяющий, обладает ли доказывающая сторона секретным ключом, соответствующим открытому ключу. Как описано здесь, модель алгоритма аутентификации с открытым ключом конфигурирована из двух субъектов, а именно - доказывающей стороны и проверяющей стороны, и трех алгоритмов, а именно - алгоритма Gen генерации ключей, алгоритма Р доказывающей стороны и алгоритма V проверяющей стороны.

Кроме того, термины «доказывающая сторона» ("prover") и «проверяющая сторона» ("verifier") используются в последующем описании, но они везде обозначают строго «субъекты». Таким образом, субъект, выполняющий алгоритм Gen генерации ключей и алгоритм Р доказывающей стороны, представляет собой устройство для обработки информации, соответствующее субъекту «доказывающая сторона». Аналогично, субъект, выполняющий алгоритм V проверяющей стороны, представляет собой устройство для обработки информации. Пример аппаратной конфигурации устройства для обработки информации показан на Фиг. 28, например. Иными словами, алгоритм Gen генерации ключей, алгоритм Р доказывающей стороны и алгоритм V проверяющей стороны реализуются центральным процессором CPU 902 на основе программы, записанной в постоянном запоминающем устройстве (ПЗУ ROM) 904, в запоминающем устройстве с произвольной выборкой (ЗУПВ RAM) 906, в модуле 920 памяти, на сменном носителе 928 записи или на аналогичном носителе.

Алгоритм Gen генерации ключей

Указанный алгоритм Gen генерации ключей, используется доказывающей стороной. Этот алгоритм Gen генерации ключей представляет собой алгоритм, генерирующий пару и открытого ключа pk и секретного ключа sk, уникальную для соответствующей доказывающей стороны. Открытый ключ pk, сформированный алгоритмом Gen генерации ключей, публикуется. После этого опубликованный открытый ключ pk используется проверяющей стороной. С другой стороны, доказывающая сторона сохраняет секретность сформированного алгоритмом Gen генерации ключей секретного ключа sk. Секретный ключ sk, с которым доказывающая сторона обращается секретно, используется для доказательства проверяющей стороне, что доказывающая сторона обладает секретным ключом sk, соответствующим открытому ключу pk. Формализованно, алгоритм Gen генерации ключей представлен формулой (1) ниже в качестве алгоритма, получающего на вход параметр защищенности 1λ (λ - целое число, равное 0 или больше) и генерирующего на выходе секретный ключ sk и открытый ключ pk.

Алгоритм Р доказывающей стороны

Рассматриваемый алгоритм Р доказывающей стороны используется доказывающей стороной. Алгоритм Р доказывающей стороны представляет собой алгоритм для доказывания проверяющей стороне, что доказывающая сторона обла