Головна
Банківська справа  |  БЖД  |  Біографії  |  Біологія  |  Біохімія  |  Ботаніка та с/г  |  Будівництво  |  Військова кафедра  |  Географія  |  Геологія  |  Екологія  |  Економіка  |  Етика  |  Журналістика  |  Історія техніки  |  Історія  |  Комунікації  |  Кулінарія  |  Культурологія  |  Література  |  Маркетинг  |  Математика  |  Медицина  |  Менеджмент  |  Мистецтво  |  Моделювання  |  Музика  |  Наука і техніка  |  Педагогіка  |  Підприємництво  |  Політекономія  |  Промисловість  |  Психологія, педагогіка  |  Психологія  |  Радіоелектроніка  |  Реклама  |  Релігія  |  Різне  |  Сексологія  |  Соціологія  |  Спорт  |  Технологія  |  Транспорт  |  Фізика  |  Філософія  |  Фінанси  |  Фінансові науки  |  Хімія

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


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

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

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

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

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

. (1)

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

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

, (2)

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

.

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

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

 

Q0Q1Q2Qm

 


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)

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

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

де
Шляхи вдосконалення управління персоналом підприємства
Глава I Загальна характеристика організації 1 Характеристика організації ТОВ «Джесіка» зареєстровано розпорядженням голови Адміністрації Радянського району м Н.Новгорода №1157-Р 15.09.1992г. З 1992 по 1996 роки ТОВ «Джесіка» орендувало приміщення в Інституті ресурсозбереження та розміщувало

Соціально-економічний розвиток Забайкальського краю
ЗМІСТ ВСТУП 1. ХАРАКТЕРИСТИКА СОЦІАЛЬНО ЕКОНОМІЧНОГО РОЗВИТКУ Забайкальського краю (ОСНОВНІ ПАРАМЕТРИ) 1.1 Економічний потенціал регіону 1.2 Накопичений промисловий та науково-освітній потенціал 1.3 Соціальний розвиток 2. СТРАТЕГІЧНІ НАПРЯМКИ І АНАЛІЗ КОНКУРЕНТНИХ привілеїв РЕГІОНУ 2.1 Стратегічна

Вдосконалення організації роботи нагрівальних печей
Федеральне агентство з освіти Державна освітня установа Вищої професійної освіти "Сибірський державний індустріальний університет" Кафедра економіки та менеджменту Курсова науково-дослідна робота по курсу: "Управління виробництвом" "Удосконалення організації роботи

Ефективність використання оборотних коштів у сільськогосподарському виробництві
Міністерство сільського господарства РФ Федеральне державне освітній заклад Вищої професійної освіти "Бурятская державна сільськогосподарська академія ім. В.Р. Філіппова " Економічний факультет Кафедра економічної теорії Дипломна робота На тему: "Ефективність використання оборотних

Типологічна характеристика управління, його структура і функції
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ РЕФЕРАТ ТИПОЛОГІЧНА ХАРАКТЕРИСТИКА УПРАВЛІННЯ, ЙОГО СТРУКТУРА І ФУНКЦІЇ 2010 ЗМІСТ 1. Суб'єкт і об'єкт управління 2. Основні компоненти управлінської діяльності 3. Функції управління Література 1. Суб'єкт і об'єкт управління Розглянувши соціальну суть і

Техніко-економічне обґрунтування проектування стадії синтезу виробництва стиролу потужністю 190000 тонн на рік
Міністерство освіти і науки Російської Федерації Державна освітня установа Вищої професійної освіти «Кузбаський державний технічний університет» Кафедра галузевої економіки. Курсова робота по економіки та управління виробництвом. Тема: "Техніко-економічне обгрунтування проектування стадії

Основні конкуренції ринку
Федеральне агентство за освітою Федеральна державна освітня установа вищої професійної освіти «Чуваський держуніверситет ім. І.Н. Ульянова» Батиревський філія Кафедра соціально-економічних дисциплін Контрольна робота По дисципліні: «Ціноутворення» По темі: Основні конкуренції. Характерні риси

© 2014-2022  8ref.com - українські реферати