МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Основні методи факторизації 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 (крива ρ-Полларда).
Рис. 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, x3 – x4 = |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=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, А +(-) В). Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|