Очевидно, що стійкість RSA і асиметричних алгоритмів в цілому залежить від складності звернення односторонніх функцій, що лежать в основі даного типу алгоритмів. У RSA складність звернення односторонньої функції F (x) - xy (mod n) залежить від складності розкладання на множники модуля п. При цьому слід мати на увазі, що це твердження є всього лише припущенням, оскільки строгих математичних доказів еквівалентності даних проблем поки не існує.

У цьому розділі розглядаються основні атаки на алгоритм RSA, відомі на сьогоднішній день. Слід зазначити, що стійкість RSA може бути знижена за рахунок некоректного вибору параметрів алгоритму.

Серед найбільш відомих недоліків алгоритму RSA можна виділити некоректний вибір значень р і q. Числа р і q повинні бути простими і не міститися ні в одній з відомих таблиць простих чисел. Ці числа також не повинні бути близькими один до одного. Якщо (р - q) / 2 мало і (р + q) / 2 трохи більше, ніж Vn, то при (р + q) 2 / 4 - п С (р - q) 2 / 4 ліва частина рівності утворює повний квадрат . При факторизації п перебираємо цілі числа на відповідність нерівності г> Vn до тих пір, поки не знайдемо таке значення, що х2 - п = у2. Тоді p = x + ynq = xy. Враховуючи викладений факт, а також ряд інших атак, заснованих на неправильному виборі чисел р і q, сформулюємо наступні вимоги до вибору чисел р і q:

1. Дані числа повинні бути великими числами однакової довжини; наприклад: якщо п = 1024 біта, то довжина р і q повинна бути дорівнює 512 бітам.

2. Різниця між р і q повинно бути більшим.

3. Числа р і q повинні бути строго простими. Число називається строго простим, якщо виконані умови:

а) р - 1 повинно мати великий простий дільник (позначимо його через г);