Алгоритм RSA

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авторов Rivest, Shamir и Aldeman, которые придумали ее во время совместных исследований в Массачусетском технологическом институте в 1977 году. Она основана на трудности разложения очень больших целых чисел на простые сомножители. Алгоритм ее работает так:

1. Выбрать два больших простых числа p и q и вычислить два произведения n = p · q и j = (p – 1) · (q – 1).

2. Выбирать случайное целое число e, такое что НОД(e, j) = 1.

3. Вычислить d, удовлетворяющее условию e·d º 1 (mod j). (Такое число d существует на основании теоремы о количестве решений сравнения первой степени.)

4. Числа e и n публикуются как открытый ключ шифрования, а число d сохраняется как закрытый ключ.

5. Если m – сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, n), то оно превращается в шифровку возведением в степень e по модулю n и отправляется получателю .

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

Рассмотрим математические результаты, положенные в основу этого алгоритма. Т.к. ed º 1 (mod j), то существует целое число k, такое что ed = 1 + kj. В соответсвии с теоремой Ферма о том, что если НОД(m, p) = 1, то

m^p^–1 º 1 (mod p).

Возведем обе части сравнения в степень k(q–1), затем умножим обе части на a.

m^{1+k(p–1)(q–1)} º m (mod p) или m^ed º m (mod p).

С другой стороны, если D(m, p) = p, то последнее сравнение опять будет выполняться, так как каждая его часть сравнима с 0 по модулю p. Таким образом, в обоих случаях имеем

m^ed º m (mod p).

Аналогично показывается, что

m^ed º m (mod q).

Т.к. p и q простые, то получим

m^ed º m (mod n),

а это эквивалентно пункту 6 алгоритма. (Последнее сравнение следует из того, что если a º b (mod m₁), ..., a º b (mod m_k), то a º b (mod HOK(m₁, ..., m_k)), где HOK(...) – наименьшее общее кратное чисел, указанных в скобках.)

Криптостойкость системы RSA основана на том, что j не может быть просто вычислено без знания простых сомножителей p и q, а нахождение этих сомножителей из n считалась трудно разрешимой задачей. Однако недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже совершенно неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа p и q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Райвест полагал, что разложение на простые множители числа из почти что 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Но математики Ленстра из фирмы Bellcore и Манасси из фирмы DEC разложили число из 155 десятичных цифр на простые сомножители всего за 6 недель, соединив для этого 1000 ЭВМ, находящихся в разных странах мира. Выбранное число, называемое девятым числом Ферма, с 1983 года находилось в списке чисел, разложение которых считалось наиболее желательным. Это число взято потому, что оно считалось неразложимым при существующей вычислительной технике и достаточно большим для того, чтобы его можно считать безопасным для формирования n в RSA. Как заявил Ленстра, ведущий в Bellcore исследования по электронной защите информации и разложению больших чисел, их целью было показать разработчикам и пользователям криптографических систем, с какими угрозами они могут встретиться и насколько осторожны должны быть при выборе алгоритмов шифрования. По мнению Ленстра и Манасси, их работа компрометирует и создает большую угрозу применениям криптографических систем RSA.

Следует учесть, что работа по совершенствованию методов и техники разложения больших чисел только началась и будет продолжена. Те же Ленстра и Манасси в 1991 году нашли делитель тринадцатого числа Ферма, которое состоит примерно из 2500 десятичных разрядов. Теперь разработчикам криптографических алгоритмов с открытым ключом на базе RSA приходится как чумы избегать применения разложимых чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают для этого применять числа в 250 и даже 300 десятичных разрядов. А так как для щифрования каждого блока информации приходится соответствующее число возводить в колоссально большую степень по модулю n, то для современных компьютеров это задача на грани возможного. Поэтому для практической реализации шифрования RSA радиоэлектроники начали разрабатывать специальные процессоры, которые позволили бы выполнять операции RSA достаточно быстро. Лучшими из серийно выпускаемых кристаллов являются процессоры фирмы CYLINK, которые позволяют выполнять возведение в степень целого числа из 307 десятичных знаков за доли секунды. Отметим, что чрезвычайно слабое быстродействие криптографических систем на основе RSA лишь ограничивает область их применения, но вовсе не перечеркивает их ценность.