Аналіз ефективності методу факторизації на еліптичних кривих. Практика

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

Наведемо визначення факторизації.

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

Будемо позначати число, яке потрібно розкласти буквою N, а два співмножника, в результаті множення яких отримаємо N, a і b.

Алгоритм факторизації Ленстры (факторизація на еліптичних кривих) є одним з найбільш швидких методів факторизації. Він має багато спільного з методом Полларда (p – 1), але працює значно швидше, слід зазначити, що він є субэкспоненциальным методом. Головна особливість алгоритму – це те, що час, витрачений на факторизацию, залежить не від розмірності N, а від розміру найменшого дільника числа N.

Докладно про цей метод, ви зможете почитати матеріалу у списку використаної літератури, але все ж наведемо основні стадії алгоритму.

  1. Введемо число N.
  2. Виберемо деяке значення B, яка є максимальною межею числа-дільника N.
  3. Згенеруємо випадковим чином значення x,y,a, які належать безлічі цілих чисел від 0 до N-1. Ці значення визначають криву, а так само x і y визначають початкову точку P.
  4. Обчислимо b = y^2-x^3-ax mod n і g = Н.Про.Д.(N, 4a^3+27b^2). Важливо, що g не був дорівнює N, інакше повертаємося до п. 2. Якщо 1 < g < n, тоді припинимо обчислення – дільник знайдено. Цей варіант можливий при малих значеннях числа N (наприклад, 10), при зростанні N ця можливість трапляється все рідше.
  5. Далі потрібно виконати цикл, в результаті якого для кожного простого числа p (в межах від 2 до B-1) обчислимо точку P, домноженную на p^r, де r найбільша ступінь, що задовольняє умові p^r < B.
В арифметиці полів немає операції ділення, яка необхідна в формулах для знаходження координат точок, так що ми перетворимо вираз у вигляді множення, а зворотний елемент шукаємо за розширеним алгоритмом Евкліда. До того ж кожне нове обчислення ми виробляємо за модулем числа N.

Алгоритм завершить свою роботу, коли буде знайдений Н.Про.Д.(N, P), який більше 1 і менше N. щоб уникнути помилки у відповіді, функція знаходження Н.Про.Д. повинна перевіряти тільки позитивні значення.

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

image
N=10 – 0,005 sec;
N=437 – 0,019 sec;
N=3127 – 0,055 sec;
N=23707 – 0,191 sec;
N=1752967 — 1,534 sec;
N=6682189 — 0,143 sec;
N=12659363 — 3,376 sec;
N=494370889 – 4,484 sec;
N=1435186847 — 87,377 sec;
Так як крива генерується з випадкових значень, то час факторизації при кожному новому запуску програми буде різним. Дивлячись вдала чи крива нам попадеться. З цього, спробуємо взяти ці ж числа і виконати факторизацию ще кілька разів і звіримо результати.

image
N=10 – 0,016 sec;
N=437 – 0,016 sec;
N=3127 – 0,218 sec;
N=23707 – 0,079 sec;
N=1752967 — 1,484 sec;
N=6682189 — 1,125 sec;
N=12659363 – 6,906 sec;
N=494370889 – 4,781 sec;
N=1435186847 — 81,766 sec;
І для закріплення зробимо останній вимір.

image
N=10 – 0,012 sec;
N=437 – 0,022 sec;
N=3127 – 0,156 sec;
N=23707 – 0,205 sec;
N=1752967 — 1,418 sec;
N=6682189 — 1,056 sec;
N=12659363 – 0,25 sec;
N=494370889 – 5,488 sec;
N=1435186847 – 14,117 sec;
Як ми бачимо на останньому графіку, час витрачений на останнє число помітно зменшилася, це характеризується тим, що крива генерується випадковим чином. Слід зауважити, що час, витрачений на виконання алгоритму, залежить і від значення B, яке ми вводимо. Я намагався брати значення наближені до значень двох співмножників (a і b), але якщо ви будете виконувати операцію над числом, де початкові множники не відомі навіть приблизно, то варто вибирати межа вище. Але чим вище межа, тим більше і часу піде на обчислення точок, тому що їх буде більше, це потрібно враховувати.

Слід враховувати і продуктивність обчислювальної машини. Я виробляв обчислення на Процесорі AMD Athlon(tm) II X4 645 з частотою 3.10 ГГц. Навантаження на Процесор була близько 40 % при роботі програми. Навантаження на Пам'ять помічено не було.

Підсумок
Алгоритм працює за досить гарний час, але тільки для відносно великих значень. Адже як ми бачимо з графіку 1 і 2, число після 1 мільярда в більшості випадків має великий розрив з часом, витрачений на число 494370889, але це було очікувано, адже як було відмічено раніше, метод є субэкспоненциальным.

Спасибі, що дочитали мою першу статтю.

Використана література: «Математичні основи захисту інформації»
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.