Пазлы Меркл - Merkles Puzzles

В криптография, Пазлы Меркла это ранняя конструкция для открытый ключ криптосистема, протокол, разработанный Ральф Меркл в 1974 г. и опубликовано в 1978 г. Он позволяет двум сторонам согласовать поделился секретом путем обмена сообщениями, даже если заранее у них нет общих секретов.

Описание

Предполагать Алиса и Боб желаю общаться. Боб может отправить сообщение Алисе следующим образом: сначала он создает большое количество головоломок, каждая из которых имеет умеренную степень сложности - Алиса должна иметь возможность решить головоломку с умеренными вычислительными затратами. Пазлы имеют форму зашифрованный сообщение с неизвестным ключ; ключ должен быть достаточно коротким, чтобы атака грубой силой. Боб отправляет все головоломки (то есть зашифрованные сообщения) Алисе, которая выбирает одну из них случайным образом и решает ее. Расшифрованное решение содержит идентификатор, а также сеансовый ключ, поэтому Алиса может сообщить Бобу, какую головоломку она решила. У обеих сторон теперь есть общий ключ; Алиса, потому что она решила головоломку, и Боб, потому что он отправил головоломку. У любого перехватчика (скажем, Евы) стоит более сложная задача - она ​​не знает, какую загадку решила Алиса. Ее лучшая стратегия - решить все головоломки, но поскольку их так много, это требует больших вычислительных затрат для Евы, чем для Алисы.

Описание высокого уровня

  1. Боб генерирует 2N сообщения, содержащие: «Это сообщение X. Это симметричный ключ Y», где X - это случайно сгенерированный идентификатор, а Y - случайно сгенерированный секретный ключ, предназначенный для симметричного шифрования. Следовательно, и X, и Y уникальны для каждого сообщения. Все сообщения зашифрованы таким образом, что пользователь может с определенными трудностями провести атаку методом грубой силы на каждое сообщение. Боб отправляет Алисе все зашифрованные сообщения.
  2. Алиса получает все зашифрованные сообщения и случайным образом выбирает одно сообщение для грубой силы. После того, как Алиса обнаруживает в этом сообщении идентификатор X и секретный ключ Y, она шифрует свой открытый текст секретным ключом Y и отправляет этот идентификатор (в открытом виде) вместе со своим зашифрованным текстом Бобу.
  3. Боб ищет секретный ключ, связанный с этим идентификатором, поскольку именно он сгенерировал их в первую очередь, и расшифровывает зашифрованный текст Алисы с этим секретным ключом.

Обратите внимание, что подслушивающая Ева может прочитать идентификатор X, отправленный обратно (в виде открытого текста) от Алисы Бобу, но не имеет возможности сопоставить его с секретным ключом Y, который Боб и Алиса теперь используют для своей текущей связи, потому что значение X внутри каждого сообщения генерировалось случайным образом.

Сложность

Предположим, что количество головоломок, отправленных Бобом, равно м, и требуется, чтобы Боб и Алиса п шаги вычисления для решения одной головоломки. Тогда оба могут вывести общий сеансовый ключ за временную сложность О (т + п). Ева же, напротив, должна решить все головоломки, что потребует от нее O (мин) времени. Если м ≈ п, труд для Евы имеет примерно квадратичную сложность по сравнению с Алисой и Бобом. п таким образом, следует выбирать так, чтобы вычисления оставались возможными для Алисы и Боба, в то время как они превосходили возможности Евы.

Квадратичная сложность обычно не считается достаточно безопасной от злоумышленника (или, с другой стороны, для больших m, n, достаточно удобной для участников) для практических реальных криптографических приложений. Однако эта схема отличается тем, что является одним из первых примеров открытый ключ криптографии и послужил источником вдохновения для Диффи-Хеллман протокол обмена ключами, который имеет гораздо более высокую сложность, полагаясь на задача дискретного логарифмирования.

В 2008 Вооз Варак и Мохаммад Махмуди-Гидари показал («Головоломки Меркла оптимальны» ), что эту квадратичную оценку нельзя улучшить.

Рекомендации

  • Меркл Р. К. (апрель 1978 г.). «Безопасная связь по незащищенным каналам». Коммуникации ACM. 21 (4): 294–299. CiteSeerX  10.1.1.364.5157. Дои:10.1145/359460.359473. [pdf ]

внешняя ссылка