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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

Например, в качестве схем цифровой подписи, которые принимают задачу многомерного полинома в качестве основы безопасности, известны схемы, основанные на криптографии Мацумото-Имаи (Matsumoto-Imai (MI)), криптографии, использующие уравнения скрытого поля (HFE), схемы подписи "масло-уксус" (OV) и криптографии, использующие способ ручного преобразования (ТТМ). Например, схема цифровой подписи на основе HFE раскрыта в следующей непатентной литературе 1 и 2.

Перечень цитируемой литературы

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

Непатентная литература 1: Jacques Patarin, «Asymmetric Cryptography with a Hidden Monomial», CRYPTO 1996, pp.45-60

Непатентная литература 2: 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-трудная задача, которую трудно решить даже в том случае, когда используется квантовый компьютер. Обычно схема аутентификации ключа общего доступа, которая имеет задачу многомерного полинома, типичным примером которой служит HFE или тому подобное, использует многостепенную многомерную систему уравнений со специальной функцией-ловушкой. Например, выполнены многостепенная многомерная система уравнений F(x₁, …, x_n)=y, зависящих от х₁, …, x_n, и линейные преобразования А и В, и линейные преобразования А и В управляются секретным образом. В этом случае многостепенная многомерная система уравнений F и линейные преобразования А и В представляют собой функции-ловушки.

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

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

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

Решение задачи

Согласно варианту осуществления настоящей технологии выполнено устройство обработки информации содержащее блок генерирования сообщения для генерирования сообщения на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который является элементом из набора Kⁿ, блок подачи сообщения, который подает сообщение верифицирующей стороне, хранящей пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), блок генерирования промежуточной информации для генерирования третьей информации на основании первой информации, произвольно выбранной с помощью верифицирующей стороны, и второй информации, полученной во время генерирования сообщения, блок предоставления промежуточной информации для предоставления третьей информации верифицирующей стороне, и блок подачи отклика для предоставления верифицирующей стороне информации отклика, соответствующей образцу верифицирующей стороны, который верифицирующая сторона выбирает из k (где k≥2) образцов верифицирующей стороны. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой ключи общего доступа. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верифицирующей стороны, соответствующего информации отклика на основании ключей общего доступа, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, х₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнено устройство обработки информации, включающее в себя блок хранения информации для хранения пары многостепенных многомерных полиномов F=(f₁, …, f_m) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), блок получения сообщения для получения сообщения, сгенерированного на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, блок предоставления информации для предоставления произвольно выбранной первой информации доказывающей стороне, которая выдает сообщение, блок получения промежуточной информации для получения третью информации, сгенерированной доказывающей стороной на основании первой информации и второй информации, полученной во время генерирования сообщения, блок предоставления информации об образце для предоставления доказывающей стороне информации относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, блок получения отклика для получения информации отклика, соответствующей выбранному образцу верификации, от доказывающей стороны, и блок верификации для верификации того, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1l)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен способ обработки информации, содержащий этапы, на которых генерируют сообщение на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который представляет собой элемент из набора Kⁿ, подают сообщение на верифицирующей стороне, хранящей пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), генерируют третью информации на основании первой информации, произвольно выбранной верифицирующей стороной, и второй информации, полученной во время генерирования сообщения, предоставляют третью информацию верифицирующей стороне и предоставляет верифицирующей стороне информацию отклика, соответствующую образцу верификации, который выбирает верифицирующая сторона из k (где k≥2) образцов верификации. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен способ обработки информации, включающий в себя этапы, на которых, с помощью устройства обработки информации, которое хранит пару многостепенных многомерных полиномов F=(f₁, …, f_m) и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), получают сообщение, сгенерированное на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, предоставляют произвольно выбранную первую информацию доказывающей стороне, которая выдает сообщение, получают третью информацию, сгенерированную доказывающей стороной, на основании первой информации и второй информации, полученной во время генерирования сообщения, предоставляют доказывающей стороне информацию относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, и получают информацию отклика, соответствующую выбранному образцу верификации, от доказывающей стороны, верифицируют то, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнена программа, вызывающая выполнение компьютером функции генерирования сообщения, выполненной с возможностью генерирования сообщения на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который представляет собой элемент из набора Kⁿ, функции подачи сообщения, выполненной с возможностью подачи сообщения на верифицирующую сторону, хранящую пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функции генерирования промежуточной информации, выполненной с возможностью генерирования третьей информации на основании первой информации, произвольно выбранной верифицирующей стороной, и второй информации, полученной во время генерирования сообщения, функцию предоставления промежуточной информации с возможностью предоставления третьей информации верифицирующей стороне и функцию подачи отклика с возможностью предоставления верифицирующей стороне информации отклика, соответствующей образцу верификации, который выбирает верифицирующая сторона из k (где k≥2) образцов верификации. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнена программа, вызывающая выполнение компьютером функции хранения информации, выполненной с возможностью хранения пары многостепенных многомерных полиномов F=(f1, fm) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функцию получения сообщения, выполненной с возможностью получения сообщения, выработанного на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, функции предоставления информации, выполненной с возможностью предоставления произвольно выбранной первой информации доказывающей стороне, которая выдает сообщение, функции получения промежуточной информации, выполненной с возможностью получения третьей информации, сгенерированной доказывающей стороной, на основании первой информации и второй информации, полученной во время генерирования сообщения, функции предоставления информации об образце, выполненной с возможностью предоставления доказывающей стороне информации относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, функции получения отклика, выполненной с возможностью получения информации отклика, соответствующей выбранному образцу верификации, от доказывающей стороны, и функции верификации, выполненной с возможностью верификации того, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+х₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1,2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен машиночитаемый носитель информации, хранящий программу, причем программа вызывает выполнение компьютером функции генерирования сообщения, выполненной с возможностью генерирования сообщения на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который представляет собой элемент из набора Kⁿ, функции подачи сообщения, выполненной с возможностью подачи сообщения на верифицирующей стороне, хранящей пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функции генерирования промежуточной информации, выполненной с возможностью генерирования третьей информации на основании первой информации, произвольно выбранной верифицирующей стороной, и второй информации, полученной во время генерирования сообщения, функции предоставления промежуточной информации, выполненной с возможностью предоставления третьей информации верифицирующей стороне и функции подачи отклика с возможностью предоставления верифицирующей стороне информации отклика, соответствующей образцу верификации, который выбирает верифицирующая сторона из k (где k≥2) образцов верификации. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен машиночитаемый носитель информации, хранящий программу, причем программа вызывает выполнение компьютером функции хранения информации, выполненной с возможностью хранения пары многостепенных многомерных полиномов F=(f₁, …, f_m) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функции получения сообщения, выполненной с возможностью получения сообщения, сгенерированного на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, функции предоставления информации, выполненной с возможностью предоставления произвольно выбранной первой информации доказывающей стороне, которая выдает сообщение, функции получения промежуточной информации, выполненной с возможностью получения третьей информации, сгенерированной доказывающей стороной, на основании первой информации и второй информации, полученной во время генерирования сообщения, функцию предоставления информации об образце с возможностью предоставления доказывающей стороне информации относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, функции получения отклика, выполненной с возможностью получения информации отклика, соответствующей выбранному образцу верификации, от доказывающей стороны и функции верификации, выполненной с возможностью верификации того, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам х₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Полезные эффекты изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Последовательность описания

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

