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

Next: 4.3. Сложность теоретико-числовых алгоритмов Up: 4. Алгоритмические проблемы теории Previous: 4.1. Введение Contents: Содержание

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

В дальнейшем мы будем предполагать, что читатель знаком с элементарными фактами теории чисел. Тех же, кто хотел бы ознакомиться с ними или напомнить себе эти факты, мы отсылаем к книге [3].

Пусть и натуральные числа. Функция , реализующая схему RSA, устроена следующим образом

$\begin{displaymath} f\colon x\mapsto x^e\mod{m}. \end{displaymath}$ (1)

Для дешифрования сообщения

достаточно решить сравнение

$\begin{displaymath} x^e\equiv a\pmod m. \end{displaymath}$

(2)

При некоторых условиях на

это сравнение имеет единственное решение

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента обозначается $\phi(m)$ и равняется количеству целых чисел на отрезке от до , взаимно простых с . Так $\phi(1)=1$ и $\phi(p^r)=p^{r-1}(p-1)$ для любого простого числа и натурального . Кроме того, $\phi(ab)=\phi(a)\phi(b)$ для любых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение $\phi(m)$ , если известно разложение числа на простые сомножители.

Если показатель степени в сравнении (2) взаимно прост с $\phi(m)$ , то сравнение (2) имеет единственное решение. Для того, чтобы найти его, определим целое число , удовлетворяющее условиям

$\begin{displaymath} de \equiv 1\pmod{\phi(m)}, \quad 1\leq d < \phi(m). \end{displaymath}$ (3)

Такое число существует, поскольку $(e,\phi(m))=1$ , и притом единственно. Здесь и далее символом

будет обозначаться наибольший общий делитель чисел

. Классическая теорема Эйлера, см. [3], утверждает, что для каждого числа

, взаимно простого с

, выполняется сравнение $x^{\phi(m)}\equiv1\pmod m$ и, следовательно,

$\begin{displaymath} a^d\equiv x^{de}\equiv x \pmod m. \end{displaymath}$

(4)

Таким образом, в предположении

, единственное решение сравнения (2) может быть найдено в виде

$\begin{displaymath} x\equiv a^d\pmod m. \end{displaymath}$

(5)

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Действительно, обозначим и . Тогда $\phi(m)$ делится на $\phi(s)$ , а из (2) следует, что . Подобно (4), теперь легко находим $x\equiv a^d\pmod s$ . А кроме того, имеем $x\equiv 0\equiv a^d \pmod r$ . Получившиеся сравнения в силу дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к функция $f^{-1}\colon x\mapsto x^d\pmod m$ вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства а) и б).

Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число , оно и является ``секретом'' , о котором речь идет в пункте в). Казалось бы, ничего не стоит, зная число , разложить его на простые сомножители, вычислить затем с помощью известных правил значение $\phi(m)$ и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю ее историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до $\sqrt{m}$ , и, деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно $2\sqrt{m}\cdot(\ln m)^{-1}$ , см. [4, гл. 5], находим, что при , записываемом 100 десятичными цифрами, найдется не менее $4\cdot10^{42}$ простых чисел, на которые придется делить при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа $m>10^{99}$ таким способом на простые сомножители потребуется не менее, чем $10^{35}$ лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно. Таким образом, название статьи М. Гарднера вполне оправдано.

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

$\begin{displaymath} \phi(m)=\phi(pq)=(p-1)(q-1), \end{displaymath}$ (6)

то единственное условие на выбор показателя степени

в отображении (1) есть

$\begin{displaymath} (e,p-1)=(e,q-1)=1. \end{displaymath}$

(7)

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число $\phi(m)$ и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (3) сообщения организатору этой системы, а организатор легко сможет дешифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (a=01, b=02, ..., z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения (1) при
$\begin{align*} m=&11438162575788886766932577997614661201021829672124236256256184... ... &5706935245733897830597123563958705058989075147599290026879543541 \end{align*}$
и . Эти два числа были опубликованы, причем дополнительно сообщалось, что , где и - простые числа, записываемые соответственно и десятичными знаками. Первому, кто дешифрует соответствующее сообщение
$\begin{align*} f(x)=&96869613754622061477140922254355882905759991124574319874695... ...&0816298225145708356931476622883989628013391990551829945157815154, \end{align*}$

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., см. [5], когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной в [1]. Она1) была вынесена в заголовок статьи [5], а соответствующие числа и оказались равными
$\begin{align*} p=&34905295108476509491478496199038981334177646384933878439908205... ...32769132993266709549961988190834461413177642967992942539798288533. \end{align*}$

Интересующиеся могут найти детали вычислений в работе [5]. Здесь же мы отметим, что этот замечательный результат (разложение на множители 129-значного десятичного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединенных сетью Internet. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

Описанная выше схема RSA ставит ряд вопросов, которые мы и попробуем обсудить ниже. Например, как проводить вычисления с большими числами, ведь стандартное математическое обеспечение не позволяет перемножать числа размером по 65 десятичных знаков? Как вычислять огромные степени больших чисел? Что значит быстрый алгоритм вычисления и что такое сложная вычислительная задача? Где взять большие простые числа? Как, например, построить простое число в 65 десятичных знаков? Существуют ли другие способы решения сравнения (2)? Ведь, если можно найти решение (2), не вычисляя секретный показатель или не разлагая число на простые сомножители, да еще сделать это достаточно быстро, вся система RSA разваливается. Наверное, читателю могут прийти в голову и другие вопросы.

Начнем с конца. За 17 лет, прошедших между публикациями работ [1] и [5], никто так и не смог дешифровать предложенную авторами RSA фразу. Конечно, это всего лишь косвенное подтверждение стойкости системы RSA, но все же достаточно убедительное. Ниже мы обсудим теоретические проблемы, возникающие при решении полиномиальных сравнений.

Мы не будем обсуждать, как выполнять арифметические действия с большими целыми числами, рекомендуем читателю обратиться к замечательной книжке Д. Кнута [6, гл. 4]. Заметим только, что большое число всегда можно разбить на меньшие блоки, с которыми компьютер может оперировать так же, как мы оперируем с цифрами, когда проводим вычисления вручную на бумаге. Конечно, для этого нужны специальные программы. Созданы и получили достаточно широкое распространение даже специальные языки программирования для вычислений с большими числами. Укажем здесь два из них - PARI и UBASIC. Эти языки свободно распространяются. Информацию о том, как их получить в пользование, можно найти в книге [17].