Page 40 - 4394

Кінець прикладу 3.2.
Характеризуючи складність криптоаналізу алгоритму RSA,
можна відмітити, що задача розкладу чисел на прості множники є
задачею з класу NР, однак сьогодні не відомо, чи це є вона NP-

повною задачею, що свідчило б про її велику складність.
У теорії алгоритмів класом NP (від англ. Non-deterministic
Polynomial – невизначеним поліноміальним) називають множину

завдань, рішення яких за наявності деяких додаткових відомостей
(так званого сертифіката рішення) можна «швидко» (за час, що не
перевершує полінома від розміру даних) перевірити на
невизначеної машині Тьюринга. На практиці задача належить до

класу NP, якщо особа, яка має необмежену обчислювальну
потужність, може знайти аргументи для перевірки правильності
розв’язку задачі за поліноміальний час.

Задачі з класу NP називають NP-повною, якщо будь-яку іншу
задачу класу NP можна звести до першої за поліноміальний час.
Більш детальну інформацію про NP-повні задачі та інші

характеристики складності задач можна знайти у [2]. Відмітимо тут
тільки труднощі, що пов’язані з розв’язком сучасних завдань теорії
складності. З іншого боку, практика показує, що відомі сьогодні

алгоритми потребують досить великих часів обчислень. Зокрема,
для розкладу чисел на прості множники методом квадратичного
решета кількість обчислюваних операцій L(k) криптоаналізу
залежить від кількості бітів k = log п, необхідних для тексту з n
2
символів, таким чином:

L(к) = ехр((1+ ) k log ), де стала  > 0.
k
2
Зазначимо, що алгоритми, складність яких оцінюють

подібним способом, називають субекспоненційними. Наприклад для
19
k =512 i k=1024 біт величина L(k) складає відповідно 6,7*10 і
1,7*10 21 операцій, виконання яких за допомогою комп'ютерів зі
6
швидкодією 1 млн операцій за секунду потребує часу 2,1*10 і
16
1,4*10 років.
Сьогодні вважають, що 512-бітовий ключ забезпечує слабкий
захист інформації, 1024-бітовий ключ дає змогу досить надійно

захистити інформацію для більшості застосувань, а 2048-бітовий
ключ є таким, що гарантує захист на десятки років.

40