"Шарады" Меркля

Оригинальный протокол обмена ключами был предложен американским криптологом Р. Мерклем (R. Merkle) в 1974 г. Данный протокол основывается на так называемых “шарадах”, которые требуется решить для получения ключа. Это гораздо легче сделать отправителю и получателю шифрованных сообщений, чем криптоаналитику, перехватывающему их. В результате Антон может послать шифрованное сообщение Борису, предварительно не передавая ему секретного ключа:

1. Борис генерирует 2²⁰ (около 1 млн) сообщений вида: “Это шарада под

номером х. Это секретный ключ под номером у”, где х — случайное число, у — случайный секретный ключ. Пара х, у является уникальной для каждого сообщения. Затем Борис шифрует все эти сообщения при помощи какого-либо симметричного алгоритма на различных 20-битных ключах и отсылает Антону.

2. Антон случайным образом выбирает одно из шифрованных сообщений,

присланных Борисом, и методом тотального перебора получает открытый текст этого сообщения.

3. Антон шифрует свое собственное секретное сообщение при помощи

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

4. Борис, зная соответствие между х и у, расшифровывает сообщение,

пришедшее ему от Антона.

Конечно же, Петр может вскрыть ключ, который был использован Антоном для зашифрования секретного сообщения, однако для этого Петру придется выполнить значительно больший объем вычислений, чем Антону и Борису. Петр должен будет прочесть все 2²⁰ шифрованных сообщений, отправленных Борисом, чтобы найти у, соответствующее значению х, выбранному Антоном. На решение этих “шарад” Петр потратит примерно квадрат времени, которое потребуется Антону и Борису, чтобы их составить. И хотя такое отличие в трудоемкости по криптографическим меркам довольно невелико, в некоторых случаях этого может оказаться достаточно. Например, если Антон и Борис смогут опробовать по 10 тыс. ключей в секунду, им понадобится немногим более 1 минуты, чтобы ключ шифрования у оказался в руках Антона. В то же время у Петра, обладающего примерно такой же вычислительной мощью для опробования ключей, как Антон и Борис, на вскрытие правильного ключа уйдет больше года.