ють методом Великого І малих кроків (Giant step-Baby step). Маркери - це Giant step. Номером ціх точок з їх-координатами зберігаються в пам'яті. Baby step - це послідовні додавання точок после чего обчіслені-координат та порівняюються з координатами маркерів. При збігу координат отрімуємо, Звідки візначається Шуканов значення. Метод Шенкса є детерміністськім. p> Обчислювальна складність методу оцінюється як середнє число малих кроків. Основний недолік методу - надмірній об'єм необхідної пам'яті, пропорційній.
Крім того, на шкірному кроці порівняння координат здійснюється за всех точках, что зберігаються в пам'яті. Для завдань реального кріптоаналізу метод не нашел! застосування. Однак, часто метод Шенкса приводитися як теоретична основа для других, більш практичних методів решение.
3. Метод ділення точок на два (продовження)
ВІН Заснований на вікорістанні точок
З максимальним порядком, (коефіцієнт крівої a = 0). Задам рекурентной функцію ділення-Відрахування
(1)
Оскількі Кожне ділення Дає Дві точки, повна процедура утворює дерево розв'язків Із Галузії (- число віднімань точки). У ідеальному випадка, при правильному віборі точок ділення, одна з Галузії найбільш коротким Шляхом веде до точки, а Інша -. При цьом двійковій запису алгоритмів ділення (0) або Відрахування - ділення (1) Дає Шуканов число або. Для цього буде нужно НЕ больше ділень. Зрозуміло, при Випадкове віборі точок ділення ймовірність знаходження таких Галузії мізерно мала.
Точки групи < P > ЗРУЧНИЙ податі у вігляді еквідістантніх точок кола, починаючі відлік від точки ПРО, розташованої ліворуч за годінніковою стрілкою (рис. 2). Будь-якій парній точці групи < P > В® відповідають Дві точки ділення ї, розташовані на одній діагоналі кола ї пов'язані співвідношенням Із точкою іншого порядку. Значення точок, верхнього півкола можна розглядаті як додатні, а Нижнього півкола - як від'ємні. Координати кожної Такої парі збігаються, а. У процедурі ділення, что прагнем до точки, можна ігноруваті знак точки, зазначімо, что є позбав - координата точки. Назвемо "правильною" точкою ділення точку лівого півкола (на рис 2 - крапка). Послідовний вибір "правильних" точок ділення в процедурі веде до точки ї, відповідно до розв'язання. Злом криптосистеме, у такий способ зводіться до Вирішення еквівалентніх проблем:
- визначення, у якому пів кола групи < P > перебуває Деяка точка цієї групи;
- визначення співвідношення (больше - менше) между двома довільнімі
точками ї групи < P >;
- визначення парності (непарності) числа для точки;
- чі віконується редукція за модулем при подвоєнні довільної точки Із групи порядку?
Доки відповісті на ці запитання НЕ вдається ECC залішається стійкою криптосистемами з експоненційною складністю розв'язання. Для кріптоаналізу зовсім необов'язково прийти до точки або, Достатньо найти точку з-координати точки, что раніше зустрічалася в Цій процедурі, або будь-якої Іншої відомої точки групи < P >. У первом випадка решение при колізії близьким до - методом Полларда, у іншому - до методу Шенкса. p> Доцільно використовуват максимально можливіть кількість ІНФОРМАЦІЇ (передрозрахункі) з метою Збільшення ймовірності колізій, однак це веде до Збільшення кількості перевірок и Розширення пам'яті.
крива поле дискретності логаріфмування атака
В
Малюнок 2 - геометричність Ілюстрація методу ділення точок крівої на два
В
Если в 1 Залишити позбав одну операцію ділення на два з Вибори точки Із групи, то ітераційна процедура ділення на два в залишковим підсумку такоже прізведе до точки (або Іншої відомої точки), ЯКЩО 2 є прімітівнім елементом поля. Послідовне ділення точок на два вімагає в НБ ЛИШЕ ОДНЕ множення в полі на шкірному кроці, Другие Операції практично НЕ вімагають витрат. При цьом, імовірно, можна досягті максімальної Швидкості кріптоаналізу. Цею метод, однак, рівносільній ПОВНЕ перебору всех точок. Більш доцільнім, Можливо, є випадкове поиск на колізій Зі складністю.
В
4. Аномальні кріві ї кріві над розширеного малого поля
Аномальні кріві над розширеного поля (кріві Коблиці) увазі, мают Особливості структурованих групи E , что дозволяють Зменшити в раз об'єм аналізованіх точок крівої (у порівнянні Із Груп Загальної структурі) І, відповідно, у раз Обчислювальна складність поиска колізій. Це пов'язано з виникненням класів еквівалентності точок крівої, породжуваніх послідовнім піднесенням у квадрат координат віхідної точки.
Позначімо функцію при цьом Для будь-якої точки порядком крівої над полем візначається ендоморфізм Фробеніуса (Відображення поля в полі), Який задовольняє характеристичностью рівняння
В
Тут Операція додавання Визначи як додавання ...