Далее, со ссылкой на фиг.4-8, будет описан пример структуры алгоритма, который относится к 3-проходной схеме аутентификации открытого ключа. Затем, со ссылкой на фиг.5-17, будет описан пример структуры алгоритма, который относится к 5-проходной схеме аутентификации открытого ключа. Далее, со ссылкой на фиг.18-21, будет описан способ модификации эффективных алгоритмов, который относится к 3-проходной и 5-проходной схемам аутентификации открытого ключа, в алгоритмах схемы цифровой подписи.

Далее, со ссылкой на фиг.22-27, будет описана параллельно-последовательная структура и последовательно-параллельная структура эффективных алгоритмов, которые относятся к 3-проходной и 5-проходной схемам аутентификации открытого ключа. Далее, со ссылкой на фиг.28, будет описан пример конфигурации аппаратных средств устройства обработки информации с возможностью реализации каждого алгоритм согласно первому и второму вариантам осуществления настоящей технологии. В конце будет кратко изложена техническая сущность настоящих вариантов осуществления и операционных преимущественных эффектов, полученных из технической сущности.

Содержание

1. Введение

1.1. Алгоритм схемы аутентификации открытого ключа

1.2. Алгоритмы для схемы цифровой подписи

1.3. N-проходная схема аутентификации открытого ключа

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

2.1. Пример конкретной структуры алгоритма

2.2. Эффективный алгоритм, основанный на квадратичном многомерном полиноме

2.2.1. Основная структура

2.2.2. Распараллеленный алгоритм

2.3. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (схема #1)

2.3.1. Основная структура

2.3.2. Распараллеленный алгоритм

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

3.1. Пример конкретной структуры алгоритма

3.2: Эффективный алгоритм, основанный на квадратичном многомерном полиноме

3.2.1. Основная структура

3.2.2. Распараллеленный алгоритм

3.3. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (первый вариант осуществления)

3.3.1. Основная структура

3.3.2. Распараллеленный алгоритм

3.4. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (второй вариант осуществления)

3.4.1. Основная структура

3.4.2. Распараллеленный алгоритм (пример 1 структуры)

3.4.3. Распараллеленный алгоритм (пример 2 структуры: высокая эффективность)

3.4.4. Распараллеленный алгоритм (пример 2 структуры: более высокая эффективность)

4. Модификация схемы цифровой подписи

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

4.1.1. Алгоритм цифровой подписи (пример 1 структуры)

4.1.2. Алгоритм цифровой подписи (пример 2 структуры: высокая эффективность)

4.2. Модификация 5-проходной схемы аутентификации открытого ключа в схему цифровой подписи

4.2.1. Алгоритм цифровой подписи (пример 1 структуры)

4.2.2. Алгоритм цифровой подписи (пример 2 структуры: высокая эффективность)

5. Алгоритм гибридного типа

5.1. Алгоритм гибридного типа, который относится к 3-проходной схеме аутентификации открытого ключа

5.1.1. Параллельно-последовательный алгоритм

5.1.2. Последовательно-параллельный алгоритм

5.2. Алгоритм гибридного типа, который относится к 5-проходной схеме аутентификации открытого ключа

5.2.1. Параллельно-последовательный алгоритм (пример #1 структуры)

5.2.2. Параллельно-последовательный алгоритм (пример #2 структуры)

5.2.3. Последовательно-параллельный алгоритм (пример #1 структуры)

5.2.4. Последовательно-параллельный алгоритм (пример #2 структуры)

6. Приложение

6.1. Способ установки параметра системы

6.2. Способ реагирования на нерегулярный вызов

6.2.1. Способ реагирования доказывающей стороной

6.2.2. Способ реагирования верифицирующей стороной

7. Пример конфигурации аппаратных средств

8. Заключение

1. Введение

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

1.1. Алгоритм схемы аутентификации открытого ключа

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

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