В криптографии головоломки Меркла представляют собой раннюю конструкцию криптосистемы с открытым ключом, протокола, разработанного Ральфом Мерклем в 1974 году и опубликованного в 1978 году. Он позволяет двум сторонам договориться об общем секрете путем обмена сообщениями, даже если у них нет секретов в общий заранее.
Предположим , Алиса и Боб хотят общаться. Боб может отправить сообщение Алисе следующим образом: сначала он создает большое количество головоломок, каждая из которых имеет умеренную сложность — Алиса должна иметь возможность решить головоломку с умеренными вычислительными затратами. Головоломки представлены в виде зашифрованного сообщения с неизвестным ключом ; ключ должен быть достаточно коротким, чтобы можно было провести атаку грубой силы. Боб отправляет все головоломки (то есть зашифрованные сообщения) Алисе, которая случайным образом выбирает одну из них и решает ее. Расшифрованное решение содержит идентификатор, а также сеансовый ключ, поэтому Алиса может сообщить Бобу, какую головоломку она решила. Обе стороны теперь имеют общий ключ; Алиса, потому что она решила головоломку, и Боб, потому что он отправил головоломку. У любого подслушивателя (скажем, у Евы) задача посложнее — она не знает, какую загадку решила Алиса. Ее лучшая стратегия — решить все головоломки, но, поскольку их так много, для Евы это требует больших вычислительных ресурсов, чем для Алисы.
Обратите внимание, что подслушиватель Ева может прочитать идентификатор X, отправленный обратно (в открытом виде) от Алисы к Бобу, но не имеет возможности сопоставить его с секретным ключом Y, который Боб и Алиса теперь используют для своего текущего общения, потому что значение X в каждом сообщении генерировалось случайным образом.
Параметры игры-головоломки могут быть выбраны так, чтобы подслушивателю было значительно труднее взломать код, чем общаться сторонам, но головоломки Меркла не обеспечивают огромных качественных различий в сложности, которые требуются для (и определяют) безопасность. в современной криптографии.
Предположим, что количество головоломок, отправленных Бобом, равно m , и Бобу и Алисе требуется n шагов вычислений, чтобы решить одну головоломку. Тогда оба могут вывести общий сеансовый ключ за временную сложность O ( m+n ). Ева, напротив, должна решить все головоломки, что отнимет у нее O( mn ) времени. Если m ≈ n , трудозатраты Евы имеют примерно квадратичную сложность по сравнению с Алисой и Бобом, т. е. ее время вычислений порядка квадрата их. Таким образом, n должно быть выбрано достаточно большим, чтобы Алиса и Боб все еще могли выполнять вычисления, в то время как они превышали возможности Евы.
Квадратичная сложность обычно не считается достаточно надежной против злоумышленника (или, с другой стороны, для больших m, n, достаточно удобной для участников) для практических реальных криптографических приложений. Однако эта схема отличается тем, что является одним из первых примеров криптографии с открытым ключом и послужила источником вдохновения для протокола обмена ключами Диффи-Хеллмана , который имеет гораздо более высокую сложность, опираясь на проблему дискретного логарифма .