Стойкость алгоритма RSA

Очевидно, что стойкость RSA и асимметричных алгоритмов в целом зависит от сложности обращения односторонних функций, лежащих в основе данного типа алгоритмов. В RSA сложность обращения односторонней функции F(x) - xy (mod n) зависит от сложности разложения на множители модуля п. При этом следует иметь в виду, что это утверждение является всего лишь предположением, поскольку строгих математических доказательств эквивалентности данных проблем пока не существует.
В настоящем разделе рассматриваются основные атаки на алгоритм RSA, известные на сегодняшний день. Следует отметить, что стойкость RSA может быть снижена за счет некорректного выбора параметров алгоритма.
Среди наиболее известных недостатков алгоритма RSA можно выделить некорректный выбор значений р и q. Числа р и q должны быть простыми и не содержаться ни в одной из известных таблиц простых чисел.

Эти числа также не должны быть близкими друг к другу. Если (р - q)/2 мало и (р + q)/2 немного больше, чем Vn , то при (р + q)2/4 - п С (р - q)2/4 левая часть равенства образует полный квадрат. При факторизации п перебираем целые числа на соответствие неравенству х >уnq до тех пор, пока не найдем такое значение, что х2 - п = у2. Тогда p = x + ynq = x-y. Учитывая изложенный факт, а также ряд других атак, основанных на неправильном выборе чисел р и q, сформулируем следующие требования к выбору чисел р и q:
1. Данные числа должны быть большими числами одинаковой длины; например: если п = 1024 бита, то длина р и q должна быть равна 512 битам.
2. Различие между р и q должно быть большим.
3. Числа р и q должны быть строго простыми. Число называется строго простым, если выполнены условия:

а) р - 1 должно иметь большой простой делитель (обозначим его через г);
б) р + 1 должно иметь большой простой делитель;
в) г - 1 должно иметь большой простой делитель.
Требование а) обусловлено противодействием алгоритмам факторизации п (один из таких алгоритмов был предложен Поллардом).

Аналогично обосновывается требование б).

Выполнение на практике требования в) позволяет противостоять циклическим атакам.