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

Ральф Меркл (Ralph Merkle) изобрел первую схему криптографии с открытыми ключами. В 1974 году он записался на курс по компьютерной безопасности в Калифорнийском университете, Беркли, который вел Ланс Хоффман (Lance Hoffman). Темой его курсовой работы, поданной раньше срока, была "Безопасная передача данных по небезопасным каналам". Хоффман не понял предложения Меркла, и в конце концов Меркл прекратил занятия. Он продолжал работать над проблемой, несмотря на продолжающееся непонимание его результатов.

Техника Меркла основывалась на головоломках ("puzzle"), которые отправителю и получателю решить легче чем злоумышленнику. Вот как Алиса может послать шифрованное сообщение Бобу, не обмениваясь с ним ключом до того.

(1)Боб создает 2²⁰ (другими словами, больше миллиона) сообщений типа: "Это головоломка номер х. Это секретный ключ номер у", где х - случайное число, а у - случайный секретный ключ. И х, и у отличаются в каждом сообщении. Используя симметричный алгоритм, он шифрует каждое сообщение своим 20 битным ключом и все их отправляет Алисе.

(2)Алиса выбирает одно сообщение и приступает к вскрытию грубой силой,пытаясь получить открытый текст. Эта работа является объемной, но не невозможной.

(3)Алиса шифрует свое секретное сообщение при помощи некоторого симметричного алгоритма полученным ею ключом и посылает это сообщение Бобу вместе с х.

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

Ева может взломать эту систему, но ей придется выполнить гораздо больше работы, чем Алисе и Бобу. Для раскрытия сообщения на этапе (3) она должна будет вскрыть грубой силой каждое из 2²⁰ сообщений, отправленных Бобом на этапе (1). Сложность этого вскрытия составит 2⁴⁰. Значения х также не помогут Еве, ведь они на этапе (1) присвоены случайным образом. В общем случае, вычислительные затраты Евы будут равны возведенным в квадрат вычислительным затратам Алисы.

Это выигрыш (n по отношению к n²) невелик по криптографическим стандартам, но при определенных условиях может быть достаточен. Если Алиса и Боб могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Боба к Алисе по линии связи 1.544 Мбит/с. Если вычислительные возможности Евы сравнимы с приведенными, ей потребуется около года для взлома системы. Другие алгоритмы еще более устойчивы к вскрытию.