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

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

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

2. Алиса объединяет M и x и хэширует результат:

e = H(M,x)

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

4. Боб вычисляет x' = a^yv^e 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 года.

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

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

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

DIFFIE-HELLMAN

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

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

1. Алиса выбирает случайное большое целое число x и посылает Бобу

X = g^x mod n

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

Y = g^y mod n

3. Алиса вычисляет

k = Y^x mod n

4. Боб вычисляет

k' = X^y mod n

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

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