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