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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

Среди этих задач другие задачи, кроме задачи поиска сечения на алгебраической поверхности, известны, как NP-трудно решаемые. В качестве варианта применения, например, в непатентной литературе 1 и в непатентной литературе 2, упомянутых ниже, раскрыты схемы аутентификации с открытым ключом на основе задачи декодирования синдрома. Кроме того, в непатентной литературе 3, упомянутой ниже, раскрыта схема аутентификации с открытым ключом на основе задачи ядра с перестановками. Кроме них, также предложена схема аутентификации с открытым ключом на основе задачи ограниченных линейных уравнений, схема аутентификации с открытым ключом на основе задача восприятия с перестановками и т.п.

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

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

Непатентная Литература 1: Jacques Stern, A New Identification Scheme Based on Syndrome Decoding, CRYPTO 1993, p13-21

Непатентная литература 2: Jacques Stern, A New Paradigm for Public Key Identification, IEEE Transactions on Information Theory, 1996, p13-21

Непатентная литература 3: Adi Shamir, An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract), CRYPTO 1989, p606-609

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

Техническая задача

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

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

Существующая схема аутентификации с открытым ключом представляет собой схемы, в которых контролер подтверждает для проверяющего “знание значения s, которое удовлетворяет y = F (s) для данного y”, используя одну пару ключей (открытый ключ y, секретный ключ s). В соответствии с этим, если было выполнено взаимодействие, которое было принято при проверке, не было возможности предотвратить знание проверяющим информации о том, что “контролер, который выполнил взаимодействие, использовал значение s”. Кроме того, в конфигурации с параллельным повторением схемы аутентификации с открытым ключом этого типа, если устойчивость к коллизии не была гарантирована для F, не было известно, был ли абсолютно гарантирован достаточный уровень безопасности для активной атаки, или нет. Фактически, устойчивость к коллизиям не гарантируется для функции F, используемой в схемах аутентификации с открытым ключом, описанных выше.

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

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

