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

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

задача проверки числа на простоту является сравнительно легкой;

задача разложения чисел вида n = pq (р и q — простые числа); на множители является очень трудной, если мы знаем только n, а р и q — большие числа (это так называемая задача факторизации, подробнее о ней см. "Основные положения теории чисел, используемые в криптографии с открытым ключом").

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные должны быть представлены в виде целых чисел между 0 и n -1 для некоторого n.

Шифрование Пусть абонент А хочет передать зашифрованное сообщение абоненту Б. В этом случае абонент Б должен подготовить пару (открытый ключ; закрытый ключ) и отправить свой открытый ключ пользователю А. Первым этапом является генерация открытого и закрытого ключей. Для этого вначале выбираются два больших простых числа Р и Q. Затем вычисляется произведение N: N = PQ.

После этого определяется вспомогательное число f: f = (Р - l)(Q - 1).

Затем случайным образом выбирается число d < f и взаимно простое с f. Далее необходимо найти число е, такое, что еd mod f = 1.

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

Так как пользователь Б хочет получить зашифрованное сообщение от пользователя А, значит пользователь Б должен отправить свой открытый ключ (d, N) пользователю А. Числа Р и Q больше не нужны, однако их нельзя никому сообщать; лучше всего их вообще забыть.

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

Второй этап – шифрование данных. Если абонент А хочет передать некоторые данные абоненту Б, он должен представить свое сообщение в цифровом виде и разбить его на блоки m1, m2, m3,..., где mi < N. Зашифрованное сообщение будет состоять из блоков сi.

Абонент А шифрует каждый блок своего сообщения по формуле

ci = mid mod N

используя открытые параметры пользователя Б, и пересылает зашифрованное сообщение С=(с1, с2, с3,...) по открытой линии.

Абонент В, получивший зашифрованное сообщение, расшифровывает все блоки полученного сообщения по формуле

mi = ce mod N

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

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

Пример вычислений по алгоритму

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

Р = 3, Q = 11, N = 3x11 = 33.

Тогда f = (Р - l)(Q - 1) = (3-1)(11-1) = 20.

Затем пользователь Б выбирает любое число d, не имеющее общих делителей с f (это необходимо для того, чтобы зашифрованное сообщение можно было потом однозначно восстановить). Пусть d = 13. Это число будет одним из компонентов открытого ключа.

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

еd mod f = 1.

Для малых значений f число е можно найти подбором. В общем случае для поиска е можно использовать обобщенный алгоритм Евклида, приведенный в "Основные положения теории чисел, используемые в криптографии с открытым ключом". В нашем случае подходит е=17. (Проверяем: 13*17 mod 20 = 221 mod 20 = 1.)

Теперь пользователь Б должен запомнить свой закрытый ключ 17, отправить открытый ключ (13, 33) пользователю А и уничтожить числа Р = 3 и Q = 11.

Пользователь А, получивший открытый ключ (13, 33), увидев, что N=33, разбивает исходное сообщение на три блока, причем значение каждого меньше N. Например, пусть имеется три блока m1=8, m2=27, m3,=5. Затем пользователь А шифрует каждый блок:

c1=813 mod 33 = 17

c2 = 2713 mod 33 = 15

c3 = 513 mod 33 = 26

Зашифрованное сообщение, состоящее из трех блоков (17, 15, 26), передается пользователю Б, который, используя свой закрытый ключ е = 17 и N=33, расшифровывает сообщение:

m1 = 1717 mod 33 = 8

m2 = 1517 mod 33 = 27

m3 = 2617 mod 33 = 5

Таким образом, абонент Б расшифровал сообщение от абонента А.

На протяжении многих лет алгоритм RSA активно используется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях. Открытое шифрование на базе алгоритма RSA применяется в популярном пакете шифрования PGP, операционной системе Windows, различных Интернет-браузерах, банковских компьютерных системах. Кроме того, различные международные стандарты шифрования с открытым ключом и формирования цифровой подписи используют RSA в качестве основного алгоритма.

Для обеспечения высокой надежности шифрования необходимо, чтобы выступающее в качестве модуля число N было очень большим – несколько сотен или тысяч бит. Только в этом случае будет практически невозможно по открытым параметрам определить закрытый ключ. Так, известно, что в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного модуля. Для этого с помощью сети Интернет было задействовано более тысячи компьютеров.

Сами авторы RSA рекомендовали использовать следующие размеры модуля N: 768 бит - для частных лиц; 1024 бит - для коммерческой информации; 2048 бит - для особо секретной информации. С момента получения их рекомендаций прошло какое-то время, поэтому современные пользователи должны делать поправки в сторону увеличения размера ключей. Однако, чем больше размер ключей, тем медленнее работает система. Поэтому увеличивать размер ключа без необходимости не имеет смысла.

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

Алгоритм RSA реализуется как программным, так и аппаратным путем. Многие мировые фирмы выпускают специализированные микросхемы, производящие шифрование алгоритмом RSA. Программные реализации значительные медленнее, чем аппаратные. К достоинствам программного шифрования RSA относится возможность гибкой настройки параметров, возможность интеграции в различные программные пакеты. В целом, и программная, и аппаратная реализации RSA требуют для выполнения примерно в тысячи раз большего времени по сравнению с симметричными алгоритмами, например ГОСТ 28147-89.