Алгоритм RSA

Текст взят из книги Брюса Шнайера "Прикладная криптография", 2-е издание

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

Такие криптосистемы называют ассиметричными, или двухключевыми, поскольку они имеют два ключа: несекретный – для шифрования и секретный – для дешифрования.

Из всех предложенных за эти годы алгоритмов с открытым ключом RSA проще всего понять и реализовать. (Мартин Гарднер (Martin Gardner) опубликовал раннее описание алгоритма в своей колонке «Математические игры» в журнале Scientific American [1]). RSA также является самым популярным алгоритмом. Названный в честь трех изобретателей – Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Адлемана (Leonard Adleman), этот алгоритм долгие годы противостоит многочисленным попыткам криптоаналитического вскрытия. Хотя криптоанализ ни доказал, ни опроверг безопасность алгоритма RSA, проведенная за эти годы работа, по сути, обосновывает степень доверия к алгоритму.

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

Для генерации двух ключей применяются два больших случайных простых числа p и q. Для максимальной безопасности p и q должны иметь равную длину. Рассчитывается произведение:

$N = pq$

Затем случайным образом выбирается ключ шифрования E, такой что E и (p-1)(q-1) являются взаимно простыми числами. Наконец, с помощью расширенного алгоритма Евклида вычисляется ключ расшифрования D, такой что:

$ED ≡ 1 \; mod \; (p-1)(q-1)$

Другими словами:

$D ≡ E^{-1} \; mod \; ((p-1)(q-1))$

Заметим, что D и N также взаимно простые числа. Числа E и N – это открытый ключ, а число Dзакрытый. Два простых числа p и q больше не нужны. Они могут быть отброшены, но не должны быть раскрыты.

При шифровании сообщение M сначала разбивается на цифровые блоки, размерами меньше N (для двоичных данных выбирается самая большая степень числа 2, меньшая N). Т.е., если p и q являются 100-разрядными простыми числами, то N будет содержать около 200 разрядов, и каждый блок сообщения Mi должен быть около 200 разрядов в длину (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше N). Зашифрованное сообщение С будет состоять из блоков Сi той же самой длины. Формула зашифрования выглядит просто:

$C_i = M_i^E\;mod\;N$

При расшифроке сообщения для каждого зашифрованного блока Сi вычисляется:

$M_i = C_i^D\;mod\;N$

Так как:

$C_i^D = (M_i^E)^D = M_i^{ED} = M_i^{k(p-1)(q-1)+1} = M_i M_i^{k(p-1)(q-1)} = M_i * 1 = M_i$, все по $(mod\;N)$

то формула восстанавливает сообщение. Все вышесказанное суммировано в табличке.

Открытый ключ:
N – произведение двух простых чисел p и q (p и q должны храниться в секрете)
E – число, взаимно простое с (p-1)(q-1)

Закрытый ключ:
$D = E^{-1} mod\;((p-1)(q-1))$

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

Атаки на RSA

Раскрытие малого секретного показателя

Атака, предложенная Майклом Винером (Michael Wiener) [2], раскрывает D, если D не превышает четверти размера N, а E меньше N. При случайном выборе E и D такое встречается редко и никогда не происходит, если значение E невелико.
Вывод: выбирайте большое значение D.

Теорема. Пусть задана RSA-криптосистема с алгоритмами:
$N = pq, ED ≡ 1\;mod\;((p-1)(q-1)), q < p < 2q, D < \frac{1}{3} * N^{\frac{1}{4}}$
Тогда D эффективно вычислимо.

Винер предлагает использовать непрерывные дроби при атаке на RSA. Одним из важных результатов теории непрерывных дробей является то, что если несократимая дробь $\frac{p}{q}$ удовлетворяет неравенству:

$| \alpha - \frac{p}{q} | \le \frac{1}{2q^2}$

то $\frac{p}{q}$ - одна из подходящих дробей в разложении $\alpha$ в непрерывную дробь. В случае атаки на RSA неравенство (доказательство мы пропустим) примет вид:

$| \frac{E}{N} - \frac{k}{D} | < \frac{1}{2D^2}$

Таким образом, раскладывая число $\alpha = \frac{E}{N}$ в непрерывную дробь, можно узнать расшифровывающую экспоненту, поочередно подставляя знаменатели подходящих дробей в выражение:

$(M^E)^D = M\;mod\;N$ для некоторого случайного числа M. Получив равенство, найдем D.

Библиография
1. M.Gardner, "A New Kind of Cipher That Would Take Millions of Years to Break", Scientific American, v.237, n.8, Aug 1977, pp. 120-124
2. M.J.Wiener, "Cryptoanalysis of Short RSA Secret Exponents", IEEE Transactions on Information Theory, v.36, n.3, May 1990, pp. 553-558
Криптографические примитивы
Алгоритмы с открытым ключом RSA DSA
Поточные шифры RC4
Хэш-функции RIPEMD-160 SHA-1/2
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License