В соответствии с аспектом настоящего раскрытия, для достижения описанной выше цели предусмотрено устройство аутентификации, которое включает в себя модуль хранения ключей для хранения L (L≥2) секретных ключей s_i(i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют уровню y_i = F (s_i) в отношении набора F многочленов нескольких переменных n-го порядка (n≥2), и модуль выполнения интерактивного протокола для выполнения проверяющим интерактивного протокола для проверки знания (L-1) секретных ключей s_i, удовлетворяющих условию y_i=F(s_i). Модуль выполнения интерактивного протокола не допускает во время выполнения интерактивного протокола проверяющим знания проверяющим, какой секретный ключ S_i был использован.

Кроме того, модуль выполнения интерактивного протокола может включать в себя модуль приема вызова, предназначенный для приема L вызовов Ch_i от проверяющего, модуль выбора вызовов для произвольного выбора (L-1) вызовов Ch_i из L вызовов Ch_i, принимаемых модулем приема вызовов, модуль генерирования ответов для генерирования с использованием секретных ключей S_i(L-1) ответов Rsp_i соответственно на (L-1) вызовов Ch_i, выбираемых модулем выбора вызовов, и модуль передачи ответа для передачи (L-1) ответов Rsp_i, генерируемых модулем генерирования ответов, проверяющему.

Далее, модуль выполнения интерактивного протокола может дополнительно включать в себя модуль передачи сообщения для передачи проверяющему сообщений Cmt_i, каждое из которых соответствует каждому из L секретных ключей S_i. В этом случае модуль приема вызовов принимает вызов Ch_i, указывающий схему проверки, выбранную из k (k≥2) схем проверки с помощью проверяющего, в соответствии с каждым сообщением Cmt_i, переданным модулем передачи сообщения.

Далее, в случае сообщения Cmt_i=(c_{i, 1}, …, c_{i, N}) модуль передачи сообщения может вычислить новое сообщение Cmt'=Н(Cmt₁, …, Cmt_L) с использованием односторонней функции H и передать это сообщение Cmt' проверяющему, а модуль передачи ответа может передавать, вместе с ответом Rsp_i, элемент сообщения Cmt_i, о том, что проверяющий не может осуществить восстановление, даже когда используется ответ Rsp_i.

Кроме того, модуль хранения ключей может не хранить один секретный ключ s_i0(1≤i₀≤L) среди L секретных ключей S_i. В этом случае модуль выполнения интерактивного протокола выполняет, на основе алгоритма фальсификации, обработку, относящуюся к секретному ключу S_i0, которая должна подлежит выполнению в интерактивном протоколе.

Кроме того, в соответствии с другим аспектом настоящего раскрытия, для достижения описанной выше цели предусмотрено устройство аутентификации, которое включает в себя модуль хранения ключей для хранения L секретных ключей S_i(i=1-L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i) в отношении набора F многочленов нескольких переменных n-го порядка (n≥2), модуль приема вызовов для приема Q наборов (Q≥2) из L вызовов CH_i ^(j)(j=1-Q) от проверяющего, модуль выбора вызовов для произвольного выбора одного набора из L вызовов CH_i ^(j) из Q наборов из L вызовов CH_i ^(j), принятых модулем приема вызовов, модуль генерирования ответов для генерирования с использованием секретных ключей s_i L ответов Rsp_i соответственно для L вызовов CH_i ^(j), выбранных модулем выбора вызовов, и модуль передачи ответа для передачи L ответов Rsp_i, генерируемых модулем генерирования ответа, проверяющему.

Кроме того, модуль выполнения интерактивного протокола может дополнительно включать в себя модуль передачи сообщений для передачи в проверочное устройство сообщений Cmt_i соответственно соответствующих L секретным ключам S_i. В этом случае модуль приема вызовов принимает вызов Chi_i ^(j), указывающий схему проверки, выбранную из k (k≥2) схем проверки проверяющим в соответствии с каждым сообщением Cmt_i, переданным модулем передачи сообщения.

Кроме того, в случае сообщения Cmt_i=(c_{i, 1}, …, c_{i, N}), модуль передачи сообщения может рассчитать новое сообщение Cmt'=H(Cmt₁, …, Cmt_L) с использованием односторонней функции H и передать это сообщение Cmt' проверяющему, а модуль передачи ответа может передать, вместе с ответом Rsp_i, элемент сообщения Cmt_i, который проверяющий не может восстановить, даже при использовании этого ответа Rsp_i.

Кроме того, в соответствии с другим аспектом настоящего раскрытия для достижения описанной выше цели предусмотрен способ аутентификации, который включает в себя этап генерирования ключей для генерирования L (L≥2) секретных ключей S_i (i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i), относительно набора F многочленов нескольких переменных n-го порядка (n≥2), и этап выполнения интерактивного протокола для выполнения, с помощью проверяющего, интерактивного протокола для подтверждения знания (L-1) секретных ключей S_i, которые удовлетворяют условию y_i=F(s_i). Этап выполнения интерактивного протокола не допускает, чтобы во время выполнения интерактивного протокола с помощью проверяющего, проверяющий знал, какой секретный ключ S_i был использован.

Кроме того, в соответствии с другим аспектом настоящего раскрытия для достижения описанной выше цели предусмотрена программа, обеспечивающая реализацию компьютером функции хранения ключей, состоящей в хранении L (L≥2) секретных ключей S_i (i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i) относительно набора F многочленов нескольких переменных n-го порядка (n≥2), и функции исполнения интерактивного протокола, состоящей в выполнении с помощью проверяющего интерактивного протокола для подтверждения знания (L-1) секретных ключей s_i, которые удовлетворяют условию y_i=F(s_i). Функция исполнения интерактивного протокола не допускает, чтобы во время выполнения интерактивного протокола с помощью проверяющего, проверяющий знал, какой секретный ключ S_i был использован.

Кроме того, в соответствии с другим аспектом настоящего раскрытия, для достижения описанной выше цели предусмотрен способ аутентификации, который включает в себя этап генерирования ключей для генерирования L секретных ключей s_i (i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i) относительно набора F многочленов нескольких переменных n-го порядка (n≥2), этап приема вызовов для приема Q наборов (Q≥2) из L вызовов Ch_i ^(j) (j = от 1 до Q) для проверяющего, этап выбора вызовов, на котором произвольно выбирают один набор из L вызовов Ch_i ^(j) из Q наборов L вызовов Ch_i ^(j), которые были приняты на этапе приема вызовов, этап генерирования ответа для генерирования с использованием секретных ключей s_i L ответов Rsp_i соответственно для L вызовов Chp_i ^(j), выбранных на этапе выбора вызовов, и этап передачи ответов для передачи проверяющему L ответов Rsp_i, сгенерированных на этапе генерирования ответов.

Кроме того, в соответствии с другим аспектом настоящего раскрытия для достижения описанной выше цели предусмотрена программа, обеспечивающая реализацию компьютером функции хранения ключей, состоящей в хранении L секретных ключей S_i (i = от 1 до L) и L открытых ключей y_i, удовлетворяющих условию y_i=F(s_i) относительно многочленов F нескольких переменных n-го порядка (n≥2), функции приема вызовов, состоящей в приеме Q наборов (Q≥2) из L вызовов Ch_i ^(j) (j = от 1 до Q) от проверяющего, функции выбора вызовов, состоящей в произвольном выборе одного набора из L вызовов Ch_i ^(j) из Q наборов из L вызовов Ch_i ^(j), принятых функцией приема вызовов, функции генерирования ответа, состоящей в генерировании с использованием секретных ключей S_i L ответов Rsp_i соответственно для L вызовов Ch_i ^(j), выбранных функцией выбора вызовов, и функции передачи ответов, состоящей в передаче L ответов Rspi, сгенерированных функцией генерирования ответов, проверяющему. В соответствии с другим вариантом осуществления настоящего раскрытия, предусмотрен считываемый компьютером носитель записи, на котором записана программа.

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

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

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

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

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

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

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

на фиг.5 показана пояснительная схема для описания конфигурации порядкового повторения интерактивного протокола;

на фиг.6 показана пояснительная схема для описания конфигурации с параллельным повторением интерактивного протокола;

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

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

на фиг.9 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a;

на фиг.10 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример 1);

