Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Иными словами, «возведение в степень 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 лишь один из множества шифров, основанных на теории чисел или ее близком родиче, комбинаторике, то есть методе подсчета числа способов, посредством которых может быть получена определенная комбинация, без перечисления всех этих способов. Если хотите убедиться в том, что математический источник идей в сфере криптографии еще не пересох, то посмотрите на альтернативную систему шифрования, которая использует одну из наиболее глубоких и интересных областей сегодняшней теории чисел. Эта область исследует эллиптические кривые, которые, наряду с другими вещами, стали основой для доказательства Великой теоремы Ферма, предложенного Эндрю Уайлсом.
Со времен Ферма теория чисел серьезно продвинулась вперед. То же произошло и с алгеброй, где акцент сместился с символьного
