Книга шифров. Тайная история шифров и их расшифровки
Шрифт:
Хеллман разрушил один из догматов криптографии и доказал, что Бобу и Алисе не нужно встречаться, чтобы условиться о секретном ключе. Теперь уже кто-нибудь просто обязан был предложить более эффективную схему, позволяющую справиться с проблемой распределения ключей.
Мэри Фишер никогда не забудет тот день, когда Уитфилд Диффи впервые пригласил ее на свидание: «Он знал, что я была фанатично предана космосу, и поэтому предложил пойти посмотреть на запуск ракеты. Уит объяснил, что сегодня вечером он ушел, чтобы увидеть старт Скайлэба, и мы ехали всю ночь и прибыли туда примерно в 3 утра. Как в те дни говорили, «птичка уже летела к нам». У Уита было удостоверение представителя прессы, но у меня его не было. Поэтому, когда потребовали мое удостоверение личности и спросили, кто я такая, Уит ответил: «Моя жена». Это было 16 ноября 1973 года». В конце концов, они действительно поженились, и в первые годы Мэри поддерживала мужа во время его криптографических раздумий. Диффи все еще работал в качестве аспиранта, получая скудное жалованье. И чтобы свести концы с концами, Мэри, археолог по образованию, нанялась
Когда Мартин Хеллман открыл свой метод обмена ключами, Уитфилд Диффи разрабатывал совершенно иной подход к решению проблемы распределения ключей. У него часто случались долгие периоды бесплодных раздумий во время одного из которых, в 1975 году, он был настолько расстроен, что уверял Мэри, что он неудачник, который никогда ничего не добьется, и даже предложил ей найти кого-нибудь другого. Но в ответ Мэри возразила, что она беспредельно верит в него, а спустя всего лишь две недели Диффи предложил поистине блестящую идею.
Он до сих пор вспоминает, как идея мелькнула у него в голове, а затем чуть было не исчезла: «Я спускался вниз по лестнице, чтобы купить кока-колу, и почти забыл об идее. Я помнил, что думал о чем-то интересном, но совершенно не мог припомнить, что же это было. Затем она всплыла в памяти, и я почувствовал прилив возбуждения с настоящим адреналиновым шоком. Впервые с тех пор, как я начал заниматься криптографией, я понимал, что обнаружил что-то действительно стоящее. Все, что мне удавалось до сегодняшнего дня найти в этой области, представлялось просто техническими деталями». Это случилось в полдень, и Диффи пришлось томиться ожиданием еще пару часов, пока не вернулась Мэри. «Уит ждал у двери», — вспоминает она. «Он сказал, что должен что-то сообщить мне, и у него было забавное выражение лица. Я вошла, и он произнес: «Сядь, пожалуйста, я хочу поговорить с тобой. Я думаю, что сделал великое открытие; я знаю, что я — первый человек, который сделал это». В этот момент весь мир для меня замер. Я почувствовала себя так, словно я — героиня голливудского фильма».
Диффи придумал новый вид шифра — шифра, который включал в себя так называемый асимметричный ключ. Все те алгоритмы шифрования, о которых до сих пор рассказывалось в этой книге, были симметричными, то есть расшифровывание представляло собой просто процесс, обратный зашифровыванию. К примеру, чтобы зашифровать сообщение, в шифровальной машине «Энигма» используется определенный ключ, а получатель, чтобы его расшифровать, использует идентичную шифровальную машину с тем же самым ключом. Точно так же при зашифровывай и и с помощью алгоритма DES применяется ключ для выполнения 16 раундов шифрования, а затем при расшифровывании с помощью алгоритма DES используется этот же ключ для выполнения 16 раундов, только в обратном порядке. Оба, и отправитель, и получатель, фактически обладают равным знанием, и оба они используют один и тот же ключ для зашифровывания и расшифровывания, то есть их взаимоотношение является симметричным. С другой стороны, в системе с асимметричным ключом, как это следует из названия, ключ для зашифровывания и ключ для расшифровывания не идентичны. При использовании асимметричного шифра, если Алиса знает ключ для зашифровывания, она сможет зашифровать сообщение, но вот расшифровать его не сумеет. Чтобы расшифровать сообщение, Алиса должна иметь доступ к ключу для расшифровывания. Вот в этом-то различии между ключом для зашифровывания и ключом для расшифровывания и заключается особенность асимметричного шифра.
Здесь стоит подчеркнуть, что, хотя Диффи сформулировал общую концепцию асимметричного шифра, но на самом деле никакого конкретного примера такого шифра у него не было. Но даже просто концепция асимметричного шифра стала революционной. Если бы криптографы смогли найти действительно работающий асимметричный шифр — систему, которая отвечает требованиям Диффи, — то для Алисы и Боба это будет иметь огромное значение. Алиса могла бы создавать свою собственную пару ключей: один ключ для зашифровывания и один — для расшифровывания. Если предположить, что асимметричный шифр является видом компьютерного шифрования, тогда Алисин ключ для зашифровывания является одним числом, а ключ для расшифровывания — другим числом. Ключ для расшифровывания Алиса хранит в секрете, поэтому он обычно называется секретным ключом Алисы. В то же время свой ключ для зашифровывания она предает гласности, так что все имеют к нему доступ, вот почему он обычно называется открытым ключом Алисы. Если Боб хочет послать Алисе сообщение, он просто ищет ее открытый ключ, который будет указан в чем-то сродни телефонному справочнику. Затем Боб берет этот открытый ключ Алисы и зашифровывает сообщение. Он посылает зашифрованное сообщение Алисе, и, когда оно приходит, Алиса может расшифровать его с помощью своего секретного ключа для расшифровывания. Точно так же, если зашифрованное сообщение Алисе хотят послать Чарли, Дон или Эдвард, они также могут отыскать открытый ключ Алисы для зашифровывания, и в каждом случае только Алиса имеет доступ к секретному ключу, необходимому, чтобы расшифровать сообщения.
Важным достоинством этой системы является то, что здесь нет той суматохи, как при использовании алгоритма обмена ключами Диффи-Хеллмана-Меркля. Бобу больше нет нужды ждать, пока придет информация от Алисы, прежде чем он сможет зашифровать и послать ей сообщение; ему просто надо найти ее открытый ключ для зашифровывания. К тому же асимметричный шифр еще и позволяет разрешить проблему распределения ключей. Алисе не требуется секретно доставлять открытый ключ для зашифровывания Бобу; напротив, она может теперь всем и всюду сообщать о своем открытом ключе для зашифровывания. Она хочет, чтобы весь мир знал ее открытый ключ для зашифровывания, чтобы любой мог воспользоваться им и слать ей зашифрованные сообщения. Но в то же время, даже если весь мир будет знать открытый ключ Алисы, ни один человек, включая Еву, не сможет расшифровать зашифрованные этим ключом сообщения, поскольку знание открытого ключа не поможет в расшифровывании. Кстати, после того как Боб зашифрует сообщение с помощью открытого ключа Алисы, даже он не сможет расшифровать его. Одна лишь Алиса, у которой имеется секретный ключ, сумеет расшифровать сообщение.
То есть здесь, в отличие от традиционного симметричного шифра, когда Алисе приходилось идти на все, чтобы безопасным образом передать ключ для зашифровывания Бобу, ситуация прямо противоположная. В симметричном шифре ключ для зашифровывания и ключ для расшифровывания один и тот же, так что Алиса и Боб должны были принимать изрядные меры предосторожности, чтобы ключ не попал в руки Евы. Это — основа основ в проблеме распределения ключей.
Если вернуться к аналогии с замками, то шифрование с открытым ключом можно представить себе следующим образом. Любой способен запереть замок, просто защелкнув его, чтобы он закрылся, но отпереть его может только тот, у кого есть ключ. Запереть замок (зашифровывание) легко, почти все могут это сделать, но открыть его (расшифровывание) имеет возможность только владелец ключа. Понимание того, как защелкнуть замок, чтобы он закрылся, ничего не скажет вам, как его отпереть. Можно провести и более глубокую аналогию. Представьте, что Алиса проектирует замок и ключ. Она бдительно охраняет ключ, но при этом изготавливает тысячи дубликатов замков и рассылает их по почтовым отделениям по всему миру. Если Боб хочет послать сообщение, он кладет его в коробку, идет на местный почтамт, просит «замок Алисы» и запирает им коробку. Теперь уже ему не удастся открыть коробку, но когда коробку получит Алиса, она сможет открыть ее своим единственным ключом. Замок и защелкивание его, чтобы он закрылся, эквивалентны общему ключу для зашифровывания, поскольку все имеют доступ к замкам и все могут воспользоваться замком, чтобы закрыть сообщение в коробке. Ключ от замка эквивалентен секретному ключу для расшифровывания, потому что он имеется только у Алисы, только она сможет открыть замок, и только она сможет получить доступ к находящемуся в коробке сообщению.
Эта система представляется простой, если рассматривать ее применительно к замкам, но далеко не так-то легко найти такую математическую функцию, которая выполняет то же самое действие, функцию, которую можно было бы включить в работоспособную криптографическую систему. Чтобы перейти от прекрасной идеи к практической реализации асимметричных шифров, кто-то должен найти подходящую математическую функцию. Диффи рассматривал специальный тип односторонней функции — функции, которая могла бы быть обратимой при особых обстоятельствах. В асимметричной системе Диффи Боб зашифровывает сообщение с помощью открытого ключа, но он не может расшифровать его — это, по сути, односторонняя функция. Однако Алиса сможет расшифровать сообщение, поскольку у нее есть секретный ключ — специальная порция информации, которая дает ей возможность провести обратное вычисление функции. Еще раз — замки являются хорошей аналогией — запирание замка представляет собой одностороннюю функцию, поскольку обычно сложно открыть замок, если только у вас нет специального инструмента (ключа) — в этом случае функция становится легко обратимой.
Диффи опубликовал основные принципы своей идеи летом 1975 года, после чего другие ученые присоединились к поискам подходящей односторонней функции, функции, которая отвечала бы критериям, требующимся для асимметричного шифра. Вначале все были настроены крайне оптимистично, но к концу года никто так и не смог найти подходящую кандидатуру. Шли месяцы, и все больше и больше создавалось впечатление, что специальных односторонних функций не существует. Казалось, что идея Диффи работала только в теории, но не на практике. Тем не менее к концу 1976 года команда Диффи, Хеллмана и Меркля произвела переворот в мире криптографии. Они убедили всех, что решение проблемы распределения ключей существует, и создали алгоритм обмена ключами Диффи-Хеллмана-Меркля — работоспособную, хотя и несовершенную систему, а также предложили концепцию асимметричного шифра — совершенную, но пока что неработоспособную систему. Свои исследования они продолжили в Стэнфордском университете, стараясь отыскать специальную одностороннюю функцию, которая позволила бы сделать асимметричные шифры реальностью. Однако найти ее им не удалось. Состязания по поиску асимметричного шифра выиграла другая троица исследователей, которая находилась за 5000 км от них, на восточном побережье Америки.
Главные подозреваемые
«Я вошел в кабинет Рона Ривеста, — вспоминает Леонард Адлеман, — и Рон держал в руках эту статью. Он начал было говорить: «Эти парни из Стэнфорда действительно сделали эту ерунду». А я в этот момент, помнится, подумал: «Это прекрасно, Рон, но мне бы хотелось поговорить о другом». Я совсем не знал истории криптографии, и меня совершенно не интересовало, о чем он говорит». Статью, которая привела Рона Ривеста в такое возбуждение, написали Диффи и Хеллман, и в ней была дана концепция асимметричных шифров. В конце концов, Ривес убедил Адлемана, что в этой проблеме может заключаться интересная математика, и они решили вместе попытаться найти одностороннюю функцию, которая удовлетворяла бы требованиям асимметричного шифра. К ним присоединился также Ади Шамир. Все трое были исследователями и работали в лаборатории вычислительной техники на восьмом этаже Массачусетского технологического института.