Проблема дискретного логарифмування
Проблема дискретного логарифмування
В пошуках криптографічних алгоритмів з відкритим розповсюдженням ключів з експоненціальною складністю криптоаналізу спеціалісти зупинилися на криптографічних перетвореннях, що виконуються в групі точок ЕК.
Відповідно до прогнозів ці перетворення ще довго забезпечуватимуть необхідний рівень стійкості. Розглянемо основні задачі криптоаналізу для систем, в яких перетворення здійснюються в групі точок ЕК, методи їх розв'язання та дамо оцінку стійкості для відомих нам методів криптоаналізу.
Під час аналізу стійкості необхідно розглянути дві проблеми стійкості – розв’язання задачі дискретного логарифму та задачі Діффі-Хеллмана.
Проблема дискретного логарифму
формується у наступному вигляді. Нехай
задано точку
на еліптичній кривій
,
де
(
просте
число) або
(
просте
число,
натуральне,
).
Відомо також значення відкритого ключа
,
причому
.
(1)
Необхідно знайти конфіденційний
(особистий ) ключ
.
Проблема Діффі – Хеллмана
формується у наступному вигляді. Нехай
дано ЕК
,
відомо значення точки
,
а також відкритий ключ
.
Необхідно знайти загальний секрет
,
(2)
де
та
– особисті ключі відповідно першого
та другого користувачів.
Насьогодні для аналізу
стійкості та проведення криптоаналізу
знайшли розповсюдження декілька методів
Полларда
та оптимальний
.
Поллард запропонував замість
детерміністського псевдоймовірнісний
алгоритм розв’язання
в полі
.
Це дозволило істотно знизити вимоги до обсягу пам'яті при практично тій же стійкості алгоритму. Ідея методу заснована на випадковому пошуку двох співпадаючих точок серед точок криптосистеми.
У теорії ймовірностей добре
відомі задачі про випадкові блукання.
Одна із задач ставиться так. Є
ящиків і
куль, які випадково розміщені по ящиках.
Процедура закінчується при
першому влученні кулі у вже зайнятий
ящик. Потрібно визначити медіану
розподілу ймовірностей
Більш простою моделлю є задача
про співпадаючі дні народження. Якщо
число днів у році, то скільки чоловік
з рівноймовірними днями народження в
році потрібно відібрати, щоб з імовірністю
дні народження хоча б двох чоловік
збіглися
Очевидно, що ймовірність такої події дорівнює
При
неважко отримати наближене значення
цієї імовірності
Приймаючи
,
отримаємо оцінку числа
.
Інакше кажучи, щоб при випадковому
переборі великої множини із
чисел з імовірністю 50% двічі з'явилося
те саме число, буде потрібно в середньому
порядку
спроб. Збіг елементів або точок в аналізі
прийнято називати колізією. Нехай
,
де генератор
криптосистеми має великий простий
порядок
.
Алгоритм
-
методу в застосуванні до еліптичних
кривих полягає в послідовному обчисленні
точок
де
якась міра координати
точки
три рівноймовірні області, у які може
потрапити ця міра. Виберемо випадкові
значення
й визначимо початкову точку як
Ітераційна послідовність обчислень
дає послідовність
,
таку що
На кожному кроці обчислене
значення
порівнюється з попереднім аж до збігу
(колізії)
або
.
Алгоритм разом з колізією дозволяє скласти рівняння
з якого визначається значення дискретного логарифма
.
Походження терміна (-метод)
пов'язане із графічною інтерпретацією
алгоритму, зображеної на рис. 1. При
замиканні петлі виникає періодичний
цикл.
Це обумовлено детермінованістю алгоритму. Його називають імовірнісним лише у зв'язку з непередбачуваністю шляху, за яким виконується одне із трьох обчислень.
Q>0 >Q>1 >Q>2 >Q>m>> >
Q>m>>+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)
Під час розв’язання задач
важливо успішно вибрати
.
Значення
рекомендується вибирати у вигляді
також можна вибрати як
де