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

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

§ 12.1. О начале и конце

Чтобы реализовать систему шифрования RSA, предназначенную для одного пользователя, необходимо выбрать два различных простых числа р и q и вычислить их произведение Простые р и q хранятся в тайне, в то время как число становится частью открытого ключа. В § 12.5 мы подробно обсудим метод выбора простых составляющих ключа, а также то, как этот выбор связан с надежностью системы.

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

Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, — последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из следующей таблицы:

(см. скан)

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

Например, численное представление девиза «ПОЗНАЙ СЕБЯ» выглядит так:

Выбрав простые мы получим произведение Поэтому численное представление сообщения, выписанное выше, нужно разбить на блоки, меньшие чем 23 393. Приведем одно из таких разбиений.

Конечно, выбор блоков не однозначен, но и не совсем произволен. Например, во избежание двусмысленностей на стадии

расшифровки не следует выделять блоки, начинающиеся с нуля.

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

Обратите внимание на то, что каждая буква таблицы кодируется двузначным числом. Так делается для предотвращения путаницы. Предположим, мы пронумеровали буквы по порядку, начиная с 1, т.е. А соответствует 1, Б - 2, и так далее. В этом случае мы не сможем точно сказать, обозначает ли блок 12 пару букв или только одну букву двенадцатую букву алфавита. Конечно, для численного представления сообщения можно использовать любое однозначное соответствие между буквами и числами, например, -кодировку, при которой перевод сообщения в цифровую форму автоматически выполняется компьютером.

§ 12.2. Шифровка и дешифровка

Сообщение, подготовленное к шифровке по методу § 12.1, состоит из последовательности блоков, каждый из которых — число, меньшее, чем Теперь обсудим, как шифруется каждый блок. Для этого нам потребуется число равное произведению простых и натуральное число, обратимое по модулю т.е. число удовлетворяющее условию

Напомним, что по известным р и q число легко вычисляется. Действительно,

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

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

Вернемся к примеру, который начали рассматривать в первом параграфе. Мы зафиксировали так что Теперь нужно выбрать число Напомним, что оно должно быть взаимно простым с Наименьшее простое число, не делящее 23088, равно 5. Положим Чтобы закодировать первый блок сообщения из § 12.1, нам предстоит определить вычет числа 25245 по модулю 23 393. С помощью программы символьных вычислений (или калькулятора, если хватит терпения) мы получим, что искомый вычет равен 22 752. Итак, Все же зашифрованное сообщение представляется следующей последовательностью блоков:

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

получается в результате операции:

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

Наконец, как мы утверждали во введении и на протяжении всей книги, для взлома RSA-криптосистемы необходимо разложить на множители, потому что для дешифровки сообщения нужно знать Однако после того, как работа системы подробно описана, ясно, что последнее утверждение не совсем точно. Чтобы прочесть шифровку, кроме самого нужно знать только обратный к элемент по модулю Поэтому для взлома системы достаточно вычислить при известных Оказывается, это вычисление равносильно разложению числа на множители, как мы убедимся в § 12.4.

В обсуждаемом примере Для определения применим расширенный алгоритм Евклида к числам и 5.

(см. скан)

Таким образом, Следовательно, обратным к 5 по модулю будет —9235 и

— наименьшее натуральное число, сравнимое с —9235 по модулю Значит, для раскодирования блока шифрованного сообщения мы должны возвести его в степень 13 853 по модулю 23 393. В нашем примере первый закодированный блок — это 22 752. Вычисляя вычет числа 22 75213853 по модулю 23 393, получим Заметьте, что даже при таких малых числах требования, предъявляемые при работе RSA-криптосистемы, превышают возможности большинства карманных калькуляторов.

§ 12.3. Почему она работает?

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

На самом деле, достаточно доказать, что

Действительно, как 6, так и неотрицательные целые числа, меньшие Поэтому они сравнимы по модулю тогда и только тогда, когда они равны. Это, в частности, объясняет, почему мы разбиваем численное представление сообщения на блоки, меньшие Кроме того, отсюда видно, что блоки

закодированного сообщения необходимо записывать отдельно: в противном случае наши рассуждения не будут работать.

