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

По мере роста масштабов коммерческих сетей, передачи все большего числа сообщений и необходимости доставки все большего количества ключей, банки пришли к заключению, что процесс распределения превратился в ужасающий кошмар, а накладные расходы стали непомерно высоки. Правительство и вооруженные силы способны до известной степени справиться с проблемой распределения ключей, вкладывая в ее решения средства и ресурсы. Контролем и распределением ключей правительства США ведает подразделение COMSEC. В 70-х годах она отвечала за перевозку огромного количества ключей текущего дня. Когда корабли, перевозящие материалы COMSEC, швартовались у причала, сотрудники, отвечающие за хранения крипто ключей, забирали все носители на которых могли храниться ключи и доставляли их адресатам

Распределение ключей может показаться рутинной задачей, но она стала важнейшей для послевоенных криптографов. Если две стороны хотят обеспечить безопасный обмен информацией, они вынуждены полагаться на третьего участника, который осуществляет доставку ключа, и становится самым слабым звеном в цепи Несмотря на заявления, что проблема распределения ключей неразрешима, команда ярких личностей справилась с ней и в середине 70-х предложила блестящее решение.Хотя компьютеры неузнаваемо изменили применение шифров, разработка способов преодоления проблемы распределения ключей явилась поистине переворотом в криптографии двадцатого столетия.

Уитнфилд Диффи – один из криптографов-интузиастов своего поколения. Родился в 1944 году и большую часть детства жил в Куинсе, одном из районов Нью-Йорка. Еще ребенком он увлекался математикой. Продолжил ее изучение в Массачусетском технологическом институте, который окончил в 1965 году. И к началу 70-х годов, проработав в нескольких местах, стал одним из нескольких полностью независимых экспертов по безопасности. Диффи особенно интересовался проблемой распределения ключей, и он понял что тот, кому удастся найти решение, войдёт в историю как один из самых величайших криптографов

Отчасти Диффи занялся этой проблемой еще и потому, что в воображении ему виделся мир, весь опутанный проводами.В конце 80-х доступ к Интернету получили пользователи, не являющиеся сотрудниками учебных заведений и правительственными служащими; с этого момента число пользователей стало быстро возрастать. Сегодня более сотни миллионов людей используют Интернет для обмена информацией и отправки сообщений по электронной почте. Диффи был убежден, что если люди будут пользоваться своими компьютерами для обмена сообщениями по электронной почте, то они должны обладать правом зашифровывать их для обеспечения секретности переписки. Количество сообщений передаваемых пользователями по электронной почте будет огромным, это означает, что распределение ключей окажется практически невыполнимым.

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

Когда Хеллман приступил к исследованиям, он наткнулся на книгу «Взломщики кодов» историка Дэвида Кана. В этой книге впервые подробно рассказывается о развитии шифров, и в этом качестве она являлась прекрасным учебником для начинающих криптографов. «Взломщики кодов» была единственным помощником Хеллмана вплоть до сентября 1974 года, когда ему неожиданно позвонил Уитфилд Диффи. У Хеллмана не было возможности нанять на работу своего нового единомышленника в качестве исследователя. Вместо этого Диффи был зачислен как аспирант. Теперь уже они вместе, приступили к изучению проблемы распределения ключей, отчаянно пытаясь найти альтернативу неинтересной задаче физической перевозки ключей на большие расстояния. Через некоторое время к ним присоединился Ральф Меркль

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

Обмен ключами при личной встрече является, несомненно, безопасным, но неудобным способом, ведь если Алиса или Боб заболеют, вся эта система перестанет работать. Или же Алиса и Боб могли бы нанять курьеров, что оказалось бы менее надежно и более затратно, но им хотя бы перепоручили часть работы. Так ли, иначе ли, но, похоже, распределения ключей не избежать. В течение двух тысяч лет это считалось аксиомой криптографии непререкаемой истиной.

Можно, однако, поставить мысленный эксперимент. Алиса хочет отправить сообщение Бобу. Она кладет его в железную коробку, закрывает ее и запирает ключом замок. Затем она кладет запертую на замок коробку в почтовый ящик, а ключ оставляет себе. Но когда коробку доставляют Бобу, он не может открыть ее, так как у него нет ключа. Алиса может положить ключ в другую коробку, замкнуть ее на замок и отправить Бобу, но без ключа ко второму замку он не сможет открыть вторую коробку и достать оттуда ключ, которым откроет первую коробку. Для Алисы, по-видимому, единственный путь обойти эту проблему это сделать дубликат своего ключа и заранее передать его Бобу, при личной встречи. До этого момента это та же старая задача в новых условиях. Избежать распределения ключей кажется логически невозможным; если Алиса хочет запереть что-то в коробке так, чтобы только Боб мог открыть ее она, безусловно, должна дать ему дубликат ключа. Обмен ключами является неизбежной частью шифрования или все-таки нет?

