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

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

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

Как и в схеме идентификации безопасность схемы подписи пропорциональна 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, служат случайные квадратные корни, определяемые

si = 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, рассчитываемое так, чтобы /Sv = 1 (mod n).

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

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

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

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

(4) Виктор вычисляет T" = DvJd 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" = DvJd mod n. Затем он вычисляет d = H(M,T"). Если d = d, то Алиса знает B, и ее подпись действительна.

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

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

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

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

(3) Алиса и Боб, каждый вычисляет T = (T4*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) перемножить значения подписывающих (8). Либо все подписи правильны, либо существует по крайней мере одна неправильная подпись .

21.3 SCHNORR

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

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

Протокол проверки подлинности

(1) Пегги выбирает случайное число r, меньшее q, и вычисляет x = ar mod Эти вычисления являются предварительными и могут быть выполнены задолго до появления Виктора .

(2) Пегги посылает x Виктору.

(3) Виктор пос1лает Пегги случайное число e, из диапазона от 0 до 2t-1. (Что такое t, я объясню чуть позже.)

(4) Пегги вычисляет y = (r + se) mod q и пос1лает y to Виктору.

(5) Виктор проверяет, что x = ayve mod p.

Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна 2t. Шнорр советует использовать p около 512 битов, q - около 140 битов и t - 72.

Протокол цифровой подписи

Алгоритм Schnorr также можно использовать и в качестве протокола цифровой подписи сообщения M. Пара ключей используется та же самая, но добавляется однонаправленная хэш-функция

(1) Алиса выбирает случайное число r, меньшее q, и вычисляет x = ar mod Это стадия предварительных вычислений.

(2) Алиса объединяет M и x и хэширует результат: e = H(M,x)

(3) Алиса вычисляет y = (r + se) mod q. Подписью являются значения e и y, она посылает их Бобу.

(4) Боб вычисляет x = ayve mod p. Затем он проверяет, что хэш-значение для объединения M и x равно e. e = H(M,x)

Если это так, то он считает подпись верной. В своей работе Шнорр приводит следующие новые свойства своего алгоритма :

Большая часть вычислений, нужных для генерации подписи и независящих от подписываемого сообщения, может быть выполнена на стадии предварительных вгчислений. Следовательно, эти вычисления могут быть выполнены во время простоя и не влияют на скорость подписания. Вскрытие, направленное против стадии предварительных вычислений, рассматр и-вается в [475], я не думаю, что оно имеет практическую ценность.

При одинаковом уровне безопасности длина подписей для Schnorr короче, чем для RSA. Например, при 140-битовом q длина подписей равна всего лишь 212 битам, меньше половины длины подписей RSA. Подписи Schnorr также намного короче подписей EIGamal.

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

Модификация, выполненная Эрни Брикеллом (Ernie Brickell) и Кевином МакКерли (Kevin McCurley), повысила безопасность этого алгоритма [265].

Патенты

Schnorr запатентован в Соединенных Штатах [1398] и многих других странах. В 1993 году PKP приобрело обще мировые права на этот патент(см. раздел 25.5). Срок действия патента США истекает 19 февраля 2008

года.

21.4 Преобразование схем идентификации в схемы подписи

Вот стандартный метод преобразования схемы идентификации в схему подписи : Виктор заменяется однонаправленной хэш-функцией. Перед подписанием сообщение не хэшируется, вместо этого хэширование встраив а-