Протокол Гиллу — Кискатра

Протокол Guillou-Quisquater  — это протокол идентификации с нулевым разглашением, расширение более раннего протокола Фиата — Шамира, разработанный Луи Гиллу (англ. Louis Guillou), Жан-Жак Кискатр (англ. Jean-Jacques Quisquater) в 1988 году.

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

Безопасность протокола основана на сложности извлечения квадратного корня по модулю достаточно большого составного числа по заданному модулю n.

В сравнении с протоколом Фиата-Шамира протокол Guillou-Quisquater имеет меньшее число сообщений, которыми необходимо поменяться сторонам для идентификации. Протокол требует только один раунд обмена сообщениями, имеет более низкие требования к памяти, используемой для хранения секретов пользователей, однако требует большего объёма вычислений.

Кроме того, схему идентификации Guillou-Quisquater можно легко преобразовать в схему подписи.

Свойства

Протокол Guillou-Quisquater — интерактивный протокол, который позволяет доказать, что доказываемое утверждение верно, и доказывающий знает это доказательство, в то же время не предоставляя никакой информации о самом доказательстве данного утверждения. Данный криптографический протокол обладает тремя свойствами:

1. Полнота: если утверждение действительно верно, то доказывающий убедит в этом проверяющего с любой наперед заданной точностью.
2. Корректность: если утверждение неверно, то любой, даже «нечестный», доказывающий не сможет убедить проверяющего.
3. Нулевое разглашение: если утверждение верно, то любой, даже «нечестный», проверяющий не узнает ничего кроме самого факта, что утверждение верно.

Общая структура раунда

Протокол Guillou-Quisquater требует только один раунд обмена сообщениями и состоит из трёх этапов. Схематично их можно изобразить следующим образом:

• $A\Rightarrow B$ : доказательство (witness)
• $A\Leftarrow B$ : вызов (challenge)
• $A\Rightarrow B$ : ответ (response)

Сначала A выбирает из заранее определённого непустого множества некоторый элемент, который становится её секретом — закрытым ключом. По этому элементу вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определённым правилам вычисляет доказательство и затем отсылает его B. После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов). В зависимости от вопроса, А посылает B ответ. Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом.

Схема идентификации

Сторона A отправляет стороне В свои атрибуты $J$. Стороне A необходимо убедить сторону В, что это именно её атрибуты. Для этого сторона A доказывает своё знание секрета $x$ стороне B, не раскрывая при этом ни одного бита самого секрета $x$. Для этого сторонам потребуется всего 1 раунд.

Алгоритм создания открытого и закрытого ключей

1. Центр доверия T выбирает два различных случайных простых числа $p$ и $q$, после чего вычисляет их произведение $n=p\cdot q$.
2. T выбирает целое число $e$ ($1<e<\varphi (n)$), взаимно простое со значением функции $\varphi (n)$. Функция $\varphi (n)$ является функцией Эйлера.
3. T вычисляет $s=e^{-1}\mod \varphi (n)$ и секрет $x=J^{-s}\mod n$.
4. T вычисляет $y=x^{e}\mod n$.
5. Тройка $\left\{n,e,y\right\}$ публикуется в качестве открытого ключа.
6. $x$ играет роль закрытого ключа, и передается стороне A.

Обмен сообщениями

1. А выбирает случайное целое $r$, находящееся в диапазоне от $1$ до $n-1$. А вычисляет $a=r^{e}\mod n$ и отправляет его В.
2. В выбирает случайное целое $c$, находящееся в диапазоне от $0$ до $e-1$. В посылает $c$ стороне А.
3. А вычисляет $z=rx^{c}\mod n$ и посылает его В.
4. B проверяет: если $z^{e}=ay^{c}\mod n$, то подлинность доказана.

Действительно $z^{e}=(rx^{c})^{e}=r^{e}x^{ec}=r^{e}(x^{e})^{c}=ay^{c}\mod n$.

Схема подписи

Эту схему идентификации можно превратить в схему подписи. Открытый и закрытый ключи не меняются.

Подпись сообщения

Пусть А хочет подписать сообщение $M$.

