Кокс и Ривест – Шамир – Адлеман выводили свои правила из красивой теоремы, открытой Ферма в 1640 году, которая показывает, как ведут себя степени чисел в модулярной арифметике. Говоря современным языком, Ферма рассказал своему другу де Бесси, что если n – простое число, то
an = a (mod n) или, что эквивалентно, an-1= 1 (mod n)
для любого числа a. «Я продемонстрировал бы тебе это, если бы не боялся, что получится слишком длинно», – писал Ферма. Эйлер получил недостающее доказательство в 1736 году, а в 1763 году он опубликовал более общую теорему, которая применима, если модуль не является простым числом. Теперь a и n не должны иметь общий делитель, а степень n – 1 во втором варианте формулы заменена на функцию Эйлера φ(n). Нам нет нужды знать, что это такое{42}, но необходимо понимать, что если n = pq есть произведение двух простых чисел p и q, то φ(n) = (p – 1)(q – 1).
Криптосистема RSA действует следующим образом:
• Найдите два больших простых числа p и q.
• Вычислите произведение n = pq.
• Вычислите φ(n) = (p – 1)(q – 1). Держите это в секрете.
• Выберите число e, не имеющее общих простых делителей с φ(n).
• Вычислите d так, чтобы de = 1 (mod φ(n)).
• Число e можно раскрыть. (Кстати говоря, это дает очень мало полезной информации о φ(n).)
• Сохраните d в секрете. (Это принципиально важно.)
• Пусть r – текстовое сообщение, зашифрованное как число по модулю n.
• Конвертируйте r в зашифрованный текст re (mod n). (Правило шифрования также можно раскрыть.)
• Чтобы расшифровать re, следует возвести его в степень d (mod n). (Не забываем, что d секретно.) Это дает (re)d, что равно red, что равно r по теореме Эйлера.
Здесь правило шифрования звучит как «возвести в e-ю степень»:
r → re,
а правило расшифровки как «возвести в d-ю степень»:
s → sd.
Кое-какие математические фокусы, в которые я не буду вдаваться, дают возможность производить все эти действия быстро (на современных компьютерах) при условии, что вам известны p и q по отдельности. Самое неприятное – то, что если они вам неизвестны, то знание n и e не сильно помогает в вычислении d, необходимого для расшифровки сообщения. По существу, вам нужно найти простые делители p и q числа n, что, как мы видели (судя по всему), намного труднее, чем перемножить p и q и найти таким образом n.
Иными словами, «возведение в степень e» и есть требуемая функция с потайным входом.
В настоящее время все вышеописанное может быть проделано за минуту или около того на обычном ноутбуке для, скажем, 100-значных простых чисел p и q. Одна из приятных особенностей системы RSA состоит в том, что по мере того, как компьютеры становятся более мощными, достаточно всего лишь увеличивать p и q. Метод по-прежнему будет работать.
Один из недостатков системы – то, что RSA, будучи полностью реализуемой и практичной, все же слишком медленна, чтобы рутинно использовать ее для шифрования полного текста каждого сообщения. Основное ее реальное применение – это безопасная передача секретного ключа для какой-то совершенно иной системы шифрования, гораздо более быстрой в использовании и надежной при условии, что ключ никому не известен. Так что RSA решает проблему раздачи ключей, которая мучила криптографию с начала времен. Одним из факторов, позволивших расшифровать код Enigma, было то, что определенные установки машины Enigma передавались операторам в начале каждого дня небезопасным способом. Еще одно распространенное применение системы RSA – проверка электронной подписи, то есть шифрованного сообщения, устанавливающего личность отправителя.
Начальник Кокса Ральф Бенджамин, научный руководитель, главный инженер и директор Центра правительственной связи, прекрасно знал свое дело и сразу обратил внимание на эту возможность. Он написал в рапорте: «Я считаю ее очень важной для военного применения. В быстро меняющейся военной ситуации можно встретить непредвиденные угрозы или возможности. Тот, кто может раздавать свой ключ быстро при помощи электронных средств связи, получает серьезное преимущество перед противником». Но компьютеры тех времен не могли выполнить эту задачу, и британское правительство упустило, как позже оказалось, громадные возможности.
Математические методы редко оказываются пригодными для решения практических задач, что называется, в готовом виде. Как и все остальное, их, как правило, приходится адаптировать и приспосабливать, чтобы преодолеть возникающие трудности. Это относится и к системе RSA: она все же не так проста, как я здесь описал. На самом деле, стоит прекратить восхищаться идеей и задуматься, что может пойти не так, как на поверхность вылезает множество интереснейших теоретических вопросов для математиков.
Несложно показать, что вычислить φ(n), не зная его простых множителей p и q, так же трудно, как и найти сами p и q. Мало того, их нахождение представляется единственным способом сделать это. Так что главный вопрос состоит в следующем: насколько трудна факторизация, то есть разложение на простые сомножители? Большинство математиков считает эту задачу чрезвычайно трудной в техническом смысле: время выполнения любого алгоритма разложения на простые множители с ростом числа знаков в произведении pq растет взрывным образом. (Кстати говоря, причина использования именно двух простых чисел, а, скажем, не трех, кроется в наибольшей сложности этого варианта. Чем больше простых сомножителей имеет число, тем проще найти один из них. Разделите на него, и число станет заметно меньше, а найти остальные сомножители будет проще.) Однако никто в настоящее время не может доказать, что разложение на простые множители – трудная задача. Никто не знает, с какой стороны подойти к поиску такого доказательства. Так что надежность метода RSA зиждется на недоказанной гипотезе.
Остальные вопросы и подводные камни касаются тонкостей метода. Неудачный выбор используемых чисел может сделать RSA уязвимой для особенно хитроумных атак. Например, если e слишком мало, то мы можем определить сообщение r, вычислив корень e-й степени из зашифрованного текста re как из обычного числа, то есть не по модулю n. Еще одна потенциальная уязвимость возникает, если одно и то же сообщение рассылается e получателям с использованием одной и той же степени e, даже если p и q для каждого из них свои. В этом случае может быть применено красивое утверждение, известное как китайская теорема об остатках, которое позволит раскрыть текст сообщения.
Говорят также, что метод RSA семантически небезопасен. Это означает, что, в принципе, он может быть взломан, если зашифровать с его помощью множество разных сообщений и попытаться сопоставить полученные результаты с шифрованным текстом, который нужно взломать. По существу, это метод проб и ошибок. Для длинных сообщений это, возможно, непрактично, но если рассылается множество коротких посланий, то такой метод дешифровки может сработать. Чтобы избежать этого, RSA модифицируют добавлением к сообщению лишних цифр по какой-то конкретной, но случайной схеме. Это делает текст длиннее и позволяет избежать многократной отправки одного и того же сообщения.
Еще при одном методе взлома шифров RSA используется не математический недостаток метода, а физическая особенность компьютера. В 1995 году криптограф и предприниматель Пол Кохер заметил, что если криптоаналитик хорошо знает используемое оборудование и может измерить, сколько времени уходит на дешифровку нескольких сообщений, то он может легко установить секретный ключ d. В 2003 году Дэн Боне и Дэвид Брамли продемонстрировали практический вариант такой атаки на примере сообщений, отправленных по традиционной сети с использованием стандартного протокола SSL (Secure Sockets Layer).
Существование математических методов, которые иногда способны очень быстро разложить на простые множители большое число, подразумевает, что простые числа p и q должны выбираться так, чтобы они удовлетворяли некоторым ограничениям. Они не должны быть слишком близкими, иначе можно будет применить известный метод, восходящий еще к Ферма. В 2012 году группа под руководством Арьена Ленстры опробовала этот метод на миллионах открытых ключей, извлеченных из интернета, и смогла взломать каждый 500-й из них.
Очень серьезно изменило бы ситуацию появление реального рабочего квантового компьютера. Эти машины, не вышедшие еще из младенческого состояния, вместо обычных двоичных цифр 0 и 1 используют квантовые биты и в принципе могут производить гигантские расчеты, такие как разложение на простые множители громадных чисел, с беспрецедентной скоростью. Я немного отложу рассказ о них.
Система RSA лишь один из множества шифров, основанных на теории чисел или ее близком родиче, комбинаторике, то есть методе подсчета числа способов, посредством которых может быть получена определенная комбинация, без перечисления всех этих способов. Если хотите убедиться в том, что математический источник идей в сфере криптографии еще не пересох, то посмотрите на альтернативную систему шифрования, которая использует одну из наиболее глубоких и интересных областей сегодняшней теории чисел. Эта область исследует эллиптические кривые, которые, наряду с другими вещами, стали основой для доказательства Великой теоремы Ферма, предложенного Эндрю Уайлсом.