Щоб розшифрувати отримане повідомлення, А використовує ключ d = 849:

Основи утворення ключів, шифрування й дешифрування опираються на таке твердження, яке випливає з теореми Ейлера.

Твердження 3.18. Нехай п = pq є добутком двох різних простих чисел. Якщо e* d 1 (mod ф(п)), то для всіх х є Zn

Хed x(mod п).

Зазначимо, що у випадку k різних простих чисел виконується таке твердження.

Твердження 3.19. Нехай п=р1* р2 *…pk є бутком k різних простих чисел. Порівняння

Хu x(mod п)

виконується для всіх х є Zn тоді й тільки тоді, коли и 1l(mod HCK(p1 - 1, р2 - 1,…,pk-1)).

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

Твердження 3.20. Нехай А - алгоритм, який для заданого ключа е, п алгоритму RSA знаходить відповідний ключ d. Тоді можна сконструювати алгоритм з процедурою А, який розкладає п на прості множники та має порівнянний з алгоритмом А час обчислень і використовує порівнянну з алгоритмом А пам'ять.

Твердження 3.20 означає таке: якщо існує практичний метод відшукання при-ватних ключів, то можна дати практичний алгоритм розкладання п на прості множники. У цьому разі, маючи розклад и на прості множники, можна легко обчислити приватний ключ. З іншого боку, алгоритм відшукання розкладу п на прості множники еквівалент-ний алгоритму відшукання модуля ф(п) конгруенції e*d = 1 (mod ф(п)).

Справді, оскільки п = pq, т о ф(п) = ф(р) ф(q) = (р -1)(q -1) = р* q - (р + q) + 1 і р+q-n- ф(п) + 1. Звідси множники р, q є коренями квадратного рівняння

Х2-Х+n=0

Отже, знаючи ф(п), можна, розв'язуючи це рівняння, знайти числа р і q, а знаючи р і q, легко обчислити ф(п).

Задача розкладу чисел на прості множники є задачею з класу NP, однак сьогодні не відомо, чи це є NP-повна задача, що свідчило б про її складність. З іншого боку, відомі сьогодні алгоритми потребують досить великих часів обчислень. Зокрема, для методу квадратичного решета цей час обчислень залежить від кількості бітів k=log2 n числа п так: L(k) = exp((l +)), де стала > 0. Зазначимо, що алгоритми, склад-ність яких оцінюють подібним способом, називають субекспоненційними.

У табл. 3.3 наведено значення величин L(k) залежно від кількості бітів k числа п, де MIPS година означає продуктивність 1 000 000 команд за секунду упродовж 1 год (3.1*1013 команд).

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

Тільки через 17 років (у 1994 р.) це повідомлення дешифрували. Факторизація розклад) числа п, яке було добутком двох різних простих чисел, потребувала величез-них затрат. Роботою керували чотири автори проекту Д.Аткінс, М.Графф, А.Ленстра та Л.Лейланд, які провели попередню теоретичну підготовку з приблизно 600 доброволь-лями. Ці люди працювали 220 днів і використали 1600 комп'ютерів, пов'язаних мере-жею Internet.

У 1991 р. фірма RSA Data Security (тепер RSA Security) почала проводити кон-курси із розкладу чисел на прості множники (RSA Factoring Challenge), які стали одним з найбільших випробувальних полігонів застосувань методів факторизації.

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

Найвагомішим нині результатом є факторизація так званого числа RSA-155 з 155 десятковими розрядами. Виставлені на конкурс числа позначають RSA-XXXX, де ХХХХ дорівнює довжині числа в бітах. Факторизацію завершено 1999 р. після семи місяців роботи. Керівниками проекту були А.Ленстра та Х.Ріеле. Обчислення виконували на 300 робочих станціях і персональних комп'ютерах. Розклад заданого 512-бітового числа є важливим у тому сенсі, що 512 бітів - загальноприйнятий розмір ключа для шифрування переважної більшості комерційної інформації, яка надходить через електронну пошту. Водночас практичне значення розкладу числа RSA-155 не треба перебільшувати. Результат вражає, проте ціна зламування 512-бітового ключа надто висока, щоб охочі могли широко застосовувати цю техніку. Його необхідно розглядати ік сигнал про важливість вибору достатньо великих за розміром ключів. Фірма RSA Security ще задовго до описаної факторизації рекомендувала розміри ключів щонайменше 768 бітів.

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

Як приклад, наведемо число RSA-155 у вигляді добутку двох простих співмнож-ників:

де обидва співмножники мають по 78 десяткових розрядів.

Інформацію про конкурси RSA Factoring Challenges