Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

(9.3)

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

 

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

(9.4)

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

Х.Y

 


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

 

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

НСД (9.5)

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

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

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

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

,

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

,

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

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

.

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

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

,

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

,

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

,

x6 = 91.

Для х6 маємо НСД (х6х5, 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) =xi = x2 + 1(mod N), тобто прийнявши, що .

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

x1 = (172 + 1)mod 209 = 81,

x2 = (812 + 1)mod 209 = 83,

 

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

x3 = (832 + 1)mod 209 = 202,

x4 = (2022 + 1)mod 209 = 50,

x3x4 = |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. Необхідно знайти особистий ключ отримувача Dk, з використанням якого можна здійснити розшифрування повідомлення М, якщо застосовується RSA перетворення.

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

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

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

.

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

.

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

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

.

Знаходимо

.

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

Таблиця 9.4

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

x   Z2mod3599 лишок

 

Беремо рядки зі значеннями 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;

;

;

;

;

.

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

.

Таким чином, Ek=31; Dk=3031.

 

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

 

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

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

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

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

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

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

LN (γ, = 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]. Спочатку метод можна було використовувати для факторизації тільки чисел спеціального вигляду 2n +(-)n. Тому метод отримав назву «спеціального решета числового поля». Практична реалізація ідеї Полларда була здійснена в 1990 році, коли з його використанням було факторизовано число Ферма (2512). Також були факторизовані деякі числа вигляду bc +(-)1. У подальшому було запропоновано використовувати метод решета числового поля й для факторизації довільних цілих чисел. Була знайдена евристична оцінка його складності, яка визначалась у (9.14). Тобто множник був зменшений у порівнянні з квадратичним решетом з 1/2 до 1/3. Очевидно, найбільш детально метод решета числового поля викладено в книзі Брігса [424] та в російськомовному виданні в [425].

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

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

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

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

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

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

n = md + ad-1 md-1 + …+a0 (9.16)

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

f1(x) = x d+ ad-1 x d-1 + …+a0 (9.17)

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

F1(a, b) = b d f1(a/b)= ad +ad-1ad-1b+ ad-2ad-2b2 +…+a0bd (9.18)

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

Nr (h1(x)× h2(x)) = (Nr (h1(x))×(Nr (h2(x))) (9.19)

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

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

f2(x) = x – m (9.20)

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

F2 (a, b) = а – b m. (9.21)

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

f1 (m) = f2 (m) (mod n), (9.22)

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

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

SR = {1 ≤ b ≤ L1, -L2 ≤ a ≤ L2}, (9.23)

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

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

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

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

FB 1 ^ FB 3 =

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

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

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

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

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

g (β) = (f1`(β))2 (9.24)

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

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

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

A2 = g(m)2 =( = (f1`(β))2 =

= (f1`(m))2 = (f1`(m))2 (9.25)

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

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

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


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

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




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

<== попередня сторінка | наступна сторінка ==>
Методика криптоаналізу RSA | Поліноміальний метод факторизації Чалмерса

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.033 сек.