Сучасні інформаційні технології/4. Інформаційна безпека

К.т.н. Цепенюк М. І., Цепенюк Н.М.

Тернопільський державний технічний університет імені Івана Пулюя, Україна

Факторизація довгих цілих в криптографії: ймовірнісний підхід

Перший конкретний алгоритм для відкритого шифрування запропонували в 1978р. Райвест, Шамір, та Ейдлман [1]. Ця криптографічна система називається RSA (Rivest-Shamir-Adleman) і вона широко використовується і по нині. Стійкість системи обумовлюється складністю факторизації (розкладу на множники) деякого довгого цілого числа n (>512 біт) у загальному випадку, тобто без будь-яких додаткових припущень про вигляд цього числа. Таким чином, розкриття RSA являє собою наступну задачу:

дано , знайти .

Наразі невідомий ефективний (поліноміальний) алгоритм розв’язання цієї задачі [2]

-алгоритм Полларда.

В класичних працях П. Л. Чебишева, Сільвестра, Ерміта та ін. була отримана відома оцінка для (див. [2]) - кількості простих чисел, що передують числу х:

.
Оскільки найменший дільник числа n не перевищує ,

то при факторизації методом прямого перебору потрібно буде ділити n в граничному випадку на перших простих чисел. Проте, для факторизації чисел довжиною 60 десяткових знаків і більше, такий підхід неприйнятний. Більше того, алгоритм повинен задовільно працювати для складного загального випадку – число n є добутком лише двох простих чисел, причому кожне із них є порядку . Розв’язати таку задачу можна лише за допомогою розподілених систем факторизації [1] із використанням спеціалізованих алгоритмів. Варіант такої системи ми побудували на основі Pollard-Rho алгоритму [2].

Нехай p - найменший простий співмножник числа n. Також нехай в результаті випадкового генерування чисел вдалося отримати такі цілі a та b (a>b>0), що

mod p . (1)

Тоді, очевидно, число p є дільником a-b і може бути отримане обчисленням НСД(a‑b,n).

Таким чином, факторизацію n можна звести до знаходження двох чисел a та b, що дають при діленні на p однакові остачі. За принципом Діріхле, це завжди можна зробити, породивши p+1 різних чисел.

Отримати такі a та b з великою ймовірністю можна значно раніше. Задамося числом r (r<p) і оцінимо ймовірність того, що, породивши випадковим чином r різних чисел, ми отримаємо їх усіх із різними остачами при діленні на p (невідоме p). Ця ймовірність, як показав Феллер (див. [2]), V(r, p), залежна від r та p, рівна

V(r,p)===

= .

Оцінимо логарифм цієї ймовірності:

ln V(r,p)=, в останній викладці використовується нерівність .

При рості r ймовірність V(r,p) падає швидко: при r=, маємо, ln V=-1/2, V=; а при r=, V=.

Відповідно, ймовірності знайти a та b, які задовольняють (1), рівні 0,39 та 0,63. Оскільки , є хороші шанси факторизувати n за спроб.

Результатом нашої роботи є побудова розподіленої системи для факторизації довгих цілих на основі паралельної модифікації алгоритму Pollard-Rho [2]. Система працює в середовищі Windows NT і використовує відповідні мережні можливості цієї ОС. Середовище зв’язку в нашому випадку являє собою швидкісну локальну мережу (LAN), яка сполучає кілька десятків(сотень) робочих станцій. На кожній із цих станцій запускається свій процес(модуль факторизації), що реалізує алгоритм Полларда. Одна з робочих станцій вибирається в якості керуючої консолі, призначеної для узгодженого функціонування інших та збору результатів факторизації за допомогою протоколу DCOM [3].

Проведені дослідження підтвердили ефективність роботи системи. Так, факторизація числа n=5191268089719664430892809=77158673929*67280421310721 тривала 28451 кроків. Факторизація проводилася із використанням одного факторизуючого модуля і зайняла 9 секунд на комп’ютері Pentium™ 1000MHz. Інші отримані результати приведені в таблиці:

n	p	q	К-сть ітерацій
5191268089719664430892809 18446744073709551617 2286227974369 439125228929	67280421310721 274177 18837001 65537	77158673929 67280421310721 121369 6700417	28451 6120 1457 679

Література:

1. О. В. Вербіцький. Вступ до криптології// ВНТЛ.- Львів, 1998.-357 с.

2. Д. Кнут. Искусство программирования для ЭВМ. - Т. 2. - М.: Мир, 1977.- 724 с.

3. Э. Рофейл, Я. Шохауд. COM и COM+. Полное руководство. ТОО «Век», 2000.- 584 с.