Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Шнайер - Прикладная криптография.doc
Скачиваний:
13
Добавлен:
01.05.2025
Размер:
10 Мб
Скачать
☆

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

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

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

  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'). Если dd', то множественная подпись действительна.

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

SCHNORR

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

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

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

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

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

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

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

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

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