Обратите внимание, что у чисел 14, 15, 21, 25 и 30 нет обратных значений mod 35, так как они не взаимно просты с 35. Это имеет смысл, так как должно быть (5 - 1) * (7 - 1)/4 квадратичных остатков mod 35, взаимно простых с 35: НОД, 35) = 1 (см. раздел 11.3).

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

(1)Пегги выбирает случайное r=16, вычисляет 162 mod 35 = 11 и посылает его Виктору.

(2)Виктор посылает Пегги строку случайных битов: {1, 1, 0, 1}

(3)Пегги вычисляет 16*(31*41*90*81) mod 35 = 31 и посылает его Виктору.

(4)Виктор проверяет, что 312*(41*111*160*291) mod 35 =11.

Пегги и Виктор повторяют этот протокол t раз, каждый раз с новым случайным r, пока Виктор будет убежден.

Небольшие числа, подобные использованным в примере, не обеспечивают реальной безопасности . Но когда длина n равна 512 и более битам, Виктор не сможет узнать о закрытом ключе Пегги ничего кроме того факта, что Пегги действительно знает его.

Улучшения

В протокол можно встроить идентификационные данные. Пусть I - это двоичная строка, представляющая идентификатор Пегги: имя, адрес, номер социального страхования, размер головного убора, любимый сорт прохладительного напитка и другая личная информация. Используем однонаправленную хэш-функцию H(x) для вычислениягде j - небольшое число, добавленное к I. Найдем набор j, для которых- это квадратич-

ный остаток по модулю n. Эти значениястановятся v1, v2, . . . vk (j не обязаны быть квадратичными остат-

ками). Теперь открытым ключом Пегги служит I и перечень j. Пегги посылает I и перечень j Виктору перед шагом (1) протокола (или Виктор загружает эти значения с какой-то открытой доски объявлений ), И Виктор генерирует vb v2, . . . vk из

Теперь, после того, как Виктор успешно завершит протокол с Пегги, он будет убежден, что Трент, которому известно разложение модуля на множители, сертифицировал связь между I и Пегги, выдав ей квадратные корни из v,-, полученные из I. (См. раздел 5.2.) Фейге, Фиат и Шамир добавили следующие замечания [544, 545]:

Для неидеальных хэш-функций можно посоветовать рандомизировать I, добавляя к нему длинную случайную строку R. Эта строка выбирается арбитром и открывается Виктору вместе с I.

В типичных реализациях k должно быть от 1 до 18. Большие значения k могут уменьшить время и трудности связи, уменьшая количество этапов .

Длина n должна быть не меньше 512 битов. (Конечно, с тех пор разложение на множители заметно продвинулось.)

Если каждый пользователь выберет свое собственное n и опубликует его в файле открытых ключей, то можно обойтись и без арбитра. Однако такой RSA-подобный вариант делает схему заметно менее удобной.

Схема подписи Fiat-Shamir

Превращение этой схемы идентификации в схему подписи - это, по сути, вопрос превращения Виктора в хэш-функциию. Главным преимуществом схемы цифровой подписи Fiat-Shamir по сравнению с RSA является ее скорость: для Fiat-Shamir нужно всего лишь от 1 до 4 процентов модульных умножений, используемых в RSA. В этом протоколе снова вернемся к Алисе и Бобу.

Смысл переменных - такой же, как и в схеме идентификации . Выбирается n - произведение двух больших простых чисел. Генерируется открытый ключ, v1, v2, . . . vk, и закрытый ключ, s1, s2, . . . sk, где s; = sqrt (v,- ) (mod

(1)Алиса выбирает t случайных целых чисел в диапазоне от 1 до n - r1, r2, . . rt - и вычисляет x1, x2, . . . xt, такие что x, = r,2 mod n.

(2)Алиса хэширует объединение сообщения и строки xb создавая битовый поток: H(m, x1, x2, . . . xt). Она использует первые k*t битов этой строки в качестве значений bj, где , пробегает от1 до t, а j от 1 до k.

(3)Алиса вычисляет y1, y2, . . . yt,, где y; = r *(s1b1 * s2b2 *K*skb,k/) mod n

(Для каждого , она перемножает вместе значения sb в зависимости от случайных значений bj. Если bj=1, то s, участвует в вычислениях, если b,j=0, то нет.)

(4)Алиса посылает Бобу m, все биты bj, и все значения y;. У Боба уже есть открытый ключ Алисы: v1, v2, . . . vk-

(5)Боб вычисляет z1, z2, . . . zt, где zj = y2*( v1b1 * v2b2 * . *vkbjk) mod n

(И снова Боб выполняет умножение в зависимости от значений by.) Также обратите внимание, что zj должно быть равно x,.

(6)Боб проверяет, что первые k*t битов z1, z2, . . . zt) - это значения by-, которые прислала ему Алиса.

