• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Основні методи факторизації RSA

З появою алгоритму RSA послідовно з часом були розроблені та реалізовані ряд методів факторизації модуля перетворення N [236, 422, 423, 11, 421, 4, 96, 9–13]. У цілому методи факторизації можна поділити на два великих класи – з експоненційною та субекспоненційною складністю. Окремо можна розглядати поліноміальний метод (Гордона Чалмерса) [421].

До експоненційно складних належать такі методи:

- перебирання типу «груба сила» зі складністю О(N^1/2);

- ρ-Полларда метод зі складністю О(N^1/4);

- P–1 Полларда метод;

- P+1 метод Вільямса;

- метод квадратичних форм Шенкса зі складністю О(N^1/4);

- метод Лемана.

До субекспоненційни[методів належать:

- метод Діксона зі складністю L_N(1/2, 2 );

- метод безперервних дробів зі складністю L_N(1/2, );

- метод квадратичного решета зі складністю L_N(1/2, );

- метод еліптичних кривих зі складністю L_p(1/2, ), де P – найменше просте, яке ділить N;

- метод решета числового поля зі складністю L_N(1/3,(64/9)^1/3);

- метод спеціального решета числового поля зі складністю L_N(1/3,(32/9)^1/3).

Окремо необхідно назвати с.

28.3.3. Метод факторизації ρ-Полларда

Метод факторизації ρ-Полларда ґрунтується на створенні колізії елементів кільця Z_N [5, 12, 96]. Його сутність полягає у знаходженні цілих чисел Х і Y, які порівнюються за , тобто

(9.3)

Порівняння (9.3) можна подати у вигляді

а також у вигляді рівняння:

(9.4)

Сутність реалізації методу можна звести до такого. За допомогою деякої функції будується послідовність точок згідно з рис. 9.1 (крива ρ-Полларда).

Рис. 9.1. Крива ρ- Полларда створення колізії

Після здійснення колізії знаходимо значення одного з простих чисел способом обчислення найбільшого спільного дільника між (X–Y) та N, тобто

НСД (9.5)

Застосування цього методу суттєво залежить від вибору функції, згідно з якою будується крива ρ-Полларда. Очевидно, єдиного підходу тут немає. Розглянемо практичні приклади для малих значень N [13].

Приклад 9.1. Факторизувати модуль N, використавши мето ρ-Поларда, якщо

N = 221, f(x) = x_i = ax_i-1 + c (при а = 11, = 127, с = 1).

Розв’язання задачі.

,

x₁ = 118; НСД (127–118, 221) = (9, 221)=1 (тобто спільних дільників немає).

,

x₂ = 19; НСД (118-19,221) = НСД (99,221) = 1.

Таким чином, НСД (х₁ – х₂, N) знову не має спільного дільника.

.

Розрахуємо послідовно х_і поки, НСД (х₁ – х₂, N) різнитиметься від 1 або N.

x₃ = 210; НСД (191,221) = 1,

,

x₄ = 7; НСД (203, 221) =1,

,

x₅ = 78; НСД (71,221) = 1,

,

x₆ = 91.

Для х₆ маємо НСД (х₆ – х₅, N) = НСД (91–78, 221) = НСД (13, 221) = 13.

Таким чином, один зі співмножників модуля N є 13, наприклад, P=13. Тоді Q=N/P=221/13=17. Перевіряємо правильність розв’язку, знайшовши P×Q = 221.

Приклад 9.2. Факторизувати число N = 209, якщо f(x) =x_i = x² + 1(mod N), тобто прийнявши, що .

Розв’язання задачі.

x₁ = (17² + 1)mod 209 = 81,

x₂ = (81² + 1)mod 209 = 83,

НCД (2, 209) = 1 (розв’язку немає),

x₃ = (83² + 1)mod 209 = 202,

x₄ = (202² + 1)mod 209 = 50,

x₃ – x₄ = |202-50| = 152.

НCД (152, 209) = 19.

Таким чином, один зі співмножників, наприклад P=19, тоді Q=209/19=11.

У цілому необхідно відмітити, що метод ρ-Полларда ґрунтується скоріше на інтуїції чи досвіді. Для практичних значень N він зараз, на наш ключів погляд, не реалізовний. Його єдиною перевагою є можливість розпаралелювання обчислень. У той же час відмітимо, що він застосовується при дискретному логарифмуванні в групах точок еліптичних кривих як найбільш ефективний [12].

28. 4. Метод факторизації «квадратичне решето»

До 1994 року для розкладання на множники застосовувався підхід, відомий як метод квадратичного решета [11, 236, 423, 422, 13, 425]. Загроза ключам великої довжини тут подвійна: безупинне зростання обчислювальної потужності сучасних комп’ютерів і безупинне вдосконалення алгоритмів розкладання на множники.

Розглянемо двійкове решето, яке, відповідно до сучасних поглядів, є найбільш швидким при довжині модуля не більше ніж 120 десяткових цифр.

Необхідно знайти два випадкові цілі числа x та y – такі, що:

. (9.6)

Представимо (9.6) у вигляді

. (9.7)

З урахуванням того, що в порівнянні (9.7) операції виконуються за модулем N, його

можна подати у вигляді рівняння:

, k=1,2,... (9.8)

Якщо розкласти (9.8) як різницю квадратів, то отримаємо, що

, k =1, 2, … . (9.9)

причому N = P×Q.

Вираз (9.9) доцільно застосовувати в таких випадках:

(9.10)

У випадках 1 і 2 P або Q знайти не можна, оскільки модуль N не може бути розкладеним на співмножники. У випадках 3 та 4 маємо розв’язок.

Далі, якщо (х–у)/Р, то ми можемо скористатися алгоритмом Евкліда та обчислити найбільший спільний дільник:

(9.11)

Враховуючи (9.11), можна обчислити P або Q.

Практично факторизацію модуля N з використанням двійкового решета можна здійснити в такій послідовності.

1. Нехай N – число, яке необхідно факторизувати. Побудуємо деяку базу з таким значенням Z, щоб , де – прості числа, краще невеликого розміру, Z – база двійкового решета.

2. Знайдемо , округливши знизу. Потім побудуємо числа вигляду

(9.12)

і знайдемо

.

Як результат отримаємо порівняння:

.

Таким чином, маємо

. (9.13)

Приклад 9.3 [13]. Зловмисник визначив, що направлене шифрування виконується на відкритому ключі отримувача Е_к=31, модуль перетворення N=3599. Необхідно знайти особистий ключ отримувача D_k, з використанням якого можна здійснити розшифрування повідомлення М, якщо застосовується RSA перетворення.

Розв’язання задачі може здійснюватись у такому порядку:

1. Факторизуємо модуль N і визначаємо прості числа P та Q.

2. Знаходимо значення функції

.

3. Розв’язуємо порівняння

.

Факторизацію виконуємо, використовуючи метод двійкового решета.

Спочатку визначаємо базу розкладу – прості невеликі числа р₁, р₂,... р_r, добуток яких Р_б є близьким до N=3599:

.

Знаходимо

.

Будуємо таблицю 9.4.

Таблиця 9.4

Реалізація двійкового решета (розрахунки)

Беремо рядки зі значеннями x=3 та x=62, у результаті маємо, що:

;

.

Перемноживши рядки, маємо

або

.

Знайшовши залишок від значення 7502, маємо

.

Отже x=304, y=245.

Далі

НСД (│304-245│,3599)=59=Р,

= =61.

Отже, Р=59, Q=61.

Далі знаходимо

.

Тепер порівняння має такий вигляд:

.

Після переходу до рівняння

,

подамо його у вигляді:

.

Розв’язуємо це діафантове рівняння, використовуючи ланцюгові дроби:

; r0=112;

; r1=3;

; r2=1;

; r3=7; μ=3;

;

;

;

;

.

Перевіримо правильність розв’язку:

.

Таким чином, E_k=31; D_k=3031.

28.5 Особливості факторизації на основі загального «решета числового поля»

У п.9.2.1 були названі основні етапи факторизації на основі використання загального решета числового поля. В узагальненому вигляді їх можна подати таким чином [423–425]:

- вибирання поліномів відповідних степенів;

- просіювання з відбиранням позитивних даних;

- обробка даних з розв’язанням задачі лінійної алгебри;

- знаходження нетривіальних рішень.

Метод загального решета числового поля (NSF number field sieve) [424] дозволяє факторизувати модуль RSA перетворення зі складністю (асимптотичною):

L_N (γ, = exp (^γ Ln (Ln (N)) ^{1- γ)}, (9.14)

де γ=1/3, а (64/9^)(1/3) Т)(приблизно 1.923) параметри методу.

Для методу спеціального решета числового поля (SNSF – special number field sieve) [424] параметри методу дорівнюють

γ=1/3, а (32/9)^1/3 (приблизно 1,526), (9.15)

тобто метод спеціального решета числового поля є менш складним (більш швидкодіючим).

Взагалі ідея методу загального решета числового поля належить Джону Полларду, який у 1988 році запропонував просіювання виконувати не у кільці цілих чисел, як це робиться в квадратичному решеті, а в алгебраїчному полі [423, 424]. Спочатку метод можна було використовувати для факторизації тільки чисел спеціального вигляду 2ⁿ +(-)n. Тому метод отримав назву «спеціального решета числового поля». Практична реалізація ідеї Полларда була здійснена в 1990 році, коли з його використанням було факторизовано число Ферма (2⁵¹²). Також були факторизовані деякі числа вигляду b^c +(-)1. У подальшому було запропоновано використовувати метод решета числового поля й для факторизації довільних цілих чисел. Була знайдена евристична оцінка його складності, яка визначалась у (9.14). Тобто множник був зменшений у порівнянні з квадратичним решетом з 1/2 до 1/3. Очевидно, найбільш детально метод решета числового поля викладено в книзі Брігса [424] та в російськомовному виданні в [425].

Розглянемо етапи базового методу решета числового поля, спираючись на [423–425].

Нехай n – непарне ціле число, яке необхідно факторизувати. Основна ідея Полларда полягає в тому, щоб замінити поліном 2-го степеня q(x) = (x +m)² – n, який використовувався у квадратичному решеті, на довільний поліном P_d(x) степеня d ≥ 3, який задовольняє умові P_d(m) = n для деякого цілого числа m. Далі, просіювання за множиною цілих чисел Z було замінене просіюванням в кільці Z(β), яке отримується приєднанням до кільця Z цілого алгебраїчного числа β, що є коренем полінома P_d(m). У порівнянні з квадратичним решетом, у решеті числового поля факторна база складається із простих елементів кільця алгебраїчних чисел.

Виграш при використанні решета числового поля полягає в тому, що умова P_d(m) = n для деякого цілого m, що накладається на поліном P_d(x), у порівнянні з коефіцієнтами, що використовуються у квадратичному решеті, може бути виконана при менших значеннях коефіцієнтів полінома P_d(x).

Метод загального решета числового поля може бути реалізований через виконання таких кроків [424–425].

1. Вибирається степінь незвідного полінома d ≥3. Можна взяти d = 2, але в цьому випадку у порівнянні з квадратичним решетом виграшу не буде.

2. Вибирається ціле число m – таке, що < m < , та розкладається число n за основою m, тобто подається у вигляді:

n = m^d + a_d-1 m^d-1 + …+a₀ (9.16)

3. Із розкладом (9.16) пов’язується незвідний поліном у кільці Z(x):

f₁(x) = x ^d+ a_d-1 x ^d-1 + …+a₀ (9.17)

4. Визначається поліном просіювання F₁(a, b) як однорідний поліном від двох змінних а та b:

F₁(a, b) = b ^d f₁(a/b)= a^d +a_d-1a^d-1b+ a_d-2a^d-2b² +…+a₀b^d (9.18)

Необхідно відмітити, що значення F₁(a,b) дорівнює нормі полінома a – b×x в алгебраїчному числовому полі Q [β], яке отримують доповненням поля раціональних чисел Q у загальному випадку комплексного кореня багаточлена f₁(x) [425]. При цьому властивості комутативності норми

Nr (h₁(x)× h₂(x)) = (Nr (h₁(x))×(Nr (h₂(x))) (9.19)

дозволяють замість розкладання багаточлена з кільця Z(β) виконати розкладання їх норм.

5. Визначається другий багаточлен

f₂(x) = x – m (9.20)

та відповідний йому однорідний багаточлен

F₂ (a, b) = а – b m. (9.21)

Головною вимогою при вибиранні пари багаточленів (f₁(x), f₂(x)) є виконання вимоги:

f₁ (m) = f₂ (m) (mod n), (9.22)

яка в нашому випадку, очевидно, виконується, оскільки перший багаточлен у точці m дорівнює n, а другий – нулю.

6. Вибирається два позитивних числа L₁ та L₂, що визначають деяку прямокутну область

SR = {1 ≤ b ≤ L₁, -L₂ ≤ a ≤ L₂}, (9.23)

яку називають областю просіювання.

7. Нехай β – корінь багаточлена f₁(x). Розглядається кільце багаточленів Z(β) (для формального описання алгоритму). Також визначимо алгебраїчну факторну базу FB₁, яка буде складатися з багаточленів першого порядку вигляду a – b×β з нормою, що є простим числом. Такі багаточлени є простими елементами, що не розкладаються, в кільці алгебраїчних цілих поля K = Q(β). Абсолютні величини норм багаточленів із факторної бази FB₁ обмежимо зверху деякою постійною В_1.

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

9. Визначається також невелика множина багаточленів першого порядку с – d×β, норма яких є простим числом. Позначимо цю множину як FB₃. Вона має задовільняти умові, що

FB ₁ ^ FB ₃ =

і називається факторною базою квадратичних характерів. Факторна база FB₃ необхідна на підсумковій стадії алгоритму для перевірки того факту, що знайдений у ході просіювання багаточлен є повним квадратом.

10. Далі для отримання гладких пар (а,b) множини М здійснюється просіювання багаточленів { a – b×β | (a,b) SR} згідно факторної бази FB₁, а також цілих чисел {a – b×m | (a,b) SR} згідно факторної бази FB₂. При цьому пара (a,b) називається гладкою, якщо НСД (a, b) = 1, а поліном a – b×β і число a – b×m розкладається по відповідним факторним базам FB₁ та FB₂. При цьому число гладких пар у множині М має бути більше загальної суми елементів усіх трьох баз щонайменше на 2 одиниці.

11. На цьому кроці шукається підмножина S ⊃M таке, що добуток усіх пар для H Z, а також

Для знаходження множини S, як і в методі квадратичного решета, складається система лінійних алгебраїчних рівнянь з коефіцієнтами із множини F₂ = {0, 1}, результатом розв’язання якої й будуть номери S.

12. Формується багаточлен

g (β) = (f₁^`(β))² (9.24)

де f₁´(x) – похідна багаточлена f₁(x).

13. Далі, якщо вся процедура виконана коректно, то багаточлен g(β) є повним квадратом у кільці поліномів Z(β). Знаходимо квадратні корені із багаточлена g(β) та цілого числа В², унаслідок чого знаходимо багаточлен та число В.

14. Замінюємо багаточлен на число . Відображення є кільцевим гомоморфізмом кільця алгебраїчних цілих чисел Z_к у кільце Z. Звідки отримаємо співвідношення:

A² = g(m)² =( = (f₁^`(β))² =

= (f₁^{`</sup>(m))<sup>2</sup> = (f<sub>1</sub><sup>`}(m))² (9.25)

Таким чином, визначивши B = f `(m) C, знайдемо пару цілих чисел (A,B), які задовольняють умові

А² = В² (mod n) (9.26)

На останок можна знайти дільник числа n, обчислюючи НСД (n, А +(-) В).

Читайте також:

1. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
2. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
3. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
4. Адаптовані й специфічні методи дослідження у журналістикознавстві
5. Адвокатура в Україні: основні завдання і функції
6. Адміністративні (прямі) методи регулювання.
7. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.
8. Адміністративні методи управління
9. Адміністративні, економічні й інституційні методи.
10. Адміністративно-правові (організаційно-адміністративні) методи мотивації
11. Адміністративно-правові методи забезпечення економічного механізму управління охороною довкілля
12. Аерометоди

Переглядів: 2072