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

Пегги - это интеллектуальная карточка, которая собирается доказать свою подлинность Виктору. Идентификация Пегги проводится по ряду атрибутов, представляющих собой строку данных содержащих название карточки, период действия, номер банковского счета и другие, подтверждаемые ее применимость, данные. Эта битовая строка называется J. (В реальности строка атрибутов может быть очень длинной, и в качестве J используется ее хэш-значение. Это усложнение никак не влияет на протокол.) Эта строка аналогична открытому ключу. Другой открытой информацией, общей для всех "Пегги", которые могут использовать это приложение, является показатель степени vи модуль n, где n- это произведение двух хранящихся в секрете простых чисел. Закрытым ключом служит B, рассчитываемое так, чтобы JB^v º 1 (mod n).

Пегги посылает Виктору свои атрибуты J. Теперь она хочет доказать Виктору, что это именно ее атрибуты. Для этого она должна убедить Виктора, что ей известно B. Вот этот протокол:

(1) Пегги выбирает случайное целое r, находящееся в диапазоне от 1 до n-1. Она вычисляет T= r^vmod nи отправляет его Виктору.

(2) Виктор выбирает случайное целое d, находящееся в диапазоне от 0 до v-1. Он посылает dПегги.

(3) Пегги вычисляет D= rB^dmod n и посылает его Виктору.

(4) Виктор вычисляет T' = D^vJ^d mod n. Если T º T' (mod n), то подлинность Пегги доказана.

Математика не слишком сложна:

T' = D^vJ^d = (rB^d)^vJ^d = r^vB^dvJ^d = r^v(B^vJ)^d = r^v= r' ºT(mod n), так как JB^v º 1 (mod n)

Схема подписи Guillou-Quisquater

Эту схему идентификации можно превратить в схему подписи, также пригодную для реализации в интеллектуальных карточках [671, 672]. Открытый и закрытый ключи не меняются. Вот как выглядит протокол:

(1) Алиса выбирает случайное целое r, находящееся в диапазоне от 1 до n-1. Она вычисляет T= r^vmod n.

(2) Алиса вычисляет d = H(M,T), где M - подписываемое сообщение, а H(x) - однонаправленная хэш-функция. Значение d, полученное с помощью хэш-функции, должно быть в диапазоне от 0 до v-1 [1280]. Если выход хэш-функции выходит за этот диапазон, он должен быть приведен по модулю v.

(3) Алиса вычисляет D= rB^dmod n. Подпись состоит из сообщения M, двух вычисленных значений, d and D, и ее атрибутов J. Она посылает подпись Бобу.

(4) Боб вычисляет T' = D^vJ^d mod n. Затем он вычисляет d' = H(M,T'). Если d º d', то Алиса знает B, и ее подпись действительна.

Несколько подписей

Что если несколько человек захотят подписать один и тот же документ? Проще всего, чтобы они подписали его порознь, но рассматриваемая схема подписи делает это лучше. Пусть Алиса и Боб подписывают документ, а Кэрол проверяет подписи, но в процесс подписания может быть вовлечено произвольное количество людей. Как и раньше, Алиса и Боб обладают уникальными значениями J и B: (J_A,B_A)и (J_B,B_B). Значения nи vявляются общими для всей системы.

(1) Алиса выбирает случайное целое r_А, находящееся в диапазоне от 1 до n-1. Она вычисляет T_А= r_А^vmod n и посылает T_АБобу.

(2) Боб выбирает случайное целое r_B, находящееся в диапазоне от 1 до n-1. Он вычисляет T_B= r_B^vmod n и посылает T_BАлисе.

(3) Алиса и Боб, каждый вычисляет T = (T_А*T_B) mod n.

(4) Алиса и Боб, каждый вычисляет d= H(M,T), где M - подписываемое сообщение, а H(x) - однонаправленная хэш-функция. Значение d, полученное с помощью хэш-функции, должно быть в диапазоне от 0 до v-1 [1280]. Если выход хэш-функции выходит за этот диапазон, он должен быть приведен по модулю v.

(5) Алиса вычисляет D_A= r_AB_A^dmod n и посылает D_AБобу.

(6) Боб вычисляет D_B= r_BB_B^dmod n и посылает D_BАлисе.

(7) Алиса и Боб, каждый вычисляет D= D_AD_Bmod n. Подпись состоит из сообщения M, двух вычисленных значений, d and D, и атрибутов обоих подписывающих: J_Aи J_B.

(8) Кэрол вычисляет J= J_AJ_Bmod n.

(9) Кэрол вычисляет T' = D^vJ^d mod n. Затем она вычисляет d' = H(M,T'). Если d º d', то множественная подпись действительна.

Этот протокол может быть расширен на любое количество людей. Для этого подписывающие сообщение люди должны перемножить свои значения T_iна этапе (3), и свои значения D_iна этапе (7). Чтобы проверить множественную подпись, нужно на этапе (8) перемножить значения J_iподписывающих (8). Либо все подписи правильны, либо существует по крайней мере одна неправильная подпись.

SCHNORR

Безопасность схемы проверки подлинности и подписи Клауса Шнорра [1396,1397] опирается на трудность вычисления дискретных логарифмов. Для генерации пары ключей сначала выбираются два простых числа, pи q так, чтобы qбыло сомножителем p-1. Затем выбирается a, не равное 1, такое что a^qº 1 (mod p). Все эти числа могут быть свободно опубликованы и использоваться группой пользователей.

Для генерации конкретной пары ключей выбирается случайное число, меньшее q. Оно служит закрытым ключом, s. Затем вычисляется открытый ключ v= a^-s mod p.