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

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

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


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


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


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


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


. (1)


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


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


, (2)


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


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


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


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


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


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


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


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



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



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



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



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


.


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



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


.


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


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


Q
0
Q
1
Q
2
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)


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



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



де


Размещено на

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:1405
Символов:10748
Размер:20.99 Кб.