Основные теоретические положения

Чтобы реализовать систему шифрования RSA, предназначенную для одного пользователя, необходимо выбрать два различных простых числа p и q и вычислить их произведение n = p•q. Простые числа p и q должны держаться в секрете, в то время как число n становится частью открытого ключа.

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

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

Таблица 1 — Соответствие букв алфавита и двухразрядных десятичных чисел.

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

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

Выбрав простые p = 149 и q = 157, мы получим произведение n = 23 393. Поэтому численное представление сообщения, выписанное выше, нужно разбить на блоки, меньшие, чем 23 393.

Приведем одно из таких разбиений.

2524 — 1723 — 10 199 — 9271 — 511 — 41.

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

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

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

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

НОД (e, ц (n)) = 1.

Напомним, что по известным р и q число ц (n) легко вычисляется. Действительно, ц (n) = (p -1) • (q — 1).

Пара (n, e) называется открытым ключом криптосистемы RSA, которую мы описываем. Пусть b — блок сообщения, то есть целое число, удовлетворяющее неравенству 0? b? n — 1. Символом Е (b) мы будем обозначать блок зашифрованного сообщения, соответствующий b. Он вычисляется по следующему правилу:

Е (b) = вычет be по модулю n.

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

Вернемся к примеру, который начали рассматривать в первом параграфе. Мы зафиксировали р = 149 и q = 157, так что п = 23 393 и ц (n) = 23 088. Теперь нужно выбрать число е. Напомним, что оно должно быть взаимно простым с ц (n). Наименьшее простое число, не делящее 23 088, равно 5. Положим е = 5. Чтобы закодировать первый блок сообщения, нам предстоит определить вычет числа 25 245 по модулю 23 393. С помощью программы символьных вычислений (или калькулятора, если хватит терпения) мы получим, что искомый вычет равен 22 752. Итак, Е (2524) = 22 752. Все же зашифрованное сообщение представляется следующей последовательностью блоков:

22 752 — 6198 — 14 204 — 23 191 — 10 723 — 14 065.

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

D (a) = вычет ad по модулю n.

Прежде чем вернуться к примеру, необходимо дать некоторые комментарии. Во-первых, вычислить d очень легко, если знать ц (n) и е. Действительно, секретный ключ определяется с помощью расширенного алгоритма Евклида. Во-вторых, если b — блок исходного сообщения, то мы вправе ожидать равенства D (E (b)) = b. Другими словами, расшифровывая блок сообщения, мы надеемся узнать соответствующий блок исходного.

Для взлома RSА-криптосистемы необходимо разложить n на множители, потому что для дешифрования сообщения нужно знать р и q. Однако после того, как работа системы подробно описана, ясно, что последнее утверждение не совсем точно. Чтобы прочесть шифровку, кроме самого n, нужно знать только d, обратный к е элемент по модулю ц (n). Поэтому для взлома системы достаточно вычислить d при известных n и е. Оказывается, это вычисление равносильно разложению числа n на множители.

В обсуждаемом примере п = 23 393 и е = 5. Для определения d применим расширенный алгоритм Евклида к числам ц (n) = 23 088 и 5.

Таким образом, 23 088 • 2 + 5 • (-9235) = 1. Следовательно, обратным к 5 по модулю 23 088 будет -9235 и d = 23 088 — 9235 = 13 853 — наименьшее натуральное число, сравнимое с -9235 по модулю 23 088. Значит, для расшифрования блока сообщения мы должны возвести его в степень 13 853 по модулю 23 393. В нашем примере первый зашифрованный блок — это 22 752. Вычисляя вычет числа 2 275 213 853 по модулю 23 393, получим D (22 752) = 2524. Заметьте, что даже при таких малых числах требования, предъявляемые при работе RSA-криптосистемы, превышают возможности большинства карманных калькуляторов.

Как мы уже отмечали ранее, шаги, описанные выше, приводят к работающей криптосистеме, только если в результате дешифрования каждого блока шифрованного сообщения будет восстанавливаться соответствующий блок исходного. Предположим, что мы имеем дело с системой RSA, имеющей открытый ключ (n, е) и секретный ключ (ц (n), d). Нам нужно показать, что для любого целого числа b, удовлетворяющего неравенству 0? b? п — 1, выполняется тождество D (E (b)) = b.

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

D (E (b)) = b (mod n).

Действительно, как b, так и D (E (b)) — неотрицательные целые числа, меньшие n. Поэтому они сравнимы по модулю n тогда и только тогда, когда они равны. Это, в частности, объясняет, почему мы разбиваем численное представление сообщения на блоки, меньшие п. Кроме того, отсюда видно, что блоки зашифрованного сообщения необходимо записывать отдельно: в противном случае наши рассуждения не будут работать. Из рецептов шифрования и дешифрования следует, что.

D (E (b)) = (be)d = bed (mod n).

Поскольку элементы d и e взаимно обратны по модулю ц (n), найдется такое натуральное k, что e•d = 1 + k•ц (n). Более того, по условию, числа e и d больше 2 и ц (n) > 0. Следовательно, к > 0. Подставляя 1 + k•ц (n) вместо произведения e•d, получаем.

bed? b1+kц (n)? (bц (n))k b (mod n).

Теперь воспользуемся теоремой Эйлера, которая утверждает, что bц (n)? 1 (mod n). Отсюда bed = b (mod n), т. е. D (E (b)) = b (mod n) [1].