Теперь представим следующую картину. Как и прежде, Алиса хочет отправить сообщение Бобу. Она опять кладет свое секретное сообщение железную коробку, запирает ее на замок и посылает Бобу. Когда коробка приходит, Боб навешивает свой собственный замок и высылает коробку обратно Алисе. Когда Алиса получит коробку, она уже заперта на два замка. Алиса снимает свой замок, оставляя на коробке только замок Боба, после чего посылает коробку назад Бобу. И вот здесь-то и заключается принципиальная разница: теперь Боб может открыть коробку, поскольку она заперта только на его собственный замок, к которому он один имеет ключ. Мы можем дать другое истолкование истории применительно к шифрованию. Алиса использует свой собственный ключ, чтобы зашифровать сообщение Бобу, который в свою очередь зашифровывает его уже своим ключом и возвращает его обратно. Когда Алиса получает дважды зашифрованное сообщение, она убирает свое шифрование и отсылает назад сообщение Бобу, который после этого может убрать уже свое Шифрование и прочитать сообщение.

Кажется, что проблема распределения ключей может быть решена, поскольку в схеме с двойным зашифровывай нем не требуется обмена ключами. Существует, однако, фундаментальное препятствие реализации системы, порядок зашифровывания и расшифровывания является принципиальным и должен подчиняться принципу «последним пришел, первым ушел». Другими словами, последний этап при зашифровывании должен быть первым этапом при расшифровывании. Представим, что у Алисы и Боба имеются свои собственные ключи и давайте взглянем, что случится, если порядок неправильный. В результате получается бессмыслица.

Несмотря на то что на практике принцип запертой на два замка коробк работать не будет, он вдохновил Диффи и Хеллмана на поиск способа, позволяющего избежать проблемы распределения ключей. Весной 1976 года он натолкнулся на алгоритм решения проблемы обмена ключами. За полчаса исступленной работы он доказал, что Алиса и Боб могут договориться о ключе, не встречаясь друг с другом, покончив, тем самым, с аксиомой, считавшейся не- прорекаемой в течение столетий. Идея Хеллмана основывалась на использовании односторонней функции вида V * (mod Р). Вначале Алиса и Боб договариваются о значениях чисел У и Р. Подходят почти любые значения за исключением некоторых ограничений; так, например, У должно быть меньше, чем Р. Рис. : Вычисленные значения функции У в обычной арифметике (ряд 2) и модулярной арифетике (ряд 3).

Даже если телефонная линия ненадежна и подлая Ева слышит этот разговор, это не имеет значения. Алиса и Боб договорились об значениях У =7 и Р =11.. Даже если телефонная линия ненадежна и подлая Ева слышит этот разговор, это, как мы увидим позже, не имеет значения. Алиса й Боб договорились об односторонней функции 7 х (mod 11). Сейчас они уже могут начать процесс создания секретного ключа. Внимательно изучив этапы в таблице видно, что и не встречаясь Алиса и Боб договорились об одном и том же ключе, который они могут использовать для зашифровывания сообщения, Например, они могут использовать свое число 9 в качестве ключа для DES-шифрования. Проверим схему Хеллмана с позиции Евы. Если она подключилась к линии, ей станут известны только следующие факты: Что функцией является 7 х (mod 11),что Алиса отправила α =* 2 и что Боб отправил β = 4. Чтобы определить ключ, она должна сделать либо то, что делает Боб, который, зная В преобразует в ключ α, либо то, что делает, Алиса, которая, зная А, преобразует в ключ β. Однако Ева не знает, чему равны А к В, потому что Алиса и Боб не обменивались значениями этих чисел.

АлисаБоб Этап 1Выбирает число, к примеру, 3 и хранит его в секрете. Обозначим это число А. Выбирает число, к примеру, 6 и хранит его в секрете. Обозначим это число А. Этап 2Подставляет 3 в одностороннюю функцию и вычисляет результат вычисляет результат 7 А (mod 11): 7 3 (mod 11) = 343 (mod 11) 2 Подставляет 3 в одностороннюю функцию и вычисляет результат вычисляет результат 7 В (mod 11): 7 6 (mod 11) = 343 (mod 11) 4 Этап 3Обозначает результат своего вычисления как α и отправляет свой результат, 2, Бобу Обозначает результат своего вычисления как β и отправляет свой результат, 4, Алисе Обмен информ ацией Обычно этот момент является критическим, поскольку Алиса и Боб осуществляют обмен информацией, и у Евы появляется удобная возможность ее перехватить и выяснить все подробности. Однако оказывается, что, даже если Ева подслушает их, это никак не скажется на стойкости. Этап 4Получает результат Боба и вычисляет значение β А (mod 11): 4 3 (mod 11) = 64 (mod 11) = 9 Получает результат Боба и вычисляет значение α А (mod 11): 4 3 (mod 11) = 64 (mod 11) = 9 КлючАлиса и Боб закончили вычисления, получив одно и тоже число 9 Это и есть ключ

