главнаяреклама на сайтезаработоксотрудничество Библиотека Revolution
 
 
Сколько стоит заказать работу?   Искать с помощью Google и Яндекса
 



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

Криптографічні перетворення, що виконуються в групі точок ЕК. Проблема дискретного логарифму. Декілька методів, що використовуються для аналізу стійкості і проведення криптоаналізу. Опис та розв’язання логарифму методом Флойда, методом Полларда.

Рубрика: Математика
Вид: контрольная работа
Язык: украинский
Дата добавления: 08.02.2011
Размер файла: 98,1 K

Полная информация о работе Полная информация о работе
Скачать работу можно здесь Скачать работу можно здесь

рекомендуем


Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже.

Название работы:
E-mail (не обязательно):
Ваше имя или ник:
Файл:


Cтуденты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны

Подобные работы


1. Методи вирішення проблем дискретного логарифмування
Огляд проблеми дискретного логарифмування в групі точок еліптичної кривої. Сутність та сфера використання методу Поліга-Хелмана. Особливості використання методу ділення точок на два. Можливі підходи і приклади розв’язання задач дискретного логарифмування.
реферат [112,8 K], добавлена 09.02.2011

2. Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої
Використання методу Полларда для вирішення проблеми дискретного логарифмування, його складність і час обчислення рішення ECDLP. Аномальні криві й криві над розширеннями малого поля. MOV-атака та суперсингулярні криві над полем F. Метод спуску Вейля.
реферат [269,5 K], добавлена 21.02.2011

3. Розв'язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплекс-методом
Розв'язання графічним методом математичної моделі задачі з організації випуску продукції. Розв'язання транспортної задачі методом потенціалів. Знаходження умовних екстремумів функцій методом множників Лагранжа. Розв'язання задач симплекс-методом.
контрольная работа [48,5 K], добавлена 16.07.2010

4. Розв’язання системи лінійних алгебраїчних рівнянь
Розв’язання систем лінійних рівнянь методом Жордана-Гауса. Еквівалентні перетворення системи, їх виконання як елемент методів розв’язування системи рівнянь. Базисні та вільні змінні. Лінійна та фундаментальна комбінації розв’язків, таблиці коефіцієнтів.
контрольная работа [170,2 K], добавлена 16.05.2010

5. Елементи інформаційних технологій в математичному програмуванні
Розв'язання завдання графічним способом. Зображення розв'язку системи нерівностей, визначення досягнення максимуму та мінімуму функції. Розв'язання транспортної задачі методом потенціалів та симплекс-методом, формування оціночної матриці з елементів.
задача [134,9 K], добавлена 31.05.2010

6. Інтегральні перетворення Лапласа
Означення та властивості перетворення Лапласа, приклади розв'язання базових задач. Встановлення відповідності між двома точками за допомогою оператора. Застосування операційного методу математичного аналізу, проведення дій над логарифмами та числами.
реферат [217,2 K], добавлена 20.12.2010

7. Розв'язання рівнянь методом оберненої матриці та методом Гауса
Запис системи рівнянь та їх розв'язання за допомогою методів оберненої матриці та Гауса. Поняття вектора-стовпця з невідомих та вільних членів. Пошук оберненої матриці до даної. Послідовне виключення невідомих за допомогою елементарних перетворень.
контрольная работа [115,2 K], добавлена 16.07.2010

8. Будування математичної моделі економічної задачі і розв'язання її за допомогою графічного метода, методів Жордана-Гаусса, потенціалу та симплекс-метода
Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлена 09.11.2009

9. Аналітична геометрія
Розв’язання системи рівнянь методом Крамера, методом оберненої матриці та методом Гаусса. Розрахунок довжини ребра, кута між ребрами, рівняння висоти, рівняння площини грані і кута між ребром та гранню. Дослідження функції та побудува її графіку.
контрольная работа [397,0 K], добавлена 30.10.2011

10. Системи нелінійних рівнянь
Чисельні методи розв’язання систем нелінійних рівнянь: лінійні і нелінійні рівняння, метод простих ітерацій, метод Ньютона. Практичне використання методів та особливості розв’язання систем нелінійних рівнянь у пакеті Mathcad, Excel та на мові С++.
курсовая работа [2,0 M], добавлена 30.11.2010


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


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

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

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

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

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

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

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

. (1)

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

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

, (2)

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

.

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

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

Q0 Q1 Q2 Qm

Qm+1

Qm+s1

Рисунок 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/

... читать дальше >>>

Поcмотреть текст работы Поcмотреть полный текст
Скачать работу можно здесь Скачать работу "Проблема дискретного логарифмування" можно здесь
Сколько стоит?

Рекомендуем!

база знанийглобальная сеть рефератов