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

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

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

DIFFIE-HELLMAN

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

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

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

X= g^xmod n

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

Y= g^ymod n

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

k= Y^xmod n

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

k' = X^y mod n

И k, и k'равны g^xymod 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= g^xmod n

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

Y= g^ymod n

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

Z= g^zmod n

(4) Алиса посылает Бобу

Z'=Z^xmod n

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

X'=X^ymod n

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

Y'=Y^zmod n

(7) Алиса вычисляет

k= Y'^xmod n

(8) Боб вычисляет

k = Z'^y mod n

(9) Кэрол вычисляет

k = X'^z mod n

Секретный ключ k равен g^xyzmod n, и никто из подслушивающих каналы связи не сможет вычислить это значение. Протокол можно легко расширить для четверых и более участников, просто добавляются участники и этапы вычислений.