Боб и Алиса передали друг другу ровно столько информации, сколько нужно, чтобы дать им возможность создать ключ, но Еве для вычисления ключа ее оказывается недостаточно. Чтобы показать, как работает схема Хеллмана, представьте шифр, в котором в качестве ключа каким-то образом используется цвет. Допустим вначале, что у всех, включая Алису, Боба и Еву, имеется трехлитровая банка, в которую налит один литр желтой краски. Если Алиса и Боб хотят договориться о секретном ключе, они добавляют в свои банки по одному литру своей собственной секретной краски. Алиса может добавить краску фиолетового оттенка, а Боб малинового. После этого каждый из них посылает свою банку с перемешанным содержимым другому. И наконец, Алиса берет смесь Боба и подливает в нее один литр своей секретной краски, а Боб берет смесь Алисы и добавляет в нее один литр своей секретной краски. Краска в обеих банках теперь станет одного цвета, поскольку в каждой находится по одному литру желтой, фиолетовой и малино­вой краски. Именно этот цвет, полученный при добавлении дважды в банки красок, и будет использоваться как ключ.

Алиса понятия не имеет, какую краску добавил Боб, а Боб также не представляет, какую краску налила Алиса, но оба они достигли одного и того же результата. Между тем Ева в ярости. Даже если она и сумеет перехватить банки с промежуточным продуктом, ей не удастся определить конечный цвет, который и будет согласованным ключом. Ева может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Алисы в банке, отправленной Бобу, и она может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Боба в банке, отправленной Алисе, но чтобы найти ключ, ей, на самом деле, необходимо знать цвета исходных секретных красок Алисы и Боба. Однако, рассматривая банки с перемешанными красками, Ева не сможет определить секретные краски Алисы и Боба. Даже если она возьмет образец одной из смешанных красок, ей не удастся разделить ее на исходные краски, чтобы найти секретную, поскольку смешивание краски является односторонней функцией.

Хотя обмен ключами Диффи-Хеллмана-Меркля оказался гигантским шагом вперед, сама система была несовершенной, поскольку по своей сути оказалась неудобной. Представим, что Алиса живет на Гавайях и хочет послать сообщение по электронной почте Бобу, живущему в Стамбуле. Боб в этот момент, возможно, спит, но электронная почта удобна тем, что Алиса может послать сообщение в любой момент и оно будет находиться в компьютере Боба, ожидая, пока он не проснется. Однако, если Алиса желает зашифровать свое сообщение, то ей нужно согласовать ключ с Бобом, а чтобы осуществить обмен ключами, для Алисы и Боба лучше одновременно находиться в режиме онлайн, так как для создания ключа требуется обоюдный обмен информацией. Так что Алисе придется ждать, пока проснется Боб. Как вариант, Алиса могла бы отправить свою часть и ожидать 12 часов ответа Боба; при получении ответа Боба ключ будет создан, и Алиса сможет, если сама не будет спать в это время, зашифровать и отправить сообщение. Так или иначе, но система обмена ключами Хеллмана затрудняет непринужденное общение по электронной почте.

Диффи придумал новый вид шифра - шифра, который включал в себя так называемый асимметричный ключ. До этого все алгоритмы шифрования, были симметричными, то есть расшифровывание представляло собой просто процесс, обратный зашифровыванию. К примеру, чтобы зашифровать сообщение, в шифровальной машине «Энигма» используется определенный ключ, а получатель, чтобы его расшифровать, использует идентичную шифровальную машину с тем же самым ключом Точно так же при зашифровывай»» с помощью алгоритма DES применяется ключ для выполнения 16 раундов шифрования, а затем мри расшифровывании с помощью алгоритма DES используется этот же ключ для выполнения 16 раундов, только в обратном порядке. Оба, и отправитель, и получатель, фактически обладают равным знанием, и оба они используют один и тот же ключ для зашифровывания и расшифровывания, то есть их взаимоотношение является симметричным.

В системе с асимметричным ключом, как это следует из названия, ключ для зашифровывания и ключ для расшифровывания не идентичны При использовании асимметричного шифра, если Алиса знает ключ для зашифровывания, она сможет зашифровать сообщение, но вот расшифровать его не сумеет. Чтобы расшифровать сообщение, Алиса должна иметь доступ к ключу для расшифровывания. Вот в этом то различии между ключом для зашифровывания и ключом для расшифровывания и заключается особенность асимметричного шифра. Хотя Диффи и сформулировал общую концепцию асимметричного шифра, но на самом деле никакого конкретного примера такого шифра у него не было. Но даже просто концепция асимметричного шифра стала революционной. Если бы криптографы смогли найти действительно работающий асимметричный шифр - систему, которая отвечает требованиям Диффи, - то для Алисы и Боба это будет иметь огромное значение Алиса могла бы создавать свою собственную пару ключей: один ключ для зашифровывания и один для расшифровывания.

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

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

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

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

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

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

