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

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

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

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

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

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

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

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

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