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

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

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

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

На следующее утро Ривест передал статью Адлеману, который, как обычно, постарался ее растерзать, но на сей раз он не смог найти ни одной ошибки. Единственно, он раскритиковал список авторов.

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

Перед тем как познакомиться с идеей Ривеста, напомним, что же искали ученые для создания асимметричного шифра:

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

(2) Алисе, однако, необходимо расшифровывать присланные ей сообщения. Поэтому у нее должен иметься секретный ключ — некоторое количество специальной информации, которая позволит ей обратить действие открытого ключа. Тем самым Алиса (и лишь она одна) сумеет расшифровать все присланные ей сообщения.

_{Рис. 65 Рональд Ривест, Ади Шамир и Леонард Адлеман.}

Душой асимметричного шифра Ривеста является односторонняя функция, основанная на модулярной функции, описанной ранее в этой главе. Односторонняя функция Ривеста может применяться для зашифровывания сообщения; к сообщению, которое в нашем случает является числом, применяется функция, и в результате получается шифртекст — другое число. Я не буду подробно описывать одностороннюю функцию Ривеста (для этого см. Приложение J) один особый аспект, известный просто как N, поскольку именно N делает при определенных обстоятельствах одностороннюю функцию обратимой и, тем самым, идеальной для применения в качестве асимметричного шифра.

N важно, поскольку оно представляет собой изменяющийся элемент односторонней функции, благодаря чему каждый человек может выбирать различные значения N, образуя всякий раз различные односторонние функции. Чтобы выбрать свое собственное значение N, Алиса берет два простых числа, р и q перемножает их. Простое число — это число, у которого нет других делителей, кроме самого себя и 1. Например, 7 — это простое число, т. к. оно не делится без остатка ни на какое другое число, кроме 1 и 7. Точно так же и 13 — простое число, т. к. оно тоже не делится без остатка ни на какое другое число, кроме 1 и 13. А вот 8 уже является не простым, а составным числом, поскольку может делиться на 2 и на 4.

Итак, Алиса может выбрать свои простые числа, например, р = 17 159 и q = 10 247. Перемножая эти два числа, она получает 17 159 x 10 247 = 175 828 273. Полученное Алисой N фактически будет ее открытым ключом для зашифровывания, и она может напечатать его на своей визитной карточке, разместить в Интернете или опубликовать в справочнике открытых ключей вместе со значениями N других людей. Если Боб захочет зашифровать сообщение для Алисы, он отыскивает ее значение N (175 828 273), а затем вставляет его в одностороннюю функцию общего вида, которая также известна всем. Теперь у Боба есть односторонняя функция, сшитая с открытым ключом Алисы, поэтому ее можно назвать односторонней функцией Алисы. Чтобы зашифровать сообщение для Алисы, он берет одностороннюю функцию Алисы, вставляет сообщение, выписывает результат и отправляет его Алисе.

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

Мы можем рассматривать N как открытый ключ — информация, которая доступна всем и каждому и необходимая для того, чтобы зашифровывать сообщения для Алисы. Тогда как p и q являются секретным ключом, доступным только Алисе, — информация, необходимая для расшифровывания этих сообщений.

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

Алиса образовала N, выбрав p и q затем перемножив их вместе. Основной момент здесь заключается в том, что это по своей сути односторонняя функция. Чтобы продемонстрировать односторонний характер умножения простых чисел, мы можем взять два простых числа, например, 9419 и 1933, и перемножить их. Используя калькулятор, нам понадобится всего лишь несколько секунд, чтобы получить ответ 18 206 927. Однако, если вместо этого нам дадут число 18 206 927 и попросят найти простые множители (два числа, которые перемножили, чтобы получить 18 206 927), это займет у нас гораздо больше времени. Если вы сомневаетесь в том, насколько трудно находить простые множители, то примите во внимание следующее. Мне понадобилось лишь десять секунд, чтобы образовать число 1 709 023, но у вас с калькулятором в руках, чтобы найти простые множители, это займет добрую часть дня.

Считается, что данная система асимметричной криптографии, известная как RSA, является одним из видов шифрования с открытым ключом. Чтобы понять, насколько надежна RSA, мы можем проверить ее с точки зрения Евы и попробовать прочесть сообщение, посланное Алисой Бобу. Для того чтобы зашифровать сообщение для Боба, Алиса должна отыскать его открытый ключ. Для создания своего открытого ключа Боб берет выбранные им самим простые числа, р_B и q_B, и перемножает их, получая N_B. Он хранит р_B и q_B в секрете, ибо они составляют его секретный ключ для дешифровывания, но при этом публикует N_V, которое равно 408 508 091. Так что Алиса подставляет открытый ключ Боба N_B в общую одностороннюю функцию шифрования, а затем зашифровывает свое сообщение ему. Когда приходит зашифрованное сообщение, Боб может обратить функцию и расшифровать его, используя значения p_в и q_B, которые составляют его секретный ключ. Между тем Ева сумела во время передачи сообщения перехватить его. Ее единственная надежда расшифровать сообщение — обратить одностороннюю функцию, а это возможно только в том случае, если она знает р_B и q_B. Боб держит рv и qv в секрете, но, как и всем остальным, Еве известно N_B, равное 408 508 091. Далее Ева пытается найти значения р_B и q_B путем подбора чисел, которые при перемножении дают 408 508 091 — процесс, известный как разложение на множители.

