Рефетека.ру / Математика

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


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


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

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

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

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


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


Необхідно знайти конфіденційний (особистий ) ключ Проблема дискретного логарифмування.

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


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


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

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

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

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

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

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

Більш простою моделлю є задача про співпадаючі дні народження. Якщо Проблема дискретного логарифмування - число днів у році, то скільки чоловік Проблема дискретного логарифмування з рівноймовірними днями народження в році потрібно відібрати, щоб з імовірністю Проблема дискретного логарифмування дні народження хоча б двох чоловік збіглися?

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


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


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


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


Приймаючи Проблема дискретного логарифмування, отримаємо оцінку числа Проблема дискретного логарифмування. Інакше кажучи, щоб при випадковому переборі великої множини із Проблема дискретного логарифмування чисел з імовірністю 50% двічі з'явилося те саме число, буде потрібно в середньому порядку Проблема дискретного логарифмування спроб. Збіг елементів або точок в аналізі прийнято називати колізією. Нехай Проблема дискретного логарифмування, де генератор Проблема дискретного логарифмування криптосистеми має великий простий порядок Проблема дискретного логарифмування. Алгоритм Проблема дискретного логарифмування- методу в застосуванні до еліптичних кривих полягає в послідовному обчисленні точок


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


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


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


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


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


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

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


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


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


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

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


Q0 Q1 Q2 Qm


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

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

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

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


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

Проблема дискретного логарифмування 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)

Під час розв’язання задач важливо успішно вибрати Проблема дискретного логарифмування. Значення Проблема дискретного логарифмування рекомендується вибирати у вигляді


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


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


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


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

Размещено на

Рефетека ру refoteka@gmail.com