Свои исследования они продолжили в Стен­фордском университете, стараясь отыскать специальную одностороннюю функцию, которая позволила бы сделать асимметричные шифры реальностью. Однако найти ее им не удалось. Состязания по поиску асимметричного шифра выиграла другая троица исследователей, которая находилась за 5000 км от них, на восточном по­бережье Америки.

Леонард Адлеман Рон Ривест а так же присоединившийся к ним позднее Адн Шамир составили великолепную команду. Ривест был специалистом в области теории вычислительных машин и систем; он обладал исключительной способностью впитывать новые идеи и применять их в самых неожиданных областях. Он всегда был в курсе последних научных статей, служивших источником его идей, то и дело предлагая причудливые и поразительные кандидатуры на лежащие в основе асимметричного шифра односторонние функции. Но в каждой из них обнаруживались изъяны. Шамир, еще один ученый в той же области, имел быстрый ум, необычайную проницательность и способность концентрироваться на сути проблемы. Он также регулярно генерировал идеи по созданию асимметричного шифра, но и они также неизменно оказывались ошибочными, Адлеман, математик, отличающийся огромным упорством и терпением, был занят преимущественно тем, что выискивал в идеях Ривеста и Шамира недостатки и слабые места, гарантируя тем самым, что они не станут впустую тратить время.

В апреле 1977 года Ривест, Шамир и Адлеман отмечали еврей­скую Пасху в студенческом общежитии колледжа и выпили значи­тельное количество вина Манишевич, а где-то около полуночи от­ правились по домам. Ривест лежа на кровати, читал учебник по математике. Непроизвольно он начал размышлять над вопросом, который занимал его уже много недель: можно ли создать асимметричный шифр? Существует ли односторонняя функция, которую можно было бы обратить, только если у получателя есть некая специальная информация? Внезапно туман в голове стал рассеиваться, и на него снизошло откровение. Остаток ночи он провел, формализуя свою идею, и, еще до того, как наступил рассвет, практически написал законченную научную статью- Ривест сделал открытие, но состоялось оно только благодаря длившемуся целый год сотрудничеству с Шамиром и Адлеманом, а без них оказалось бы невозможным. Закончил статью Ривест перечислением авторов в алфавитном порядке: Адлеман, Ривест, Шамир.

На следующее утро Ривест передал статью Адлеману, который, как обычно, постарался ее растерзать, но на сей раз он не смог найти ни одной ошибки. Единственно, он раскритиковал список авторов. «Я попросил Рона, чтобы он убрал мое имя статьи, вспоминает Адлеман. Я сказал ему, что это его открытие, а не мое. Но Рон отказался, и в результате завязался спор. Мы порешили, что я отправлюсь домой, поразмышляю над этим ночь и скажу, чего бы мне хотелось. На следующий день я вернулся и предложил Рону, чтобы он поставил меня третьим автором.» Алгоритм, получивший название RSA (Ривест, Шамир, Адлеман), а не ARS, стал важнейшим шифром в современной криптографии.

На следующее утро Ривест передал статью Адлеману, который, как обычно, постарался ее растерзать, но на сей раз он не смог найти ни одной ошибки. Единственно, он раскритиковал список авторов. «Я попросил Рона, чтобы он убрал мое имя статьи, вспоминает Адлеман. Я сказал ему, что это его открытие, а не мое. Но Рон отказался, и в результате завязался спор. Мы порешили, что я отправлюсь домой, поразмышляю над этим ночь и скажу, чего бы мне хотелось. На следующий день я вернулся и предложил Рону, чтобы он поставил меня третьим автором.» Алгоритм, получивший название RSA (Ривест, Шамир, Адлеман), а не ARS, стал важнейшим шифром в современной криптографии.

Душой асимметричного шифра Ривеста является односторонняя функция, основанная на модулярной функции. Односторонняя функция Ривеста может применяться для зашифровывания сообщения; к сообщению, которое в нашем случает является числом, применяется функция, и в результате получается шифртекст - другое число. N - важный аспект делает при определенных обстоятельствах одностороннюю функцию обратимой и, тем самым, идеальной для применения в качестве асимметричного шифра. N важно, поскольку оно представляет собой изменяющийся элемент односторонней функции, благодаря чему каждый человек может выбирать различные значения N, образуя всякий раз различные односторонние функции. Чтобы выбрать свое собственное значение N Алиса берет два простых числа, p и q, и перемножает их. Алиса может выбрать свои простые числа, например, p=17159и q= Перемножая эти два числа, она получает N ~ х = Полученное Алисой N фактически будет ее открытым ключом для зашифровывания, и она может напечатать его на своей визитной карточке, разместить в Интернете или опубликовать в справочнике открытых ключей вместе со значениями N других людей.

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

