Контрольная работа Проблема дискретного логарифмування

Работа добавлена на сайт bukvasha.net: 2015-10-25

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

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 23.11.2024

Проблема дискретного логарифмування

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

Відповідно до прогнозів ці перетворення ще довго забезпечуватимуть необхідний рівень стійкості. Розглянемо основні задачі криптоаналізу для систем, в яких перетворення здійснюються в групі точок ЕК, методи їх розв'язання та дамо оцінку стійкості для відомих нам методів криптоаналізу.

Під час аналізу стійкості необхідно розглянути дві проблеми стійкості – розв’язання задачі дискретного логарифму та задачі Діффі-Хеллмана.

Проблема дискретного логарифму формується у наступному вигляді. Нехай задано точку

на еліптичній кривій

, де

(

просте число) або

(

просте число,

натуральне,

). Відомо також значення відкритого ключа

, причому

. (1)
Необхідно знайти конфіденційний (особистий ) ключ

.

Проблема Діффі – Хеллмана формується у наступному вигляді. Нехай дано ЕК

, відомо значення точки

, а також відкритий ключ

. Необхідно знайти загальний секрет

, (2)
де

та

– особисті ключі відповідно першого та другого користувачів.

Насьогодні для аналізу стійкості та проведення криптоаналізу знайшли розповсюдження декілька методів Полларда -

та оптимальний

.

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

в полі

.

Це дозволило істотно знизити вимоги до обсягу пам'яті при практично тій же стійкості алгоритму. Ідея методу заснована на випадковому пошуку двох співпадаючих точок серед точок криптосистеми.

У теорії ймовірностей добре відомі задачі про випадкові блукання. Одна із задач ставиться так. Є

ящиків і

куль, які випадково розміщені по ящиках.

Процедура закінчується при першому влученні кулі у вже зайнятий ящик. Потрібно визначити медіану розподілу ймовірностей

Більш простою моделлю є задача про співпадаючі дні народження. Якщо

- число днів у році, то скільки чоловік

з рівноймовірними днями народження в році потрібно відібрати, щоб з імовірністю дні народження хоча б двох чоловік збіглися?

Очевидно, що ймовірність такої події дорівнює

При

неважко отримати наближене значення цієї імовірності

Приймаючи

, отримаємо оцінку числа

. Інакше кажучи, щоб при випадковому переборі великої множини із

чисел з імовірністю 50% двічі з'явилося те саме число, буде потрібно в середньому порядку

спроб. Збіг елементів або точок в аналізі прийнято називати колізією. Нехай

, де генератор

криптосистеми має великий простий порядок

. Алгоритм

- методу в застосуванні до еліптичних кривих полягає в послідовному обчисленні точок

де

- якась міра координати

точки

- три рівноймовірні області, у які може потрапити ця міра. Виберемо випадкові значення

й визначимо початкову точку як

Ітераційна послідовність обчислень дає послідовність

, таку що

На кожному кроці обчислене значення

порівнюється з попереднім аж до збігу (колізії)

або

.
Алгоритм разом з колізією дозволяє скласти рівняння

з якого визначається значення дискретного логарифма

.
Походження терміна (

-метод) пов'язане із графічною інтерпретацією алгоритму, зображеної на рис. 1. При замиканні петлі виникає періодичний цикл.

Це обумовлено детермінованістю алгоритму. Його називають імовірнісним лише у зв'язку з непередбачуваністю шляху, за яким виконується одне із трьох обчислень.

Q₀Q₁Q₂Q_m

Q_m₊₁

Qm+s-1
Рисунок 1 - Графічна інтерпретація

-методу Полларда
Реалізація методу пов'язана з нарощуванням пам'яті, у яку записуються

-координати точок, що

обчислюють. У міру збільшення порядку

криптосистеми він незабаром стає практично нереалізованим. Позбутися від цього недоліку вдається за допомогою методу Флойда. Ідея методу проста й елегантна.

На циферблаті секундна стрілка завжди обганяє хвилинну, а хвилинна - годинну. При влученні всередину петлі в

-методі Полларда якась точка

наздоганяє точку

(колізія

), що дає рішення ECDLP. У такий спосіб замість порівняння чергової обчисленої точки з усіма попередніми достатньо у пам'яті зберегти для порівняння лише дві точки:

.

Точка колізії при цьому зрушується усередину петлі на відстань, що не перевищує половини довжини петлі. Тим самим відбувається обмін необхідної пам'яті на час обчислень.

Кожен цикл у методі Флойда вимагає обчислення трьох точок відповідно до алгоритму й порівняння двох з них. Вихідні дані – точки

