1 січня 2008 р.

Надійність криптосистеми RSA

Аналізуючи надійність криптосистеми RSA можна навести такий приклад. Автори алгоритму RSA в 1977 році зашифрували англійське повідомлення «the magic words are squeamish ossifrage» (магічні слова до нудоти закостенілі). На початку кожна англійська літера була замінена її номером в англійській абетці – і таким чином було отримане дане повідомлення m у цифровій формі. Як публічний ключ було вибрано число n із 129 десятковими розрядами та число е = 9007. Ці два числа та зашифроване з їх допомогою повідомлення m були опубліковані. Крім того, повідомлялося, що число n є добутком двох простих чисел з 64 та 65 десятковими розрядами відповідно. Тому, хто перший дешифрує згадану фразу, була обіцяна символічна нагорода у 100 доларів США.

Тільки через 17 років (1994р.) це повідомлення було дешифроване. Факторизація числа n, яке було добутком двох різних простих чисел, вимагала величезних затрат. Роботою керували чотири автори проекту Д.Аткінс, М.Графф, А.Ленстра та П.Лейланд, які провели попередню теоретичну підготовку з приблизно 600 добровольцями. Ці люди працювали 220 днів і використали 1600 комп’ютерів, зв’язаних мережею Інтернет.
1991 року фірма RSA Data Security (тепер має змінену назву RSA Security) почала проводити конкурси із розкладу чисел на прості множники (RSA Factoring Challenge), які стали одним із найбільших випробувальних полігонів застосувань методів факторизації.

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

Уявлення про числа, виставлені на конкурс RSA Factoring Challenge, дає наступна таблиця.
Числа, виставлені на конкурсі RSA Factoring Challenge, та суми винагород за їх факторизацію

Число для розкладу

Кількість десяткових розрядів

Призова сума

RSA-640

193

$ 20 000

RSA-704

212

$ 30 000

RSA-768

232

$ 50 000

RSA-896

270

$ 75 000

RSA-1024

309

$ 100 000

RSA-1536

463

$ 150 000

RSA-2048

617

$ 200 000


Наведемо для прикладу інформацію про найменше RSA-640 та найбільше RSA-2048 числа, виставлені на конкурс. Вважається, що для розкладу числа RSA-640 потрібно приблизно рік, а до часу факторизації числа RSA-2048 пройдуть десятки років.
Число RSA-640 має 193 десяткових розряди, а число RSA-2048 має 617 десяткових розрядів.

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