Однако остается вопрос, как же Алиса сумеет его расшифровать? Чтобы прочитать присланные ей сообщения, у Алисы должен быть способ обращения односторонней функции. Ей необходимо иметь доступ к некоторой специальной порции информации, которая и даст ей возможность расшифровать сообщение. Для Алисы, Ривест задумал и создал одностороннюю функцию таким образом, что она является обратимой для каждого, кто знает значения р и q - два простых числа, которые были перемножены для получения N. Хотя Алиса сообщила всем, что у нее N равняется она не раскрыла значений р и q, поэтому только у нее есть специальная информация, необходимая для расшифровки своих сообщений.

Если все знают открытый ключ N, то разве нельзя найти p и q секретный ключ - и прочесть сообщения Алисы. В действительности же оказывается, что если N достаточно велико, то из него практически невозможно вычислить р и q, и это, пожалуй, самый превосходный и элегантный аспект в асимметричном шифре RSA. Алиса образовала N, выбрав p и q, а затем перемножив их вместе. Основной момент здесь заключается в том, что это по своей сути односторонняя функция. Чтобы продемонстрировать односторонний характер умножения простых чисел, мы можем взять два простых числа, например, 9419 и 1933, и перемножить их. Используя калькулятор, нам понадобится всего лишь несколько секунд, чтобы получить ответ Однако, если вместо этого нам дадут число и попросят найти простые множители это займет у нас гораздо больше времени.

Чтобы понять, насколько надежна RSA, мы можем проверить ее с точки зрения Евы и попробовать прочесть сообщение, посланное Алисой Бобу. Для того чтобы зашифровать сообщение для Боба, Алиса должна отыскать его открытый ключ. Для создания своего открытого ключа. Боб берет выбранные им самим простые числа, p в и q в, и перемножает их, получая N B. Он хранит р в и q в в секрете, ибо они составляют его секретный ключ для расшифровывания, но при этом публикует Nv, которое равно Так что Алиса подставляет открытый ключ Боба N B в общую одностороннюю функцию шифрования, а затем зашифровывает свое сообщение ему. Когда приходит зашифрованное сообщение, Боб может обратить функцию и расшифровать его, используя значения р в и q в, которые составляют его секретный ключ. Между тем Ева сумела во время передачи сообщения перехватить его. Ее единственная надежда расшифровать сообщение обратить одностороннюю функцию, а это возможно только в том случае, если она знает р в и q в. Боб держит p v и q v в секрете, но, как и всем остальным, Еве известно N B, равное Далее Ева пытается найти значения р в и q в путем подбора чисел, которые при перемножении дают процесс, известный как разложение на множители.

Операция разложения на множители отнимает очень много времени, но сколько же на самом деле понадобится Еве времени, чтобы найти сомножители числа ? Существуют различные способы разложения на множители числа N B. Хотя одни из них быстрее, а другие медленнее, но по сути во всех них проверяется, делится ли N B без остатка на каждое из простых чисел. Например, 3 - это простое число, но оно не является множителем числа , так как нацело на 3 не делится. Поэтому Ева берет следующее простое число точно также не является множителем, поэтому Ева переходит к следующему простому числу и так далее. В конце концов, Ева добирается до числа , 2000-го простого числа, которое является множителем числа Найдя один из сомножителей, легко найти и другой Ева сможет раскрыть секретный ключ Боба и, тем самым, расшифровать перехваченное сообщение менее, чем за день, Это не слишкомто высокий уровень стойкости, но Боб мог бы выбрать гораздо большие простые числа и повысить стойкость свое­го секретного ключа. Например, он мог бы выбрать простые числа, состоящие из цифр.

RSA является неуязвимой. Единственное предупреждение относительно надежности использования алгоритма RSA шифрования с открытым ключом это то, что в будущем кто-нибудь сможет найти способ быстро находить множители N. Возможно ктото откроет способ быстрого разложения на множители, после чего RSA станет бесполезным. Однако свыше двух тысяч лет математики пытались и не смогли его отыскать, и на сегодняшний момент для разложения на множители требуется огромное количество времени. Большинство математиков полагает, что разложение на множители по своей природе является трудной задачей и что существует некий математический закон, который запрещает любые ускоренные вычисления. Если, допустим, они правы, то RSA останется надежной в течение обозримого будущего.