Операция разложения на множители отнимает очень много времени, но сколько же на самом деле понадобится Еве времени, чтобы найти сомножители числа 408 508 091? Существуют различные способы разложения на множители числа N_B. Хотя одни из них быстрее, а другие — медленнее, но, по сути, во всех них проверяется, делится ли N_B без остатка на каждое из простых чисел. Например, 3 — это простое число, но оно не является множителем числа 408 508 091, так как 408 508 091 нацело на 3 не делится. Поэтому Ева берет следующее простое число — 5. 5 точно так же не является множителем, поэтому Ева переходит к следующему простому числу и так далее. В конце концов, Ева добирается до числа 18 313, 2000-го простого числа, которое является множителем числа 408 508 091. Найдя один из сомножителей, легко найти и другой — 22 307. Если у Евы есть калькулятор и она способна проверять четыре простых числа в минуту, то ей, чтобы отыскать p_B и q_B, потребуется 500 минут, или свыше 8 часов. Другими словами, Ева сможет раскрыть секретный ключ Боба и, тем самым, расшифровать перехваченное сообщение менее, чем за день.

Это не слишком-то высокий уровень стойкости, но Боб мог бы выбрать гораздо большие простые числа и повысить стойкость своего секретного ключа. Например, он мог бы выбрать простые числа, состоящие из 10⁶⁵ цифр (это означает 1 с 65 нулями, или сто тысяч миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов). В результате величина N будет приблизительно составлять 10⁶⁵ x 10⁶⁵, то есть 10¹³⁰ цифр. Компьютер смог бы перемножить оба простых числа и вычислить N всего лишь за секунду, но если Ева захочет выполнить обратную операцию и определить p и q, на это потребуется не в пример больше времени. Насколько больше, зависит от быстродействия компьютера Евы. По оценке эксперта по безопасности Симеона Гарфинкеля, 100-MHz компьютеру Intel Pentium с 8 MB RAM, чтобы разложить на множители число, состоящее из 10¹³⁰ цифр потребуется около 50 лет. Криптографы проявляют тенденцию к параноидальности и учитывают при определении стойкости своих шифров наихудшие ситуации, как, например, глобальная секретность. Поэтому Гарфинкель рассматривал, что произойдет, если объединить вместе сотню миллионов персональных компьютеров (количество компьютеров, проданных в 1995 году). В результате он получил, что число, состоящее из 10¹³⁰ цифр, может быть разложено на множители примерно за 15 секунд. Так что в настоящее время общепринято, что для обеспечения подлинной стойкости необходимо использовать еще большие простые числа. Для ответственных банковских операций N стремятся сделать как минимум 10³⁰⁸, которое в десять миллионов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов раз больше, чем 10¹³⁰. Объединенными усилиями сотне миллионов персональных компьютеров потребуется затратить более тысячи лет, чтобы раскрыть такой шифр. При достаточно больших значениях p и q, RSA является неуязвимой.

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

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

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

Об RSA впервые было объявлено в августе 1977 года, когда Мартин Гарднер написал статью, озаглавленную «Новый вид шифра, для взлома которого потребуются миллионы лет», для колонки «Математические игры» в «Сайентифик Америкен». Объяснив, как происходит шифрование с открытым ключом, Гарднер задал задачу своим читателям. Он напечатал зашифрованное сообщение и дал открытый ключ, который использовал для его зашифровывания:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

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

Что касается задачи Гарднера, то для ее решения потребовалось 17 лет. 26 апреля 1994 года команда из шестисот добровольцев сообщила о том, какие сомножители были у N:

q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577

p = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533.

Используя эти значения в качестве секретного ключа, они смогли расшифровать сообщение. Сообщение состояло из ряда чисел, но, преобразованное в буквы, гласило: «Волшебные слова: брезгливая скопа». Задача разложения на множители была распределена между добровольцами, проживающими в Австралии, Англии, США и Венесуэле. Они использовали свободное время своих рабочих станций, больших ЭВМ и суперкомпьютеров; при этом каждый занимался только частью задачи. По сути, чтобы решить задачу Гарднера, компьютеры, разбросанные по всему миру, объединялись в сеть и работали одновременно. Даже принимая во внимание огромную работу, которая велась параллельно, некоторые читатели могут удивиться, что RSA была взломана за такое короткое время, но следует заметить, что в задаче Гарднера использовалось относительно малое значение N; оно составляло порядка 10¹²⁹. Сегодня, чтобы обеспечить безопасность жизненно важной информации, пользователи RSA могут брать гораздо большие значения. Ныне вполне обычное дело зашифровывать сообщение с использованием такого большого N, что всем компьютерам в мире, чтобы взломать шифр, потребуется время, превышающее возраст Вселенной.