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