ПРОВЕРКА ПОДЛИННОСТИ ПРИ ПОМОЩИ СХЕМЫ ФЕЙГА-ФИАТА-ШАМИРА

Введение

В реальном мире зачастую необходимо убедиться, что одна из сторон обладает информацией, при этом не раскрывая её содержания. Для решения поставленной задачи в данной работе мы рассмотрим протокол идентификации стороны при помощи схемы Уриэля Фейга, Амоса Фиата и Ади Шамира, который на данный момент является одним из лучших доказательств с нулевым разглашением, а также продемонстрируем работу алгоритма на примере.

Основные определения

Введем некоторые определения, которые будут использованы в работе. 

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

2. Простое число – натуральное (целое положительное) число ℕ, которое имеет ровно два различных натуральных делителя – единицу и самого себя.

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

Генерация ключей

1. На начальном этапе доверенный арбитр выбирает случайны модуль n, являющийся произведением двух больших простых чисел , где p,q – простые числа. Число n является общедоступным, а числа p и q – секретными.
2. Чтобы сгенерировать отрытый и закрытый ключ сторона А выбирает k случайных целых чисел , таких что  и каждое  - квадратичный остаток по модулю n, то есть необходимо чтобы имело решение, и существовало . Последовательность будет являться открытым ключом.
3. Вычисляется последовательность , в которой Данная последовательность будет являться закрытым ключом.

Работа протокола

1. Сторона А: Выбирает случайное целое число r,  и вычисляет и отправляет x стороне Б
2. Сторона Б: Посылает стороне А набор k случайных битов:
3. Сторона Б: Вычисляет . Таким образом, если случайный бит , то  войдет в произведение, иначе и  не войдет в произведение.
4. Сторона Б: Проверяет, что

Протокол повторяется t раундов до тех пор пока сторона Б не убедится в том, что сторона А действительно знает последовательность . Вероятность успешной атаки на протокол путем подбора значений  из последовательности  составляет . Рекомендуется использовать параметры k = 5 и t =4, таким образом вероятность успешной атаки на протокол равна .

Рисунок 1. Схема работы протокола

Пример работы протокола

Генерация ключей:

1. Арбитр выбирал два случайных простых числа p = 5, q = 7 и опубликовал  . Параметры безопасности k=4 и t=1. Возможными квадратичными остатками будут являться числа:

Таблица 1.

Вычисление квадратичных остатков

2. Вычислим обратные значения по модулю 35 и их квадратичные корни. Числа, которые не взаимно простые с 35, не будут иметь обратных значений (mod 35)

Таблица 2.

Вычисление обратных значений к квадратичным остаткам и их квадратичных корней.

Работа протокола:

Сторона А получает открытый ключ, состоящий из k=4 значений: {4, 11, 16, 29}. Ему будет соответствовать закрытый ключ {3, 4, 9,8}.

1.Сторона А выбирает случайное число r=16 и посылает стороне Б число  

2.Сторона Б посылает набор случайных битов {1, 1, 0, 1} стороне А.

3.Сторона А вычисляет значение и отправляет его стороне Б.

4.Сторона Б производит проверку

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

Заключение

В данной работе был рассмотрен принцип протокола идентификации с нулевым разглашением Фейга-Фиата-Шамира, а также разобраны основные этапы работы протокола на конкретном примере.

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

1. Додонова Н.Л. Конспект лекций по дисциплине алгебраические структуры и теория чисел. Самара, 2016