§ 1.2. Система шифрования RSA

Из систем кодирования с открытым ключом лучше всего известна и наиболее широко распространена система RSA. Ее изобрели в 1978 году Ривест, Шамир и Адлеман из МТИ ([1]). Подробное описание этой системы будет дано только в последней главе — оно опирается на идеи и методы, которые излагаются на протяжении всей книги. Следует, однако, немного представить себе причины, по которым знание системы кодирования RSA не позволяет немедленно вывести процедуру декодирования. Здесь мы сталкиваемся с примером ловушки, упомянутой в конце предыдущего параграфа.

Предположим, что мы хотим установить систему RSA для какого-то пользователя. Основными составляющими системы служат два нечетных простых числа, скажем Обозначим через произведение этих чисел, Открытый, или кодирующий, ключ этого пользователя системы RSA - число (и еще одно число, которое нам пока не требуется). Секретный, или декодирующий, ключ состоит, по существу, из чисел Таким образом, у каждого пользователя есть персональная пара простых чисел, которую нужно держать в тайне. Однако произведение этих простых чисел общедоступно. Поэтому если банк использует RSA, то любой желающий может послать ему закодированное сообщение, поскольку ключ кодирования известен всем.

Почему же тогда систему RSA трудно взломать? Ведь для нахождения р и q всего-то и надо, что разложить на

множители число Однако, если каждое из простых чисел содержит больше 100 цифр, то время и ресурсы, необходимые для разложения числа на множители, таковы, что взламывание кода становится очень трудным. Таким образом, ловушка в системе RSA заключается в том, что умножение чисел р и q для получения числа простая операция, тогда как обратная задача — разложение числа на множители для получения практически неразрешима. Другими словами, мы очень хорошо понимаем, как взломать RSA, однако на практике взлом не реализуем. Не следует забывать, однако, что препятствие носит чисто технологический характер: можно представить себе, что в один прекрасный день развитие компьютеров или изобретение лучших способов разложения на множители сделают систему RSA устаревшей. Драматическое подтверждение этому было получено при взломе системы RSA-129. Это тестовое сообщение было зашифровано создателями RSA в 1977 году; его название объясняется тем, что в кодирующем ключе было 129 цифр. Было подсчитано, что его расшифровка доступными методами займет не менее лет. В 1986 году -значное число было разложено на множители с использованием новой элементной базы компьютеров и возможностей Интернета. Разложение потребовало восьми месяцев работы, на протяжении которых были использованы компьютеры 600 добровольцев из стран. Каждый из компьютеров работал над маленьким кусочком задачи в свободное от других заданий время. Затем все результаты были сведены воедино с использованием суперкомпьютера. Достижения в этой области были настолько стремительны, что разложение большего числа RSA-130 потребовало в 1996 году лишь 15 процентов машинного времени, затраченного на RSA-129.

Подводя итог предыдущему обсуждению, мы заключаем, что

1) для реализации системы RSA необходимо иметь два больших простых числа

2) для кодирования сообщений с помощью RSA мы пользуемся числом

3) для декодирования шифровки RSA мы должны знать числа

4) безопасность системы RSA определяется тем, что разложить число на множители трудно, поскольку они очень велики.

После того, как мы, наконец, вплотную познакомимся с RSA в главе 12, мы поймем, что хотя приведенные утверждения и не вполне точны, они отражают все основные особенности системы.

Не обратили ли Вы внимание на то, что утверждения (3) и (4) противоречат друг другу? И вправду, безопасность системы RSA опирается на трудность разложения числа на простые множители. Число трудно разложить на множители, поскольку оно очень велико. Однако число является большим, только если р и q велики, и мы должны доказать, что эти большие числа простые, т.е. они делятся только сами на себя и на 1. Таким образом, для доказательства простоты числа необходимо применить к нему процедуру разложения на множители и убедиться, что у него нет множителей, отличных от Но не натыкаемся ли мы тут на то же самое препятствие, что и в случае с Если алгоритм разложения на множители работает слишком долго в случае не будет ли то же самое справедливо и для

Так и есть, однако это не означает, что у нас нет других способов доказать простоту большого числа. Мы просто доказываем простоту, не раскладывая число на множители. Имеются методы проверки числа на простоту и разложимость, даже не пытающиеся искать разложение. Так, мы знаем, что число 22 4-1 — составное, однако ни один из его сомножителей не известен. Ничего удивительного здесь нет, так как в указанном числе 4993 цифры. Косвенные методы проверки

чисел на простоту и разложимость обсуждаются в седьмой и одиннадцатой главах.

Предыдущее обсуждение показывает, что для того, чтобы объяснить систему шифрования RSA и реализовать ее, нужно хорошо знать свойства целых чисел. Особенно тесно связаны с ней два вопроса:

• как эффективно раскладывать данное целое число на множители?

• как доказывать, что данное целое число простое?

Как мы уже видели, ответ на второй вопрос, хотя он и близко связан с первым, не вытекает непосредственно из ответа на первый вопрос. Область математики, занимающаяся изучением свойств целых чисел, называется теорией чисел. Это одна из старейших отраслей математической науки, а упомянутые выше вопросы принадлежат к числу наиболее ранних проблем в теории чисел, рассматривавшихся человечеством.

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