Рассмотрим вопрос о том, когда можно считать, что владелец открытого ключа, по которому выполняется процедура его аутентификации, в ходе выполнения протокола не передает никаких знаний о секрете проверяющей стороне. Очевидно, что владелец открытого ключа (доказывающий) неминуемо должен воспользоваться своим секретным ключом. Однако, протокол позволяет проверяющему субъекту удостовериться с вероятностью сколь угодно близкой к единице, что аутентифицируемый субъект действительно знает секретный ключ. То, что передаваемые доказывающим значения не содержат в себе информации о секретном ключе, понимается в том смысле, что эти значения не упрощают для потенциального нарушителя задачи вычисления секретного ключа по связанному с ним открытому ключу. Это имеет место в следующих случаях:
Доказывающий передает проверяющему значение, которое заведомо известно последнему.
Доказывающий передает проверяющему значение, которое последний может вычислить самостоятельно до получения ответа.
Доказывающий передает проверяющему случайные значения.
Доказывающий передает проверяющему случайные пары или наборы случайных значений, удовлетворяющих некоторому проверочному соотношению, в которое входит открытый ключ. Однако, статистически неразличимые пары или наборы случайных значений могут быть выработаны нарушителем, используя только открытый ключ доказывающего [14].
Статистическая неразличимость (статистическая равнозначность) наборов случайных значений, формируемых нарушителем, от наборов, формируемых владельцем открытого ключа с использованием своего личного секретного ключа, понимается в том смысле, что эти наборы с одинаковым успехом могут использоваться в попытках вычисления по ним секретного ключа при знании открытого ключа.
Пусть, например, используется проверочное соотношение вида
где p - достаточно большое простое число; б ? число простого порядка r по модулю p; y - открытый ключ доказывающего, вычисляемый по личному секретному ключу и формуле R ? значение фиксатора (разового открытого ключа), вырабатываемого по случайному равновероятному секретному значению и формуле R =. w ? ответ доказывающего, направляемый по открытому каналу связи.
Множество значений , где i = 1, 2, …, q, охватывает все возможные значения фиксатора R. При равновероятном случайном выборе значения k, удовлетворяющего условию k < q, случайное значение R является равновероятным, т.е. принимает с одинаковой вероятностью любое значение из множества Нетрудно видеть, что ответ w вычисляется доказывающим по формуле , поэтому при равновероятном выборе k значение w является равновероятным, т.е. всевозможные значения w имеют одну и ту же вероятность, равную . Всевозможные пары значений (w, R), генерируемых доказывающим и удовлетворяющих соотношению (1), имеют одну и ту же вероятность, равную .
Такие же равновероятные пары (w, R) может сгенерировать и нарушитель. Для этого он генерирует случайное равновероятное значение w < q и вычисляет значение При таком способе генерации пар (w, R), удовлетворяющих соотношению (1), всевозможные значения этих пар имеют одну и ту же вероятность . Таким образом, если наличие равновероятных случайных пар (w, R) из области их возможных значений как-то упрощают задачу дискретного логарифмирования по простому модулю, то нарушитель может самостоятельно сгенерировать равновероятные случайные пары (w, R) в нужном ему количестве без того, чтобы тратить время на ожидание выполнения протокола с нулевым разглашением [16].
3.2 Многораундовые протоколы
Многораундовые протоколы с нулевым разглашением включают многократное повторения трех типовых шагов:
- генерация доказывающим разового случайного секретного ключа и вычисление по нему разового открытого ключа, который передается (объявляется) проверяющему и часто называется фиксатором;
- генерация проверяющим нулевого (r = 0) или единичного (r = 1) запроса с вероятностью 0,5 и направление бита запроса r доказывающему;
- вычисление доказывающим ответа w и направление w проверяющему.
После каждого такого трехшагового раунда проверяющий подставляет полученный им ответ в некоторое проверочное соотношения, в которое входят значения фиксатора, открытого ключа и запроса Если это соотношение выполняется то, проверяющий считает, что текущий ответ правильный [11].
Протокол Фиата-Шамира.
Протокол Фиата-Шамира основан на сложности извлечения квадратного корня по составному модулю, включающему не менее двух больших простых множителей, при условии, что разложение неизвестно. Доказывающий выбирает два больших простых числа p и q и вычисляет модуль n = pq. Затем выбирает в качестве своего личного секретного ключа случайное число s, такое, что 1 ? s ? n - 1, и вычисляет значение (В дальнейшем он будет доказывать проверяющему то, что он знает квадратный корень из y.) Значение y, которое объявляется всем участникам протокола, играет роль открытого ключа в смысле его использования для проверки того, что доказывающий знает s.
Протокол состоит из z-кратного повторения раунда, включающего следующие три шага:
Доказывающий выбирает случайное число k, такое, что 1 ? k ? n - 1, вычисляет значение , называемое фиксатором, и посылает его проверяющему. (Число k играет роль разового секретного ключа и обеспечивает защиту личного секретного ключа от разглашения при направлении ответа, зависящего от s.)
Проверяющий отправляет доказывающему равновероятный случайный бит r (r = 1 или r = 0).
3. Доказывающий вычисляет значение и направляет его проверяющему. (Если r = 1, то . Если r = 0, то w = k. Видно, что по этим двум результатам легко вычисляется секрет s, поэтому значения k должны уничтожаться после каждого раунда или после выполнения всего протокола) [11].
Проверяющий считает ответ верным, если выполняется соотношение
Если r = 1, то должно выполняться . Если r = 0, то получаем . В ходе осуществления протокола выполняется z шагов. Вероятность того, что нарушитель (который не знает секрета s) при выполнении одного раунда может дать положительный ответ, равна , следовательно, вероятность того, что нарушитель может быть принят за пользователя, знающего секрет s, составляет. Выбирая в протоколе достаточно большое число раундов проверки, можно сделать сколь угодно низкой вероятность обмана.
Рассмотрим два возможных варианта действий нарушителя в одном раунде.
В первом варианте он выбирает произвольное число k и передает проверяющему значение . Если он получит от проверяющего запрос r = 0, то направит правильный ответ w = k. Однако правильно ответить на запрос r = 1 нарушитель не имеет возможности.
Во втором варианте нарушитель выбирает произвольное число k и направляет проверяющему число . Если он получит от проверяющего запрос , то направит ответ , который будет принят проверяющим за правильный, поскольку
Однако, на запрос r = 0 нарушитель правильно ответить не сможет.
Таким образом, нарушитель в лучшем случае может правильно ответить только на один вопрос, и в одном раунде с вероятностью 1/2 попытка обмана обнаруживается.
В протоколе нет утечки информации о ключе. Действительно, по запросу проверяющего r = 0 доказывающий направляет ему случайное число k, но проверяющий самостоятельно мог бы сгенерировать случайное число, возвести его в квадрат, получив значение . Самостоятельно полученная пара случайных чисел ничем не хуже, чем пара случайных чисел , полученных от доказывающего. По запросу проверяющего доказывающий направляет ему случайное число w, но проверяющий самостоятельно мог бы сгенерировать случайное число и вычислить случайное значение . Нетрудно видеть, что, если проверяющий сможет вычислить квадратный корень из случайного , то потом он легко вычислит секретный ключ. Идентичную возможность имеет проверяющий при получении пары случайных чисел , связанных соотношением , т. е. если проверяющий сможет вычислить квадратный корень из случайного числа u, то затем он легко вычислит секретное значение s. Таким образом, данные, полученные в процессе выполнения описанного протокола проверяющим от доказывающего, не дают никаких новых возможностей проверяющему для вычисления секретного ключа. В этом смысле следует понимать то, что утечки информации о секрете, в ходе протокола, не происходит [11].
3.3 Трёхшаговые протоколы
Достоинством многораундового протокола Фиата?Шамира является его сравнительно низкая вычислительная сложность ? каждая из сторон участвующих в протоколе выполняет не более 2z модульных умножений, где z - заданное число раундов. Однако, существенным недостатком всех многораундовых протоколов является необходимость выполнения очень большого числа чередующихся пересылок сообщений от доказывающего к проверяющему и обратно. Этот недостаток можно устранить, используя механизм объединения всех случайных однобитовых запросов проверяющего в единую случайную битовую строку, которая направляется доказывающему целиком, и свертки всех ответов в единое значение, которое направляется от доказывающего к проверяющему. То есть, доказывающий вычисляет z различных фиксаторов и отправляет их, в определенном порядке, проверяющему. Доказывающий получает от проверяющего запрос в виде равновероятной случайной z-битовой цепочки, для z соответствующих друг другу пар значений фиксатора и бита запроса вычисляет z ответов и высылает их проверяющему в соответствующем порядке. Таким образом, любой многораундовый протокол может быть данным способом преобразован в трехшаговый протокол, сохраняя его исходную вычислительную сложность.
Некоторые многораундовые протоколы могут быть преобразованы в трехшаговые более практичным способом. Последний способ реализуется за счет использования открытого ключа, представляющего собой z упорядоченных значений, вычисляемых как независимые открытые ключи исходного многораундового протокола [11].
Трехшаговый вариант протокола Фиата?Шамира.
Личный секретный ключ каждого пользователя представляет собой два больших сильных простых числа p и q и z последовательных значений . Открытый ключ вычисляется в виде z упорядоченных значений по формуле
.
Вычислительная трудность извлечения квадратного корня по составному модулю n имеет один порядок с вычислительной трудностью задачи разложения модуля n на простые множители, поэтому можно говорить, что описываемый далее протокол основан на вычислительной трудности задачи факторизации. Процедура проверки подлинности владельца открытого ключа, играющего роль доказывающего, выполняется за следующие три шага:
Доказывающий выбирает случайное число k, такое, что , вычисляет значение и посылает его проверяющему.
Проверяющий отправляет доказывающему случайную равновероятную z-битовую строку в качестве своего запроса, в которой каждый бит с вероятностью 0,5 равен 1 и с вероятностью 0,5 равен 0.
Доказывающий вычисляет свой ответ в виде значения и направляет его проверяющему.
Проверяющий считает ответ положительным, если выполняется соотношение
Легко показать, что вероятность обмана проверяющего в этом протоколе составляет .
4. Двухшаговые протоколы с нулевым разглашением секрета
4.1 Протоколы на основе алгоритмов открытого шифрования
Построение протоколов с нулевым разглашением можно реализовать, используя известные алгоритмы открытого шифрования. Для этого будет использоваться секретный ключ. Для того, кто выполнил процедуру шифрования правильно, восстановленное сообщение будет нести только информацию о том, что тот, кто восстановил зашифрованное сообщение, знает секретный ключ, связанный с открытым ключом. Однако, потенциальный нарушитель может выбрать произвольное значение и объявить его криптограммой, полученной в результате шифрования сообщения M, и попросить владельца открытого ключа выполнить процедуру расшифрования криптограммы. Если последний это сделает и раскроет восстановленное сообщение, то уже потенциально может иметь место утечка информации о секретном ключе. Говорить, что сообщение не несет в себе информацию о секретном ключе нельзя, так как была раскрыта информация. Поэтому, при построении протоколов с нулевым разглашением секрета, нужен некоторый механизм, который позволяет владельцу открытого ключа (доказывающему) убедиться до раскрытия восстановленного сообщения в том, что последнее уже известно (проверяющему) [17].
В качестве такого механизма могут использоваться алгоритмы хэширования (хэш-функции) или заранее специфицированные метки, встраиваемые в исходные сообщения. Первый механизм используется в протоколах с нулевым разглашением, описанных в стандарте . В протоколах такого типа предполагается использование некоторого алгоритма открытого шифрования . Проверяющий может направить доказывающему некоторое случайное сообщение M, предварительно зашифровав его по открытому ключу доказывающего, т.е. направив доказывающему криптограмму , где - открытый ключ доказывающего. Прочитать это сообщение может только тот, кто знает секрет, связанный с открытым ключом P, т.е. только подлинный доказывающий. Получив значение в качестве случайного запроса, доказывающий должен расшифровать криптограмму и направить проверяющему в качестве своего ответа исходное сообщение, т.е. проверяющий получает значение которое уже знает. Поскольку проверяющий не получил никакого нового сообщения, то и утечки информации о личном секретном ключе доказывающего не происходит. При этом проверяющий получает информацию о том, что доказывающий является подлинным.