Об RSA впервые было объявлено в августе 1977 года,- когда Мар­ тин Гарднер написал статью, озаглавленную «Новый вид шифра, для взлома которого потребуются миллионы,лет», для колонки «Математические игры» в «Сайентифик Америкен». Объяснив, как происходит шифрование с открытым ключом, Гарднер задал задачу своим читателям. Он напечатал зашифрованное сообщение и дал открытый ключ, который использовал для его зашифровывания: N = Призом были 100 долларов. У Гарднера не было места, чтобы объяснить все подробности алгоритма RSA; вместо этого он попросил читателей написать в лабораторию вычислительной техники Массачусетского технологического института, откуда им пришлют технический меморандум, который был как раз к тому времени подготовлен. Ривест, Шамир и Адлеман были поражены, получив три тысячи запросов. Однако ответили они не сразу, так как были обеспокоены, что открытое распространение их идеи могло бы поставить под угрозу получение патента.

Что касается задачи Гарднера, то для ее решения потребовалось 17лет. 26 апреля 1994 года команда из шестисот добровольцев сообщила о том, какие сомножители были у N: q= p= Используя эти значения в качестве секретного ключа, они смогли расшифровать сообщение которое гласило: «Волшебные слова: брезгливая скопа». Задача разложения на множители была распределена между добровольцами. Они использовали свободное время своих рабочих станций, больших ЭВМ и суперкомпьютеров; при этом каждый занимался только частью задачи. Даже принимая во внимание огромную работу, которая велась параллельно,можно подумать, что RSA была взломана за такое короткое время, но следует заметить, что в задаче Гарднера использовалось относительно малое значение N оно составляло порядка Сегодня, чтобы обеспечить безопасность жизненно важной информации, пользователи RSA могут брать гораздо большие значения.

Как заявило правительство Великобритании, шифрование с открытым ключом было первоначально разработано в Штаб-квартире правительственной связи в Челтенхеме, сверхсекретном учреждении, которое было сформировано из остатков Блечли-Парка после Второй мировой войны. История началась в конце 60-х годов, когда перед Вооруженными силами Великобритании встала проблема распределения ключей. Заглядывая в 70-е годы, высшие армейские чины представили себе ситуацию, когда миниатюризация и снижение стоимости радио при­ведет к тому, что у каждого солдата будет постоянная связь со своим офицером, но информация при этом должна передаваться в зашифрованном виде, и проблема распределения ключей оказалась бы непреодолимой.

В начале 1969 года представители вооруженных сил попросили Джеймса Эллиса, одного из ведущих правительственных криптографов Великобритании. изучить, каким образом можно было бы справиться с проблемой распределения ключей. Эллис был любознательным и слегка эксцентричным человеком. В школе его прежде всего интересовала наука. После школы он продолжил изучение физики в Имперском колледже, а затем поступил на службу в исследовательский центр Управления почт и телеграфа в Доллис Хилл, где Томми Флауэрс построил «Колосс», первый компьютер для взлома шифров. Криптографиическое отделение в Доллис Хилл было в итоге присоединено к ШКПС, и поэтому 1 апреля 1965 года Эллис был переведен в Челтенхем для работы во вновь созданном Отделении обеспечения скрытности работы средств связи и электронного оборудования, специальное подразделение в ШКПС, предназначенное для обеспечения безопасности британских средств коммуникации. В связи с тем, что его работа была связана с вопросами национальной безопасности, Эллис обязался хранить тайну в течение всего срока службы

Эллис приступил к решению проблемы с того, что перерыл всю свою сокровищницу научных статей. Много лет спустя он записал тот миг, когда обнаружил, что распределение ключей не является обязательной частью криптографии: «Случаем, который изменил мою точку зрения, послужило то, что я нашел подготовленный в военное время отчет неизвестного автора из компании Белл Телефон, в котором описывалась остроумная идея, как обезопасить телефонные разговоры. Предлагалось, чтобы тот, кто слушает, маскировал речь говорящего, создавая шум в линии. Потом он смог бы отсечь шум, так как это он создал его и потому знает, каков он. Использовать такую систему не позволили ее очевидные практические недостатки, но в ней было несколько интересных моментов. Разница между этой системой и обычным шифрованием заключалась в том, что в данном случае тот, кто слушает, участвует в процессе шифрования... Так родилась идея.»

Шумом называется любой сигнал, который накладывается на сигналы, используемые для связи. Обычно он создается естественными причинами, и больше всего в нем раздражает то, что он носит совершенно случайный характер, что означает, что убрать шум из сообщения крайне сложно. Эллис предложил, чтобы получатель, Алиса, намеренно создавала шум, который она может измерять перед тем, как подать его в канал связи, соединяющий ее и Боба. После этого Боб может послать сообщение Алисе; если же Ева подсоединится к каналу связи, она не сможет прочесть сообщение, потому что оно будет «утоплено» в шуме. Ева не сможет выделить сообщение из шума. Так что единственным человеком, который в состоянии устранить шум и прочесть сообщение будет Алиса, поскольку она единственная знает точную природу шума. Эллис понял, что безопасность достигнута без обмена какими-либо ключами. Ключом здесь послужил шум, и только Алисе требовалось знать вер об этом шуме.