Из рецептов шифрования и дешифрования следует, что

Поскольку элементы взаимно обратны по модулю найдется такое натуральное к, что Более того, по условию, числа больше Следовательно, Подставляя вместо произведения в уравнение (3.1), получаем

Теперь воспользуемся теоремой Эйлера, которая утверждает, что Отсюда т. е.

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

Внимательно просмотрев еще раз наши рассуждения, Вы заметите, что мы не учитывали условий теоремы Эйлера. На самом деле, прежде чем применять теорему, необходимо убедиться во взаимной простоте чисел За этим, казалось бы, нужно следить при подготовке сообщения к шифровке, т.е. во время разбиения численного представления сообщения на блоки нужно добиваться уверенности в том, что все получающиеся блоки взаимно просты с К счастью, в этом нет необходимости, потому что на самом деле сравнение выполнено для любого блока. И ошибка кроется не в результате, который мы хотим доказать, а только лишь в самом доказательстве. Правильный подход основывается на рассуждениях, использованных при доказательстве теоремы Корселта в главе 7.

Напомним, что где различные простые числа. Определим вычеты числа по модулям Поскольку

вычисления для обоих простых чисел аналогичны, мы проработаем в деталях только случай Итак, мы уже убедились в том, что

для некоторого целого Следовательно,

Мы хотели бы теперь применить теорему Ферма, но имеем право сделать это, только если не делит Пусть это требование выполнено. Тогда и мы получаем, что

Заменив теорему Ферма теоремой Эйлера, мы не решили возникшей проблемы: сравнение справедливо только для некоторых, но не для всех блоков. Однако теперь блоки, для которых рассуждения не проходят, должны делиться на Далее, если делит то как 6, так и сравнимы с 0 по модулю а значит сравнимы между собой. Таким образом, доказываемое сравнение справедливо и в этом случае. Следовательно, сравнение истинно для любого целого числа Обратите внимание на то, что мы не. могли использовать подобное рассуждение, когда применяли теорему Эйлера к Действительно, неравенство не означает сравнения потому что число составное.

Итак, мы доказали, что Аналогично доказывается сравнение Другими словами, делится и на и на Но различные простые числа, так что Таким образом, лемма из § 3.6 гарантирует нам, что делит А так как мы имеем для любого целого числа Другими словами, Как мы отметили в начале параграфа, этого достаточно для доказательства равенства поскольку обе его части — неотрицательные целые числа, меньшие Подводя итог, можно утверждать, что

алгоритм предыдущего параграфа приводит к практической криптосистеме. Теперь нужно убедиться в ее надежности.

§ 12.4. Почему система надежна?

Напомним, что RSA - система шифрования с открытым ключом, состоящим из произведения различных простых чисел и натурального числа обратимого по модулю Посмотрим внимательно, что можно сделать для взлома RSA, если все, что известно, это пара

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

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

известны, то мы с легкостью вычисляем Действительно,

так что сумма искомых простых делителей известна. Далее,

поэтому разность тоже известна. Теперь, решая простую систему линейных уравнений, легко наг ходим разложение на множители.

Значит, алгоритм, вычисляющий фактически раскладывает число на множители, так что это одного поля ягодки. Но успокаиваться пока рано. Можно пойти дальше в своих фантазиях и предположить, что кто-то изобрел алгоритм, определяющий непосредственно по Но Так что, если нам известны то мы знаем число, кратное Оказывается, такой информации тоже достаточно для разложения Вероятностный алгоритм, приводящий к такому разложению, можно найти в [29]. В упражнении 7 приведен похожий (но более простой) алгоритм разложения в предположении, что криптосистему Рабина можно взломать. Он даст вам представление о вероятностном алгоритме из [29].

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

§ 12.5. Выбор простых

Из предыдущего обсуждения вытекает, что для безопасности RSA-криптосистемы важно правильно выбрать простые числа Естественно, если они малы, то система легко взламывается. Однако недостаточно выбрать большие Действительно, даже если р и q огромны, но разность мала, их произведение легко разлагается на множители с помощью алгоритма Ферма (см. § 3.4).

