Пазлы Меркла

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

Описание

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

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

1. Боб генерирует 2 ^Н сообщения, содержащие фразу «Это сообщение 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 году Боаз Барак и Мохаммад Махмуди-Гидари показали ( «Загадки Меркла оптимальны» ), что эту квадратичную оценку невозможно улучшить.

Ссылки

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

Внешние ссылки

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