Xreferat.com » Рефераты по математике » Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

групі точок еліптичної кривої" width="69" height="29" align="BOTTOM" border="0" />

359 354

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

431 426

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої


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

Операція експоненціювання Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої у мультиплікативній групі найбільш ефективно здійснюється методом послідовного піднесення до квадрата. Для цього число Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої подається у двійковій системі числення


Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої


як Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої-розрядне двійкове число Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Наприклад, мінімальним 5-розрядним числом (з 1 у старшому розряді) є двійкове число Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (рівне 16 у десятковій системі), а максимальним – число 11111 (рівне 31 у десятковій системі). Тоді експоненціювання елемента Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої зводиться до послідовного піднесення до квадрата і множення на Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (останнє за наявності 1 у двійковому записі від старшого розряду до молодшого):


Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої


У першому випадку виконується 4 операції множення, у другому 8-множень. У загальному випадку експоненціювання у двійкову Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої-розрядний степінь цим методом здійснюється за допомогою від Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої до Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої операцій множення за модулем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Об'єм обчислень пропорційний розрядності числа Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Така обчислювальна складність називається поліноміальною Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої а - коефіцієнт пропорційності).

Зворотна функція дискретного логарифмування Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої у найгіршому разі може зажадати перебору до Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої значень, при цьому говорять про експонентну складність обчислень Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Взагалі кажучи, поняття обчислювальної складності визначається через співвідношення вхідного й вихідного об'ємів даних деякого обчислювального алгоритму. Алгоритми поліноміального часу (швидкі алгоритми) характеризуються лінійним співвідношенням об'ємів даних на виході й вході процесора, а алгоритми експонентного часу (повільні), відповідно, експонентним. Зі збільшенням об'єму вхідних даних експонентна складність веде до практично нереалізованих обчислювальних витрат.

Сьогодні відомі досить ефективні субекспоненційні методи рішення DLP над скінченними полями. Це пов'язано з тим, що елемент поля Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої - ціле число, яке можна факторизувати у вигляді добутку ступенів простих чисел. Це затребувано з метою безпеки істотно збільшити розміри поля для криптосистем Діффі-Хеллмана й Ель-Гамала (до тисяч біт). З іншого боку, точку еліптичної кривої Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої факторизувати на зразок цілого числа не вдається. Тому для ЕСС поки не відомі методи розв’язання Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, більш ефективні, ніж класичні методи з експонентною складністю обчислень. Цим і пояснюється високий рівень безпеки криптосистем на еліптичних кривих.

Криптоатаки на Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої прийнято розділяти на дві групи: атаки на загальну структуру й атаки ізоморфізму. До першого звичайно відносять:

– метод Шенкса( Shenks Method- Giant Step-Baby step);

– Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої методи Полларда (Pollardўs Method);

– метод Поліга- Хеллмана (Pohlig-Hellman Method);

– метод обчислення степенів (Index Calculus Method).

Ці методи застосовні для будь-якої скінченної групи, у тому числі й для еліптичної кривої (крім останнього). Атаки ізоморфізму специфічні для ECC. Серед них найбільш відомі:

– атака Менезиса, Окамото й Ванстоуна, або MOV- атака;

– ізоморфізм Семаєва;

– метод спуску Вейля й ін.

Атаки ізоморфізму базуються на перетвореннях, що переводять абелеву групу точок Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої в елементи мультиплікативної групи поля. Оскільки, рішення Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої у поле набагато простіше, ніж на еліптичній кривій (при порівнянних порядках), то знаходження ізоморфізму між двома групами істотно знижує безпека ЕСС. Поки відомі кілька класів криптографічно слабких кривих, для яких ці атаки успішні.


2. Метод Шенкса


Прямий метод розрахунку дискретного логарифма може використати два варіанти: Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої- кратне додавання точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої до збігу із точкою Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (шлях від точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої до точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої) або шлях від точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої до точкиСкладність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. У найгіршому випадку для визначення числа Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої із точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої може знадобитися до Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої додавань точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої( при Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої маємо множину зворотних за знаком точок, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої- координати яких уже відомі). Обчислювальна складність безпосереднього розрахунку дискретного логарифма оцінюється числом операцій Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Щоб скоротити шлях до збігу (колізії) з відомою точкою, природно на всьому шляху поставити маркери Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, координати яких визначено на етапі попередніх обчислень. Рухаючись від точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої до найближчого маркера, ми істотно скорочуємо зону пошуку (рис 1). Виникає лише питання, як розставити маркери?


Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Рисунок 1 - Подання елементів циклічної групи точками на колі й інтервал аналізу за методом Шенкса


По суті введення маркерів - це обмін обчислень на пам'ять. Якщо об'єми цих ресурсів зробити рівними, то відстань між маркерами слід вибирати рівною Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої . Ця ідея запропонована Д.Шенксом.

Метод Шенкса часто називають методом великих і малих кроків (Giant step-Baby step). Маркери Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої - це Giant step. Номери Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої цих точок з їх Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої-координатами зберігаються в пам'яті. Baby step – це послідовні додавання точок Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої після чого обчислені Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої-координати порівняюються з координатами маркерів. При збігу координат отримуємо Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, звідки визначається шукане значення Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Метод Шенкса є детерміністським.

Обчислювальна складність методу Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої оцінюється як середнє число малих кроків. Основний недолік методу – надмірний об'єм необхідної пам'яті, пропорційний Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої.

Крім того, на кожному кроці порівняння координат здійснюється по всіх точках, що зберігаються в пам'яті. Для задач реального криптоаналізу метод не знайшов застосування. Однак, часто метод Шенкса приводиться як теоретична основа для інших, більш практичних методів рішення Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої.

Метод ділення точок на два ( продовження)


Він заснований на використанні точок <P> з максимальним порядком Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (коефіцієнт кривої a=0). Задамо рекурентну функцію ділення-відрахування


Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривоїСкладність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (1)


Оскільки кожне ділення дає дві точки, повна процедура утворює дерево розв’язків із Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої галузями (Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої - число віднімань точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої). В ідеальному випадку, при правильному виборі точок ділення, одна з галузей найбільш коротким шляхом веде до точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, а інша – Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. При цьому двійковий запис алгоритму ділення (0) або відрахування – ділення (1) дає шукане число Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої або Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Для цього буде потрібно не більше Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої ділень. Зрозуміло, при випадковому виборі точок ділення ймовірність знаходження таких галузей мізерно мала.

Точки групи <P> зручно подати у вигляді еквідистантних точок кола, починаючи відлік від точки ПРО, розташованої ліворуч за годинниковою стрілкою (рис. 2). Будь-якій парній точці групи <P> ® Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої відповідають дві точки ділення Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої й Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, розташовані на одній діагоналі кола й пов'язані співвідношенням Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої із точкою Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої другого порядку. Значення точок Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої верхнього півкола можна розглядати як додатні, а нижнього півкола Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої - як від’ємні. Координати Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої кожної такої пари збігаються, а Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. У процедурі ділення, що прагне до точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, можна ігнорувати знак точки, зазначимо, що є лише Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої- координата точки. Назвемо "правильною" точкою ділення точку лівого півкола (на рис 2 – точка Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої). Послідовний вибір "правильних" точок ділення в процедурі Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої веде до точки Складність методів вирішення проблеми
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: