Проблема дискретного логарифмування
В пошуках криптографічних алгоритмів з відкритим розповсюдженням ключів з експоненціальною складністю криптоаналізу спеціалісти зупинилися на криптографічних перетвореннях, що виконуються в групі точок ЕК.
Відповідно до прогнозів ці перетворення ще довго забезпечуватимуть необхідний рівень стійкості. Розглянемо основні задачі криптоаналізу для систем, в яких перетворення здійснюються в групі точок ЕК, методи їх розв'язання та дамо оцінку стійкості для відомих нам методів криптоаналізу.
Під час аналізу стійкості необхідно розглянути дві проблеми стійкості – розв’язання задачі дискретного логарифму та задачі Діффі-Хеллмана.
Проблема дискретного логарифму формується у наступному вигляді. Нехай задано точку  на еліптичній кривій  , де  ( просте число) або  (просте число,  натуральне,  ). Відомо також значення відкритого ключа  , причому
 . (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)
Під час розв’язання задач важливо успішно вибрати  . Значення рекомендується вибирати у вигляді
також можна вибрати як
де 
Размещено на
|
