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