на фиг.11 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример 2);

на фиг.12 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример 3);

на фиг.13 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b;

на фиг.14 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b (модифицированный пример);

на фиг.15 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a;

на фиг.16 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример);

на фиг.17 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b;

на фиг.18 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b (модифицированный пример);

на фиг.19 показана пояснительная схема для описания способа уменьшения величины передаваемых данных в интерактивном протоколе схемы аутентификации с открытым ключом SSH10a;

на фиг.20 показана пояснительная схема для описания способа уменьшения величины передаваемых данных в интерактивном протоколе схемы аутентификации с открытым ключом SSH10b; и

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

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

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

Порядок пояснений

Здесь будет кратко установлен порядок пояснений в варианте осуществления настоящего раскрытия, которое будет описано ниже. Вначале структура алгоритма схемы аутентификации с открытым ключом будет описана со ссылкой на фиг.1. Затем схема аутентификации n-ходового открытого ключа будет описана со ссылкой на фиг.2. Затем интерактивный протокол схемы аутентификации с открытым ключом SSH10a будет описан со ссылкой на фиг.3. После этого интерактивный протокол схемы аутентификации с открытым ключом SSH10b будет описан со ссылкой на фиг.4. После чего конфигурации повторения интерактивного протокола будут описаны со ссылкой на фиг.5 и 6. В этом пункте будет кратко описан уровень безопасности, достаточный для активной атаки.

