Головоломки Меркла

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

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

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

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

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

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

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

В 2008 году Боаз Барак и Мохаммад Махмуди-Гидари показали («Merkle Puzzles Are Optimal»), что эту квадратичную границу улучшить невозможно.

• Merkle, RC (апрель 1978 г.). «Безопасная связь по незащищенным каналам». Communications of the ACM . 21 (4): 294–299. CiteSeerX  10.1.1.364.5157 . doi :10.1145/359460.359473.[pdf-файл]

• Ральф Меркл, Безопасная связь по незащищенным каналам (1974): История идеи и ее публикации, с интервью 1995 года, под редакцией Арнда Вебера
• Ральф Меркл, проектное предложение 1974 года для CS 244 в Калифорнийском университете в Беркли.
• Ральф Меркл, 7 декабря 1975 г., «Безопасная связь по незащищенным каналам»