В меморандуме Эллис подробно описал ход своих мыслей: «Следующий вопрос был очевиден.. Можем ли создать Надежным образом зашифрованное сообщение, которое сможет прочесть законный получатель без какого-то ни было предварительного секретного обмена ключом? Этот вопрос действительно както ночью, когда я лежал в кровати, пришел мне в голову, причем на доказательство теоретической возможности мне понадобилось всего несколько минут. Мы получили теорему существования. То, что представлялось немыслимым, на самом деле было возможно». Другими словами, вплоть до того момента поиск решения проблемы распределения ключей напоминал поиск иголки в стоге сена, причем была вероятность, что иголки там может и не быть вовсе. Однако благодаря теореме существования Эллис теперь знал, что иголка где-то там есть. Идеи Эллиса очень напоминали идеи Диффи, Хеллмана и Меркля, за исключением того, что он на несколько лет опережал их. Однако никто не знал о работе Эллиса, так как он был служащим Бри­танского правительства и потому дал клятву хранить тайну.

В конце 1969 года Эллис зашел в тот же тупик, что и стэнфордская троица в 1975 году. Он убедился, что криптография с открытым ключом возможна, и развил концепцию раздельных открытых и секретных ключей. Он также знал, что ему необходимо найти специальную одностороннюю функцию функцию, которая смогла бы стать обратимой, если получатель имел доступ к некоторому количеству специальной информации. К сожалению, Эллис не был математиком. Он поэкспериментировал с несколькими математическими функциями, но вскоре понял, что самостоятельно добиться большего не сможет. На этом этапе Эллис представил свое открытие руководству Следующие три года самые светлые умы ШКПС изо всех сил ста­рались отыскать одностороннюю функцию, которая удовлетворила бы требованиям Эллиса, но ничего не вышло

В сентябре 1973 года к команде присоединился новый математик. Клиффорд Кокс недавно окончил Кембриджский университет, где он специализировался в теории чисел, Когда он пришел в ШКПС, он почти ничего не знал ни о шифровании, ни о призрачном мире военных и дипломатических средств связи, так что ему был выделен наставник, Ник Паттерсон, который инструктировал и направлял его первые несколько недель в ШКПС. Примерно через шесть недель Паттерсон в общих чертах обрисовал теорию Эллиса относительно криптографии с открытым ключом и пояснил, что до сих пор никто не сумел отыскать требуемую математическую функцию. Паттерсон поделился с Коксом не потому, что ожидал от него, что тот попробует ее решить, а поскольку это была самая щекочущая нервы криптографическая идея. Однако в тот же день, чуть позже, Кокс принялся за эту работу. Поскольку Кокс работал в области теории чисел, было вполне естественно, что и думать он стал об односторонних функциях, с помощью которых вы можете что-то сделать, но вернуться обратно уже не удастся. Явными кандидатурами были простые числа и разложение на множители, и это стало его отправной точкой.

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

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

Несмотря на то что идея Кокса была одной из важнейших в ШКПС, она страдала от того, что время для нее еще не пришло. Кокс нашел математическую функцию, которая дала жизнь криптографии с открытым ключом, но по-прежнему оставалась сложность с реализацией данной системы. Для шифрования с использованием криптографии с открытым ключом требуются гораздо большие вычислительные мощности, чем для шифрования с использованием симметричного шифра, как, например, DES. Но в начале 70-х компьютеры были все еще сравнительно примитивными и не могли выполнять процесс шифрования с открытым ключом за приемлемое время. Так что ШКПС была не в состоянии использовать криптографию с открытым ключом. Кокс и Эллис доказали, что, казалось бы, невозможное было возможным, но никто не мог найти способ сделать возможное осуществимым.

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

Единственно, что тревожило Уильямсона, это то, что ШКПС не стала брать патент на криптографию с открытым ключом. Когда Кокс и Уильямсон совершали свои открытия, в руководстве ШКПС существовало мнение, что патентование невозможно по двум причинам. Во-первых, патентование Означало бы раскрытие деталей их работы, что противоречило бы целям ШКПС. Во-вторых, в начале 70-х годов было далеко не ясно, могут ли быть запатентованы математические алгоритмы. Однако когда Диффи и Хеллман в 1976 году попробовали подать заявку на патент, оказалось, что патентовать их можно. В этот момент у Уильямсона появилось огромное желание предать гласности свое открытие и заблокировать заявку Диффи и Хеллмана, но ему было отказано руководителями высокого ранга, которые не были достаточно дальновидны, чтобы разглядеть возникновение цифровой революции и возможностей криптографии с открытым ключом. К началу 80-х руководство Уильямсона начало уже раскаиваться в своем решении, поскольку усовершенствования в компьютерах и зарождающийся Интернет убедительно показали, что RSA и алгоритм обмена ключами Диффи-Хеллмана-Меркля оказались бы продуктами, имеющими огромный коммерческий успех.

