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

Число RSA-576 має 174 десяткові розряди, а його значення дорівнює

188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996 221305168759307650257059.

У цьому разі сума десяткових розрядів становить 785, а розмір винагороди за його розклад - 10 000 дол. США.

\

Число RSA-2048 має 617 десяткових розрядів, і винагорода за його факторизацію становить 200 000 дол. США:

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

Генерування відбувалося на переносному персональному комп'ютері Compaq без будь-якого його приєднання до мережі таким способом. Спочатку утворено 30 000 випадкових бітів за допомогою апаратного генератора випадкових чисел, приєднаного до паралельного порту комп'ютера. Утворені випадкові біти використано як паростки для програми генерування пар ключів RSA. Приватну частину пар ключів знищено, а публічну частину перетворено у відповідний формат і виставлено на сторінці Інтернету. Після цього твердий диск комп'ютера знищено.

У табл. 3.5 наведено оцінку ресурсів, що потрібні для розкладання за один рік чисел з різною кількістю бітів. Під машиною мають на увазі комп'ютер 500 MHz Pentium (або подібний) з відповідною оперативною пам'яттю.

Як видно з табл. 3.5, для розкладання 760-бітового числа упродовж одного року потрібно 215 000 машин класу Pentium, кожна з яких має 4 Гбайтів оперативної пам'яті. Наведені оцінки ґрунтуються на найліпших сьогодні алгоритмах розкладання. Можливо, що будуть розроблені нові підходи, які дадуть змогу зменшити як кількість комп'ютерів, так і обсяг пам'яті кожної машини.

Криптосистема Рабіна

Система Рабіна (1979) є криптосистемою, стійкість якої ґрунтується на складнос-ті розв'язування задачі розкладу числа на прості співмножники.

Вибір ключа. Випадковим способом вибирають два великі прості числа р і q та обчислюють їхній добуток п=рq. У криптосистемі Рабіна число п є публічним ключем, а пара чисел p,q — приватним ключем.

Шифрування. Шифрувати можна число (блок тексту) 0 ?m? п:

Е(т) = т2 mod n.

Тоді для блока явного тексту отримаємо криптограму

с = Е(т).

Дешифрування. Число т є квадратним коренем з с = Е(т) за модулем п.

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

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

Зазначимо, що система Рабіна не допускає однозначного дешифрування, однак її можна зробити такою шляхом простої модифікації. Однозначності можна досягти шля-хом передавання разом із криптотекстом деякої додаткової незашифрованої інформації. Це справді необхідно, коли шифрують не текстову, а суто числову інформацію.

Приклад 3.15. Нехай р = 59 і q = 71. Тоді число п = 4189 є публічним ключем. Розглянемо шифрування повідомлення новий пароль - скеля. Ігноруючи тире та пропус-ки між словами і нумеруючи літери української абетки (починаючи з нуля), переводимо наше повідомлення в числовий вигляд.

З огляду на величину и зашифровуємо повідомлення, розбиваючи його на блоки по чотири цифри в кожному: 1718 0210 1319 0020 1815 3021 1406 1532. Обчислюємо

Отримано криптотекст 2468 2210 1326 0400 1671 2799 3817 1184.

Проілюструємо тепер процес дешифрування у вибраній системі Рабіна.

Нехай маємо криптотекст 02250557 і хочемо його розшифрувати. З огляду на значення публічного ключа розіб'ємо криптотекст на два 4-цифрові блоки. Першим розшифруємо блок 0225.

Обчислимо хp = 255(mod 59) = 48 та хq = 255(mod 71) = 12. Із твердження 3.9 ви-пливає ) yp = ±4814+1(mod59) = (15,44), (p=4*14+3); yq= ±1217+1(mod 71) = (15,56), (q= 4* 17 + 3). На підставі китайської теореми про залишки отримаємо таке число z1 = 15, що 15 = 15(mod 59) та 15 = 15(mod 71). Для залишків (15, 56) маємо z2= 2257. Оскільки п = 4189, то –z1 = 4189 - 15 = 4174 і -z2 = 4189 - 2257 = 1932.

Отримано чотири тексти: 0015; 2257; 4174; 1932. Українській абетці відповідають лише комбінації 0015 ("ал") та 1932 ("пя").

Аналогічно розшифруємо блок 0557 і отримаємо комбінацію 2230 („ть"). Отже, було зашифровано повідомлення п 'ять.

З наведеної вище конструкції алгоритму Рабіна зрозуміло, що задача зламування цієї криптосистеми є задачею добування квадратного кореня з числа за модулем. Ця задача має таку ж обчислювальну складність, як і задача розкладу числа на прості множники.

Криптосистема Ель-Гамаля

Система Ель-Гамаля (1985) є криптосистемою, стійкість якої грунтується на складності розв'язування задачі дискретного логарифмування в скінченному полі.

Вибір ключів. Випадково вибирають таке просте число р, що обчислення лога-рифма за модулем р (тобто отримання для заданого числа : 0<<p такого степеня i, що ai (mod р), де а - твірна множини Zp*) практично важко реалізувати.

Далі випадково вибирають число g таке, щоб 1 < g < р - 1 і g було того самого порядку, що й числа в Zр* (в ідеальному випадку елемент g є твірною для Zр*). Відшу-кують такі числа а і h, що 1 <