1. А выбирает случайное целое $r$, находящееся в диапазоне от $1$ до $n-1$. А вычисляет $a=r^{e}\mod n$.
2. А вычисляет $d=H(M,a)$, где $M$ — подписываемое сообщение, а $H(x)$ — однонаправленная хеш-функция. Значение $d$, полученное с помощью хеш-функции, должно быть в диапазоне от $0$ до $e-1$. Если выход хеш-функции выходит за этот диапазон, он должен быть приведен по модулю $e$.
3. А вычисляет $z=rx^{d}\mod n$. Подпись состоит из сообщения $M$, двух вычисленных значений $d$ and $z$, и её атрибутов $J$. А посылает подпись B.

Проверка подписи

Пусть В хочет проверить подпись.

1. B вычисляет $a'=z^{e}J^{d}\mod n$. Затем он вычисляет $d'=H(M,a')$. Если $d=d'$, то А знает B, и её подпись действительна.

Схема множественной подписи

Схема подписи может быть переделана на случай, когда несколько человек хотят подписать один и тот же документ. Пусть А и B подписывают документ, а K проверяет подписи, но в процесс подписания может быть вовлечено произвольное количество людей. Как и раньше, А и B обладают уникальными значениями $J$ и $x$: ($J_{A}$,$x_{A}$) и ($J_{B}$,$x_{B}$). Значения $n$ и $e$ являются общими для всей системы.

Подпись сообщения

Пусть А и B хотят подписать сообщение $M$.

1. А выбирает случайное целое $r_{A}$, находящееся в диапазоне от $1$ до $n-1$. Она вычисляет $a_{A}=r_{A}^{e}\mod n$ и посылает B.
2. B выбирает случайное целое $r_{B}$, находящееся в диапазоне от $1$ до $n-1$. Она вычисляет $a_{B}=r_{B}^{e}\mod n$ и посылает А.
3. А и B, каждый вычисляет $a=(a_{A}\cdot a_{B})\mod n$.
4. А и B, каждый вычисляет $d=H(M,a)$, где $M$ — подписываемое сообщение, а $H(x)$ — однонаправленная хеш-функция. Значение $d$, полученное с помощью хеш-функции, должно быть в диапазоне от $0$ до $e-1$. Если выход хеш-функции выходит за этот диапазон, он должен быть приведен по модулю $e$.
5. А вычисляет $z_{A}=r_{A}x_{A}^{d}\mod n$ и посылает B.
6. B вычисляет $z_{B}=r_{B}x_{B}^{d}\mod n$ и посылает А.
7. А и B, каждый вычисляет $z=z_{A}z_{B}\mod n$. Подпись состоит из сообщения $M$, двух вычисленных значений $d$ and $z$, и атрибутов обоих подписывающих: $J_{A}$ и $J_{B}$.

Проверка подписи

Пусть К хочет проверить подпись.

1. K вычисляет $J=J_{A}J_{B}\mod n$.
2. К вычисляет $a'=z^{e}J^{d}\mod n$. Затем она вычисляет $d'=H(M,a')$. Если $d=d'$, то множественная подпись действительна.

Этот протокол может быть расширен на любое количество людей. Для этого подписывающие сообщение люди должны перемножить свои значения $a_{i}$ на этапе (3), и свои значения $z_{i}$ на этапе (7). Чтобы проверить множественную подпись, нужно на этапе (1) перемножить значения $J_{i}$ подписывающих. Либо все подписи правильны, либо существует по крайней мере одна неправильная подпись.

Литература

• Feige, Uriel; Fiat, Amos; Shamir, Adi. Zero-knowledge proofs of identity (англ.) // Journal of Cryptology : journal. — 1988. — Vol. 1, no. 2. — P. 77—94. — doi:10.1007/BF02351717. Архивировано 17 декабря 2012 года.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 с. — ISBN 0-8493-8523-7.
• Louis Guillou, Jean-Jacques Quisquater. A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory (англ.). — 1988.
• Саломаа А. Криптография с открытым ключом — М.: Мир, 1995. — 318 с. — ISBN 978-5-03-001991-8
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.