Несмотря на то что работа в ШКПС оставалась по-прежнему секретной, существовала еще одна организация, которой было известно об открытиях, совершенных в Великобритании. К началу 80-х годов американское Агентство национальной безопасности знало о работе Эллиса, Кокса и Уильямсона, и возможно, что именно от АНБ до Уитфилда Диффи дошел слух об открытиях в Великобритании. В сентябре 1982 года Диффи решил проверить, насколько слухи истинны, и со своей женой отправился в Челтенхем, чтобы с глазу на глаз поговорить с Джеймсом Эллисом. Диффи и Эллис обсуждали различные темы, но каждый раз, как разговор начинал переходить на криптографию, Эллис мягко менял тему. В конце своего визита Диффи, поскольку он уже готовился уезжать и больше не мог выжидать, без обиняков спросил Эл­лиса: «Расскажите мне, как вам удалось открыть криптографию с от­крытым ключом?»Последовала длинная пауза. Наконец Эллис про­шептал: «Ну, я не знаю, сколько я могу рассказать. Позвольте мне только заметить, что вы сделали гораздо больше, чем мы».

И хотя криптографию с открытым ключом вначале нашли в ШКПС, не следует недооценивать достижения ученых, открывших ее «заново». Именно они первыми осознали возможности шифрования с открытым ключом, и именно они воплотили ее в жизнь. Более того, вполне возможно, что ШКПС никогда бы и не обнародовала их работу, воспрепятствовав тем самым появлению шифрования, которое позволит цифровой революции раскрыть все свои возможности. И наконец, открытие было сделано учеными совершенно независимо от открытия в ШКПС, а интеллектуально – наравне с нею. Засекреченная область закрытых исследований полностью обособлена от академической среды, и ученые академических институтов не имеют доступа к программным продуктам и секретным сведениям, которые могут быть скрыты от них в засекреченном мире.

С другой стороны, у исследователей, работающих в засекреченной области, всегда есть доступ к академическим изданиям. Можно представить себе этот поток информации как одно- стороннюю функцию: информация свободно движется в одном направлении, но в обратном направлении передавать информацию запрещено. Когда Диффи рассказывал Хеллману об Эллисе, Коксе и Уильямсоне, по его мнению, поступить надо было следующим образом: об открытиях ученых академических институтов следует указывать в виде примечания в историческом описании закрытых исследований, а об открытиях, сделанных в ШКПС, следует указывать в виде примечания в историческом описании академических исследований. Однако на данном этапе никто, кроме ШКПС, АНБ, Диффи и Хеллмана, не знал о закрытых исследованиях, и поэтому их не удалось бы дать даже в качестве ссылки.

К середине, 80-х настроение в ШКПС изменилось и ее руководство подумывало о том, чтобы открыто объявить о работе Эллиса, Кокса и Уильямсона. Математика криптографии с открытым ключом была уже в достаточной мере разработана в открытых исследованиях, и не было причин продолжать держать ее в секрете. Более того, если бы Великобритания обнародовала свою выдающуюся работу по криптографии с открытым ключом, это принесло бы очевидные выгоды. В 1997 году Клиффорд Кокс закончил имеющую важное значение несекретную работу по RSA, которая представляла интерес для широкой общественности, и которая, если бы ее опубликовали, не представляла угрозы системе безопасности. В результате его попросили представить статью на конференцию в Институт математики и ее приложений, которая должна была проводиться в Сиренчестере. Комната была переполнена экспертам и криптографами. Только некоторые из них знали, что Кокс, доклад которого будет посвящен только одному аспекту RSA, являлся на самом деле его невоспетым автором.

Существовал риск, что кто-нибудь мог задать ему неуместный вопрос, на­пример: «Это вы придумали RSA?» Если бы такой вопрос прозвучал, как должен был реагировать Кокс? Согласно политике ШКПС, ему следовало отрицать свое участие в разработке RSA и тем самым лгать в совершенно безобидном вопросе. Ситуация была совершенно смехотворной, и ШКПС решила, что настало время изменить свою политику. Коксу разрешили начать свой доклад с краткой предыстории о вкладе ШКПС в криптографию с открытым ключом. декабря 1997 года Кокс прочитал свой доклад. После почти трех десятилетий секретности Эллис, Кокс и Уильямсон получили заслуженное признание.