Page 20 - 4395

 розкласти n на два прості співмножники p i q; це дасть
-1
можливість обчислити Ф(n) = (p - 1) · (q - 1) і d = e (mod Ф(n));
 визначити Ф(n) безпосередньо, без початкового визначення р
-1
і q; це також дасть можливість визначити d = e (mod Ф(n));
 визначити d безпосередньо, без початкового визначення
Ф(n).
Захист від лобової атаки для RSA і йому подібних алгоритмів

полягає у використанні великої довжини ключа. Таким чином, чим
більше бітів в е і d, тим краще. Проте, оскільки обчислення необхідні
як при створенні ключів, так і при шифруванні/дешифруванні, то
чим більше розмір ключа, тим повільніше працює система.

Більшість дискусій про криптоаналіз RSA фокусуються на
завданні розкладання n на два прості співмножники. В даний час
невідомі алгоритми, за допомогою яких можна було б розкласти

число на два прості множники для дуже великих чисел (тобто
декілька сотень десяткових цифр). Кращий з відомих алгоритмів дає
результат, пропорційний

L (n) = esqrt (ln n * ln (ln n)).

Поки не розроблено кращі алгоритми розкладання числа на

прості множники, можна вважати, що величини n від 100 до 200
цифр у даний час є достатньо безпечними. На сучасному етапі
вважається, що число з 100 цифр може бути розкладене на

множники за час порядку двох тижнів. Для дорогих конфігурацій
криптоаналізу (тобто близько 10 млн дол.) число з 150 цифр може
бути розкладене приблизно за рік. Розкладання числа з 200 цифр
перебуває за межами обчислювальних можливостей. Наприклад,

навіть якщо обчислювальний рівень в 1024 млрд операцій у секунду
досяжний, що вище за можливості сучасних технологій, то буде
потрібно понад 10 років для розкладання на множники числа з 200

цифр з використанням існуючих алгоритмів.
Для відомих у даний час алгоритмів завдання визначення Ф(n)
за даними е і n, принаймні, порівнянне за часом із завданням

розкладання числа на множники.
Для того щоб уникнути вибору значення n, яке могло б легко
розкладатися на співмножники, на р і q має бути накладене багато

додаткових обмежень:
 р і q повинні один від одного відрізнятися за довжиною
тільки декількома цифрами; таким чином, обидва значення р і q

20