Это не праздный разговор. В 1995 году два студента одного американского университета взломали версию RSA, находящуюся в общественном пользовании. Такое стало возможным из-за плохого выбора простых множителей системы.

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

Предположим, мы хотим создать RSA-криптосистему с открытым ключом в котором целое число имеет около знаков. Сначала выберем простое число количество знаков которого лежит между возьмем близким к В настоящее время рекомендованный для персонального использования размер ключа равен 768 битам, т.е. должно приблизительно состоять из 231 цифры. Чтобы построить такое число, нам потребуются два простых, скажем, из 104 и 127 знаков. Обратите внимание на то, что выбранные таким образом простые достаточно далеки друг от друга, т.е. применение алгоритма Ферма для разложения в этой ситуации непрактично. Кроме того, нам нужно удостовериться в том, что в разложении чисел на простые множители участвуют не только малые делители, но и большие. Действительно, в противном случае, число становится легкой добычей для некоторых известных алгоритмов разложения (см. [43]). Рассмотрим теперь метод, с помощью которого находят простые числа, удовлетворяющие перечисленным условиям.

Сначала нам потребуется один простой результат о распределении простых чисел. Напомним, что обозначает количество простых, не превосходящих х. Учитывая теорему о простых числах, мы видим, что для больших х число приблизительно равно где натуральный логарифм

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

Предполагая, что очень мало, мы можем считать значение равным 0 и получить разумную оценку разности Итак, число простых, заключенных между приблизительно равно Естественно, оценка тем точнее, чем больше х и меньше Для более подробного знакомства с такой оценкой см. [23] ([Д.10]).

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

простых числа. В конце второго параграфа главы 11 мы сформулировали стратегию, предназначенную для доказательства простоты данного нечетного числа Она состоит из трех шагов:

(1) проверяем, делится ли на какое-нибудь простое число, не превосходящее 5000;

(2) если не делится ни на одно из них, то применяем к нему тест Миллера, используя в качестве оснований первые 20 простых чисел;

(3) если тест Миллера по всем этим основаниям дает неопределенный ответ, то подвергаем тесту на простоту из § 11.2.

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

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

Пусть положительное целое число. Если

Таким образом, в интервале ] существует

чисел, кратных Найденное число, приблизительно равное совпадает с количеством положительных чисел, кратных и не превосходящих 104. Это позволяет нам заключить, что в интервалах и [0,104] находится почти одинаковое количество чисел, делящихся на какое-нибудь простое число, не превышающее 5000. Последнее из них вычисляется без особого труда. Прежде всего заметим, что составное число, лежащее между 0 и 104, должно быть кратно простому, меньшему, чем Таким образом, целое число в интервале кратно какому-то простому числу, меньшему чем 5000, если оно либо совпадает с этим простым числом, либо

является составным. Учитывая, что 2 — единственное четное простое число, мы получаем, что количество нечетных составных чисел, не превосходящих 104, равно Следовательно, все количество нечетных составных чисел, оставшихся в интервале после завершения первого шага нашей стратегии, приблизительно равно

Отметим, что значения легко вычисляются с помощью решета Эратосфена.

Итак, в данном интервале можно надеяться отыскать около 34 простых чисел среди всего 560 целых, оставшихся после отсеивания заведомо составных.

§ 12.6. Проблема подписи

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

Метод, которым подписывают электронное сообщение, весьма прост и работает для любого открытого ключа криптосистемы. Пусть компания использует в качестве функций кодирования и раскодирования, а соответствующие функции банка. Рассмотрим блок а сообщения, которое компания собирается послать банку. Мы видели, что для

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

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

Почему такой подписи достаточно для уверенности в том, что сообщение пришло именно из компании, а не откуда-нибудь извне? Банк должен подвергнуть полученное сообщение последовательности преобразований

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

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

У вышеупомянутого метода имеется один маленький недостаток. Пусть открытый ключ компании, а ключ банка. Мы помним, что закодированный блок начального сообщения должен удовлетворять неравенству Предположим, теперь, что В этом случае у нас нет никакого способа узнать заранее, будет ли меньшим,

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

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

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)