Как и в схеме идентификации безопасность схемы подписи пропорциональна l/2kt. Она также зависит от сложности разложения n на множители. Фиат и Шамир показали, что подделка подписи облегчается, если сложность разложения n на множители заметно меньше 2kt. Кроме того, из-за вскрытия методом дня рождения (см. раздел 18.1), они рекомендуют повысить k*t от 20 по крайней мере до 72, предлагая k = 9 и t = 8.

Улучшенная схема подписи Fiat-Shamir

Сильвия Микали (Silvia Micali) и Ади Шамир улучшили протокол Fiat-Shamir [1088]. Они выбирали v1, v2, . . . vk так, чтобы они были первыми k простыми числами. То есть

v1= 1, v2= 3, v3= 5, и т.д.

Это открытый ключ. Закрытым ключом, s1, s2, . . . sk, служат случайные квадратные корни, определяемые

s, = sqrt (v,-1) (mod n)

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

Другие улучшения

На основе алгоритма Fiat-Shamir существует и N-сторонняя схема идентификации [264]. Два других улучшения схемы Fiat-Shamir в [1218]. Еще один вариант - в [1368].

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

Этот протокол является вариантом схемы идентификации Feige-Fiat-Shamir, его безопасность основана на трудности разложения на множители [1198, 1199]. Эти же авторы разработали схему с несколькими подписями (см. раздел 23.1), с помощью которой различные люди могут последовательно подписывать [1200]. Эта схема была предложена для реализации на интеллектуальных карточках [850].

Патенты

Fiat-Shamir запатентован [1427]. При желании получить лицензию на алгоритм свяжитесь с Yeda Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.

21.2 GUILLOU-QUISQUATER

Feige-Fiat-Shamir был первым практическим протоколом идентификации . Он минимизировал вычисления, увеличивая число итераций и аккредитаций на итерацию . Для ряда реализаций, например, для интеллектуал ь-ных карточек, это не слишком подходит. Обмены с внешним миром требуют времени, а хранение данных для каждой аккредитации может быстро исчерпать ограниченные возможности карточки .

Луи Гиллу (Louis Guillou) и Жан-Жак Кискатр (Jean-Jacques Quisquater) разработали алгоритм идентификации с нулевым знанием, который больше подходит для подобных приложений [670, 1280]. Обмены между Пегги и Виктором, а также параллельные аккредитации в каждом обмене сведены к абсолютному минимуму : для каждого доказательства существует только один обмен, в котором - только одна аккредитация . Для достижения того же уровня безопасности при использовании схемы Guillou-Quisquater потребуется выполнить в три раза больше вычислений, чем при Feige-Fiat-Shamir. И, как и Feige-Fiat-Shamir, этот алгоритм идентификации можно превратить в алгоритм цифровой подписи .

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

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

ключом служит B, рассчитываемое так, чтобы JBv = 1 (mod n).

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

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

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

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

(4)Виктор вычисляет T = DvJ mod n. Если T = T (mod n), то подлинность Пегги доказана. Математика не слишком сложна:

T = DvJd = (rBd)vJd = rvBdvJd = rv(BvJ)d = rv = r =T (mod n), так как JBv = 1 (mod n) Схема подписи Guillou-Quisquater

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

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

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

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

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

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

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

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

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

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

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

(5)Алиса вычисляет DA = rABAd mod n и посылает DA Бобу.

(6)Боб вычисляет DB = rBBBd mod n и посылает DB Алисе.

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

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

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

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