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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Основні методи факторизації 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. Аерометоди

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