РЕАЛИЗАЦИЯ ПРОТОКОЛА АУТЕНТИФИКАЦИИ ШНОРРА В КОДЕ СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ

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

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

В качестве недостатка данного протокола можно отметить, что вторую часть протокола Фиата-Шамира надо повторять многократно, например до 50 раз. Это связано с тем, что разрядность вопроса равна единице. В этом случае вероятность имитации ответа составляет . Это очень высокая вероятность. Чтобы понизить ее предлагается выполнять вторую часть протокола многократно. Если число раундов протокола будет равно W=50, то вероятность имитации ответа составит . В качестве недостатка протокола Фиата-Шамира можно выделить низкую скорость процесса аутентификации. Устранить данный недостаток позволяет протокол аутентификации Шнорра с нулевым разглашением знаний [2].

В отличие от протокола Фиат-Шамира данный протокол проводит аутентификацию претендента за один раунд. Протокол также имеет две части. В первой части рассматривается вопрос получения ключей. Секретный ключ используется претендентом. Открытый ключ – нужен проверяющему для проведения проверки ответов.

Однако данный протокол имеет недостаток. Согласно [2] к данному протоколу были выдвинуты следующие требования. Чтобы обеспечить высокую криптографическую стойкость к подбору правильного ответа на поставленный вопрос разработчики предложили, чтобы модуль А имел не менее 512 разрядов. Размерность второго модуля В, который является делителем числа А, должна составлять не менее 140 двоичных разрядов. При этом параметр С, который используется во второй части протокола должен находиться в пределах от 52 до 72 двоичных разрядов.

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

Устранить данный недостаток, то есть повысить скорость выполнения процедуры аутентификации, можно, если использовать коды системы остаточных классов. Это параллельные арифметические коды, в которых вычисления выполняются параллельно по основаниям. При этом аргументы выступают остатки, которые получаются при делении целых числе на числа, которые выбраны в качестве оснований СОК. Рассмотрим реализацию протокола аутентификации Шнорра в коде СОК.

Как отмечалось ранее, протокол Шнорра проводит аутентификацию претендента за один раунд. Протокол также имеет две части. В первой части рассматривается вопрос получения ключей. Секретный ключ используется претендентом. Открытый ключ – нужен проверяющему для проведения проверки ответов. Рассмотрим первую часть протокола.

Как отмечалось ранее, протокол Шнорра проводит аутентификацию претендента за один раунд. Протокол также имеет две части. В первой части рассматривается вопрос получения ключей. Секретный ключ используется претендентом. Открытый ключ – нужен проверяющему для проведения проверки ответов. Рассмотрим первую часть протокола, которая состоит из этапов.

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

   ,                                                 (1)

где А – большое простое число, по которому реализуется протокол Шнорра;

 – рабочий диапазон кода.

Затем вычисляются функции Эйлера для каждого основания

.                       (2)

После этого претендент находит простые числа , которые являются делителями соответствующих функций Эйлера

.                            (3)

2 этап. Претендент находит такие числа N_i, где , для которого справедливо сравнение

.                                            (4)

3этап. Претендент производит выбор чисел К_i, где , которые является секретным ключом. Данное число должно удовлетворять 

.                                               (5)

4 этап.  Претендент производит вычисление открытого ключа протокола аутентификации

 ,                                          (6)

где .

Вторая часть протокола включает в себя этапы аутентификации претендента.

1 этап. Претендент находит набор случайных чисел Х_i, где . Данное число должно удовлетворять

.                                      (7)

2 этап. Претендент приступает к вычислению

 ,                                     (8)

где .

Полученный результат претендент по радиоканалу передает на проверяющую сторону V.

3 этап. Проверяющий готовит вопрос. Для этого он находит случайные числа S_i. Данное число выбирается из условия

,                                        (9)

где ; .

Сгенерированный вопрос  передается на сторону претендента.

4 этап. Претендент, получив вопрос , должен вычислить ответ

,                                (10)

где.

Вычисленный ответ  на вопрос передается по радиоканалу на сторону проверяющего.

5 этап. Проверяющий осуществляет проверку полученного от претендента ответа . Для этого используется выражение

  .                                 (11)

где .

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

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

1 этап. Пусть задано простое число А = 10369. Претендент находит основания  кода СОК. Данные основания обеспечивают рабочий диапазон равный . Таким образом, выполняется условие (1), то есть . В этом случае не будет снижение стойкости протокола аутентификации к имитации правильного ответа.

Затем претендент вычисляет функции Эйлера для каждого основания

.

После претендент находит простые числа , которые являются делителями соответствующих функций Эйлера

.

2 этап. Претендент находит такие числа N_i, которые удовлетворяют условию (4). Он выбрал числа N₁=3, N₂=3, N_3,=3, так как для них справедливо

, ,  .

3 этап. Претендент производит выбор чисел К_i, который является секретным ключом. Данное число должно удовлетворять (5). Претендент выбрал числа .

4 этап.  Претендент производит вычисление открытого ключа протокола аутентификации, используя выражение (6)

 .

 .

 .

Вторая часть протокола включает в себя этапы аутентификации претендента.

1 этап. Претендент находит набор случайных чисел

. Данное число должно удовлетворять (7).

2 этап. Претендент приступает к вычислению

 .

 .

 .

Полученный результат  претендент по радиоканалу передает на проверяющую сторону V.

3 этап. Проверяющий готовит вопрос. Для этого он находит случайные числа . Сгенерированный вопрос передается на сторону  претендента.

4 этап. Претендент, получив вопрос , приступает к вычислению ответа, используя равенство (10)

 .

 .

 .

Вычисленный ответ  на вопрос передается по радиоканалу на сторону проверяющего.

5 этап. Проверяющий осуществляет проверку полученного от претендента ответа  с помощью (11)

 .

 .

 .

Затем проверяющий сравнивает полученный результат с полученным числом . Так результат совпал с данным числом

,

то проверяющая сторона считает претендента легитимным.

Переход к вычислениям по основаниям кода СОК позволяет повысить скорость проведения аутентификации. В рассмотренном примере было выбрано простое число А, которое представляется в виде 14-разрядного двоичного кода. При использовании кода СОК самым большим основанием было число 83. Данное число представляется с помощью 7-разрядного двоичного кода. Так как временные затраты на реализацию операций умножения и возведения в степень по модулю прямо пропорционально разрядности операндов, то применение кодов СОК повысило скорость аутентификации в 2 раза без учета немодульных операций прямого и обратного преобразований.