Далее, со ссылкой на фиг.7, будет описан алгоритм фальсификации против интерактивного протокола схемы аутентификации с открытым ключом SSH10a. Затем, со ссылкой на фиг.8, будет описан алгоритм фальсификации против интерактивного протокола схемы аутентификации с открытым ключом SSH10b. После, со ссылкой на фиг.9-12, будут описаны способы применения способа, в соответствии с первым вариантом осуществления (настоящий способ №1) настоящего раскрытия для интерактивного протокола схемы аутентификации с открытым ключом SSH10a. Затем способы применения настоящего способа №1 для интерактивного протокола схемы аутентификации с открытым ключом SSH10b будут описаны со ссылкой на фиг.13 и 14.

Потом способы применения способа, в соответствии со вторым вариантом осуществления (настоящий способ №2) настоящего раскрытия, для интерактивного протокола схемы аутентификации с открытым ключом SSH10a, будут описаны со ссылкой на фиг.15 и 16. Затем способы применения настоящего способа №2 для интерактивного протокола для схемы аутентификации с открытым ключом SSH10b будут описаны со ссылкой на фиг.17 и 18. Затем способы уменьшения количества передаваемых данных при интерактивных протоколах, в соответствии с настоящими вариантами осуществления, будут описаны со ссылкой на фиг.19 и 20. Затем пример конфигурации аппаратных средств в устройстве обработки информации, выполненного с возможностью реализации интерактивных протоколов, в соответствии с настоящими вариантами осуществления, будет описан со ссылкой на фиг.21. И, наконец, технические идеи, в соответствии с вариантом осуществления, будут сведены вкратце, и будут кратко описаны эффекты, полученные в результате технических идей.

Содержание описания

1: Введение

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

1-2: Схема аутентификации N-ходового открытого ключа

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

1-4: Интерактивный протокол схемы аутентификации с открытым ключом SSH10b

1-5: Конфигурация повторения интерактивного протокола

1-6: Алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10a

1-7: Алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10b

2: Первый вариант осуществления (настоящий способ №1)

2-1: Общий обзор

2-2: Применение для схемы аутентификации с открытым ключом SSH10a

2-3: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 1)

2-4: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 2)

2-5: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 3)

2-6: Применение для схемы аутентификации с открытым ключом SSH10b

2-7: Применение для схемы аутентификации с открытым ключом SSH10b (модифицированный пример)

3: Второй вариант осуществления (настоящий способ №2)

3-1: Общий обзор

3-2: Применение для схемы аутентификации с открытым ключом SSH10a

3-3: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример)

3-4: Применение для схемы аутентификации с открытым ключом SSH10b

3-5: Применение для схемы аутентификации с открытым ключом SSH10b (модифицированный пример)

4: Приложение

4-1: Расширение схемы

4-2: Схема неинтерактивной аутентификации с открытым ключом

4-3: Способ уменьшения объема вычислений

5: Конфигурация аппаратных средств

6: Краткая сводка

1: Введение

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

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

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

Общий обзор

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

В случае, когда контролер A пытается доказать проверяющему B, что она сама по себе не является контролером, контролер A может выполнить интерактивный протокол с проверяющим B и доказать, что она знает секретный ключ sk_A, соответствующий открытому ключу pk_A. Затем, в случае, когда проверяющий B подтверждает с помощью интерактивного протокола, что контролер A знает секретный ключ sk_A, легитимность контролера A (что она является сама по себе контролером), является доказанной.

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

Первое условие состоит в том, чтобы уменьшить по возможности в максимально возможной степени вероятность фальсификации, установленной во время выполнения интерактивного протокола фальсификатором, который не имеет секретный ключ sk. Удовлетворение этого первого состояния называется ″прочностью″. Другими словами, при использовании прочного интерактивного протокола фальсификатор, не имеющий секретный ключ sk, не устанавливает фальсификация с не пренебрежимо малой вероятностью. Второе условие состоит в том, что, даже если будет выполнен интерактивный протокол, не допускается утечка информации для проверяющего В секретного ключа sk_A контролера A. То, что такое второе условие удовлетворяется, называется “нулевым знанием”.

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

Модель

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

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

