21.3 SCHNORR

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

Для генерации конкретной пары ключей выбирается случайное число, меньшее 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.

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

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

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

(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 Преобразование схем идентификации в схемы подписи

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

ется в алгоритм подписи. В принципе, такую манипуляцию можно проделать с любой схемой идентификации

Глава 22 Алгоритмы обмена ключами

22.1 DIFFIE-HELLMAN

Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году [496]. Его безопасность опирается на трудность вычисления дискретных логарифмов в конечном поле (в сравнении с легк остью возведения в степень в том же самом поле . Diffie-Hellman может быть использован для распределения ключей - Алиса и Боб могут воспользоваться этим алгоритмом для генерации секретного ключа - но его нельзя использовать для шифрования и дешифрирования сообщений .

Математика несложна. Сначала Алиса и Боб вместе выбирают большие простые числа n и g так, чтобы g было примитивом mod n. Эти два целых числа хранить в секрете необязательно, Алиса и Боб могут договориться об из использовании по несекретному каналу . Эти числа даже могут совместно использоваться группой пол ь-зователей. Без разницы. Затем выполняется следующий протокол:

(1)Алиса выбирает случайное большое целое число x и посылает Бобу X = gx mod n

(2)Боб выбирает случайное большое целое число y и посылает Алисе

Y= gy mod n

(3)Алиса вычисляет k = Yx mod n

(4)Боб вычисляет k = Xy mod n

И k, и k равны gxy mod n. Никто из подслушивающих этот канал не сможет вычислить это значение, им и з-вестно только n, g, X и Y. Пока они не смогут вычислить дискретный логарифм и раскрыть x или y, они не смогут решить проблему. Поэтому, k - это секретный ключ, который Алиса и Боб вычисляют независимо .

Выбор g и n может заметно влиять на безопасность системы. Число (n-1)/2 также должно быть простым [1253]. И, самое главное, n должно быть большим: безопасность системы основана на сложности разложения на множители чисел того же размера, что и n. Можно выбирать любое g, которое является примитивом mod n; нет причин, по которым нельзя было бы выбрать наименьшее возможное g - обычно одноразрядное число. (К тому же, на самом деле, g не должно даже быть примитивом, оно только должно генерировать достаточно большую подгруппу мультипликативной группы mod n.)

Diffie-Hellman с тремя и более участниками *

Протокол обмена ключами Diffie-Hellman легко можно расширить на случай с тремя и более участниками . В приводимом примере Алиса, Боб и Кэрол вместе генерируют секретный ключ.

(1)Алиса выбирает случайное большое целое число x и вычисляет X = gx mod n

(2)Боб выбирает случайное большое целое число y и посылает Кэрол

Y= gy mod n

(3)Кэрол выбирает случайное большое целое число z и посылает Алисе Z = gz mod n

(4)Алиса посылает Бобу Z=Zx mod n

(5)Боб посылает Кэрол * X=X mod n

(6)Кэрол посылает Алисе Y=Ymod n

(7)Алиса вычисляет k = Y* mod n