Книга шифров .Тайная история шифров и их расшифровки

Если вернуться к аналогии с замками, то шифрование с открытым ключом можно представить себе следующим образом. Любой способен запереть замок, просто защелкнув его, чтобы он закрылся, но отпереть его может только тот, у кого есть ключ. Запереть замок (зашифровывание) легко, почти все могут это сделать, но открыть его (расшифровывание) имеет возможность только владелец ключа. Понимание того, как защелкнуть замок, чтобы он закрылся, ничего не скажет вам, как его отпереть. Можно провести и более глубокую аналогию. Представьте, что Алиса проектирует замок и ключ. Она бдительно охраняет ключ, но при этом изготавливает тысячи дубликатов замков и рассылает их по почтовым отделениям по всему миру. Если Боб хочет послать сообщение, он кладет его в коробку, идет на местный почтамт, просит «замок Алисы» и запирает им коробку. Теперь уже ему не удастся открыть коробку, но когда коробку получит Алиса, она сможет открыть ее своим единственным ключом. Замок и защелкивание его, чтобы он закрылся, эквивалентны общему ключу для зашифровывания, поскольку все имеют доступ к замкам и все могут воспользоваться замком, чтобы закрыть сообщение в коробке. Ключ от замка эквивалентен секретному ключу для расшифровывания, потому что он имеется только у Алисы, только она сможет открыть замок, и только она сможет получить доступ к находящемуся в коробке сообщению.

Эта система представляется простой, если рассматривать ее применительно к замкам, но далеко не так-то легко найти такую математическую функцию, которая выполняет то же самое действие, функцию, которую можно было бы включить в работоспособную криптографическую систему. Чтобы перейти от прекрасной идеи к практической реализации асимметричных шифров, кто-то должен найти подходящую математическую функцию. Диффи рассматривал специальный тип односторонней функции — функции, которая могла бы быть обратимой при особых обстоятельствах. В асимметричной системе Диффи Боб зашифровывает сообщение с помощью открытого ключа, но он не может расшифровать его — это, по сути, односторонняя функция. Однако Алиса сможет расшифровать сообщение, поскольку у нее есть секретный ключ — специальная порция информации, которая дает ей возможность провести обратное вычисление функции. Еще раз — замки являются хорошей аналогией — запирание замка представляет собой одностороннюю функцию, поскольку обычно сложно открыть замок, если только у вас нет специального инструмента (ключа) — в этом случае функция становится легко обратимой.

Диффи опубликовал основные принципы своей идеи летом 1975 года, после чего другие ученые присоединились к поискам подходящей односторонней функции, функции, которая отвечала бы критериям, требующимся для асимметричного шифра. Вначале все были настроены крайне оптимистично, но к концу года никто так и не смог найти подходящую кандидатуру. Шли месяцы, и все больше и больше создавалось впечатление, что специальных односторонних функций не существует. Казалось, что идея Диффи работала только в теории, но не на практике. Тем не менее к концу 1976 года команда Диффи, Хеллмана и Меркля произвела переворот в мире криптографии. Они убедили всех, что решение проблемы распределения ключей существует, и создали алгоритм обмена ключами Диффи-Хеллмана-Меркля — работоспособную, хотя и несовершенную систему, а также предложили концепцию асимметричного шифра — совершенную, но пока что неработоспособную систему. Свои исследования они продолжили в Стэнфордском университете, стараясь отыскать специальную одностороннюю функцию, которая позволила бы сделать асимметричные шифры реальностью. Однако найти ее им не удалось. Состязания по поиску асимметричного шифра выиграла другая троица исследователей, которая находилась за 5000 км от них, на восточном побережье Америки.

Главные подозреваемые

«Я вошел в кабинет Рона Ривеста, — вспоминает Леонард Адлеман, — и Рон держал в руках эту статью. Он начал было говорить: «Эти парни из Стэнфорда действительно сделали эту ерунду». А я в этот момент, помнится, подумал: «Это прекрасно, Рон, но мне бы хотелось поговорить о другом». Я совсем не знал истории криптографии, и меня совершенно не интересовало, о чем он говорит». Статью, которая привела Рона Ривеста в такое возбуждение, написали Диффи и Хеллман, и в ней была дана концепция асимметричных шифров. В конце концов, Ривес убедил Адлемана, что в этой проблеме может заключаться интересная математика, и они решили вместе попытаться найти одностороннюю функцию, которая удовлетворяла бы требованиям асимметричного шифра. К ним присоединился также Ади Шамир. Все трое были исследователями и работали в лаборатории вычислительной техники на восьмом этаже Массачусетского технологического института.