Кроме того, выражения ″контролер″ и ″проверяющий″ используются в следующем описании, но эти выражения строго означают объекты. Поэтому, субъект, который выполняет алгоритм Gen генерирования ключа и алгоритм P контролера, представляет собой устройство обработки информации, соответствующее объекту ″контролер″. Аналогично, субъект, который выполняет алгоритм V проверяющего, представляет собой устройство обработки информации. Конфигурация аппаратных средств этих устройств обработки информации показана, например на фиг.21. Таким образом, алгоритм Gen генерирования ключа, алгоритм P контролера и алгоритм V проверяющего выполняет CPU 902 на основе программы, записанной в ROM 904, RAM 906, в модуль 920 накопителя, на съемный носитель 928 записи и т.п.

Алгоритм Gen генерирования ключа

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

Выражение 1

( s k , p k ) ← G e n ( 1 λ )       … ( 1 )

Алгоритм P контролера

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

Алгоритм V проверяющего

Алгоритм V проверяющего используется проверяющим. Алгоритм V проверяющего представляет собой алгоритм для проверки, в интерактивном протоколе, обладает ли контролер секретным ключом sk, соответствующим открытому ключу pk. Алгоритм V проверяющего определен, как алгоритм, который принимает открытый ключ рk контролера, как вход, и затем выводит 0 или 1 (1 бит) после выполнения интерактивного протокола с контролером. Кроме того, предполагается, что в случае вывода 0, контролер является нелегитимным, и в случае вывода 1, предполагается, что контролер является легитимным.

Приложение

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

Выше была описана структура алгоритма схемы аутентификации с открытым ключом.

1-2: Схема аутентификации N-ходового открытого ключа

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

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

В случае схемы аутентификации n-ходового открытого ключа, контролер выполняет процесс, используя алгоритм P контролера (этап 1), и информацию T₁ передают проверяющему. Затем процесс выполняет проверяющий, используя алгоритм V проверяющего (этап 2), и информацию Т₂ передают в контролер. Процессы на (этапе 3) - (этапе n) выполняют аналогично и часть информации Т₃, …, T_n передают, и выполняют процесс (этап n+1). Такая схема аутентификации с открытым ключом на основе интерактивного протокола, где часть информации передают/принимают n раз, называется ″n-ходовой″ схемой для аутентификации открытого ключа.

Выше была представлена n-ходовая схема аутентификации открытого ключа.

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

Далее, со ссылкой на фиг.3, будет описан интерактивный протокол схемы аутентификации с открытым ключом SSH10a. На фиг.3 показана пояснительная схема для описания интерактивного протокол схемы аутентификации с открытым ключом SSH10a. Кроме того, схема аутентификации с открытым ключом SSH10a представляет собой одну из схем аутентификации с открытым ключом, разработанную авторами настоящего изобретения (Sakumoto, Shirai и Hiwatari), которая основана на задаче одновременного решения уравнения с многочленом от нескольких переменных. Кроме того, такая схема аутентификации с открытым ключом SSH10a представляет собой пример 3-ходовой схемы аутентификации с открытым ключом.

Кроме того, задача одновременного решения уравнения от нескольких переменных с множеством порядков представляет собой задачу для получения вектора (s₁, …, s_n)∈Kⁿ, который удовлетворяет (f₁(s₁, …, s_n), …, f_m(s₁, …, s_n))=y, где заданы m многочленов с множеством порядков n переменными f₁(x₁, …, x_n), …, f_m(х₁, …, x_n) на кольце K и вектор y∈K^m. Задача решения одновременного уравнения с множеством переменных второго порядка или выше называется задачей NP-сложности, и она принадлежит к классу задач, которые чрезвычайно трудно решать.

Теперь интерактивный протокол схемы аутентификации с открытым ключом SSH10a конфигурируют на основе алгоритма Gen генерирования ключа, алгоритма P контролера и алгоритма V проверяющего. Далее будет описано содержание каждого алгоритма.

Алгоритм Gen генерир