, обчислені в попередньому циклі. Тоді на їхній основі розраховуються точки

і рівняються

- координати першої й останньої точок. При їхньому збігу має місце колізія

, де знак визначається з порівняння

- координат обчислених точок.

Найпростіша ілюстрація цього методу - спрощений алгоритм із обчисленням

. Колізія на

-му циклі

відразу дає розв’язання дискретного логарифму

По суті це прямий метод визначення дискретного логарифму з експоненційною складністю

.

В іншому окремому випадку алгоритму маємо

Колізія на

-му кроці призведе до рівняння

або

Воно не має розв'язку

. Якщо модернізувати алгоритм так, що на кожній ітерації порівнювати точки

й генератор

, то при виконанні

можна отримати розв’язання

за умови, що 2 є примітивним елементом поля

. Цей метод також вимагає об'єму обчислень порядку

Розглянуті дві частки випадку оцінюються максимальною складністю у зв'язку з тим, що при переборі всіх точок криптосистеми колізія виникає лише один раз.

Перехід до псевдовипадкового алгоритму породжує множина можливих точок колізій, число яких оцінюється як

, а обчислювальна складність методу

-Полларда, застосованого до групи загальної структури, дорівнює

. Оскільки в групі точок EK зворотні точки визначаються досить просто, об'єм пошуку в просторі точок скорочується вдвічі, а обчислювальна складність зменшується в

раз і стає рівною

На практиці для виявлення колізій замість методу Флойда знайшла застосування його модифікація, запропонована Шнором і Ленстрой. У цієї модифікації пам'ять містить 8 осередків, зрушення вмісту яких здійснюється при

, де

- номери ітерацій в останньому й першому осередках відповідно. Отримано експериментальну оцінку складності цього методу для групи

Алгоритм

- методу Полларда з розбивкою на три області

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

рівноймовірних областей з вибором, наприклад, ітераційної функції

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

Очевидно колізію точок можна отримати й іншим шляхом, рухаючись із двох (або більше) різних точок

до збігу

. Ця ситуація відображується на рисунку 2. Даний метод одержання колізії зветься

-Методом Полларда. Походження терміна прийнято з рисунка.

Розглянемо

-метод Полларда на прикладі ЕК над простим полем Галуа

, тобто

криптографичний дискретний логарифм

(3)
Для всіх точок

задано операції додавання та подвоєння. Наприклад, якщо

, то

Рисунок 2 - Графічна інтерпретація

-методу Полларда
де

(4)
Для ЕК над полем

виду

причому

, то для двох точок

та

таких, що

виходить

(5)

примітивний поліном m-го степеня;

(6)
Для розв’язання задачі пошуку конфіденційного ключа

в порівнянні (1) розглянемо

метод Полларда над простимо полем

Нехай

– базова точка,

відкритий ключ, шукатимемо пари цілих

та

, таких що

(7)
Позначимо в загальному вигляді

(8)
Суть

-методу Полларда розв’язання порівняння (1) міститься в наступному. Знайдемо деяку функцію

, вибравши

де

порядок точки

на ЕК

(9)

Далі знайдемо

послідовність:

...,

для пар

, таких що:

(10)
Рекомендується в простих випадках (при відносно невеликих

) послідовність

розраховувати у вигляді:

(11)
При цьому

та

складають частини області

. Якщо область

рівномірно ділиться, то (8.11) має вигляд:

(12)
При побудові множини

пошук буде успішним, якщо ми знайдемо

що еквівалентно знаходженню

(13)
Зробивши прості перетворення, маємо:

(14)
і далі

(15)
З (1) та (15) випливає, що

(16)
Більш ефективним є розрахунок

з розбиванням інтервалу

на

інтервалів. Для реальних значень

рекомендується

. У цьому випадку замість (11) маємо

(17)
причому

та

є випадкові цілі із інтервалу

.

У випадку (17) розв'язок знаходиться як і раніше у вигляді (12), а потім (17). З урахуванням позначень в (17)

(18)
Успішне розв'язання задачі дискретного логарифму в групі точок ЕК вимагає

(19)
операцій на ЕК.

Із (18) та (19) випливає, що задача пошуку пар

та

може бути розпаралелено на

процесорів, тоді

. (20)

Розроблено методики та алгоритми, які дозволяють розв'язати задачу (1) зі складністю

(21)
а при розпаралелюванні на

процесорах складність визначається, як

. (22)

Під час розв’язання задач важливо успішно вибрати

. Значення

рекомендується вибирати у вигляді

також можна вибрати як

де

Размещено на http://www.allbest.ru/

Bukvasha