Лекція 18 Складність методів розв’язання проблеми дискретного логарифмування в групі точок еліптичної кривої. Метод Полларда ( продовження). Метод Шенкса. План

1. Метод Полларда ( продовження)

2. Метод Шенкса.

Методи Полларда.

Продовжуючи розгляд методу Полларда розв’язання проблеми дискретного логарифмування вирішимо наступну задачу.

Задача 1. Нехай точка належить ЕК

,

причому і , тобто

.

Відкритий ключ . Порядок точки , порядок ЕК , де -кофактор. Необхідно знайти відкритий ключ із порівняння

У нашому випадку

.

Розв'язання задачі. Використовуючи співвідношення, отримаємо

Результати розв'язку задачі наведено в таблиці 18.1.

Таблиця 18.1 - Результати розв'язку задачі 1

	1	0
	2	0
	3	0
	4	1

Виберемо як тоді належить , тому

.

Розв'язуємо це рівняння, використовуючи алгоритм Евкліда

Отже Таким чином,

У результаті маємо, що

Таким чином

Другий крок: Знаходимо

Мультипликативно зворотний елемент числу 2 у полі знаходимо з рівняння

дійсно

Таким чином,

Далі знаходимо

Таким чином, у таблиці мі знайшли, що

Знаходимо

Перевіряємо

Таким чином

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

де - випадкові цілі числа з інтервалу .

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

Стійкість заснована на складності розв’язання задачі дискретного логарифмування. У порівнянні з більше ранніми прототипами  криптосистемами Діффі-Хеллмана й Ель-Гамала  вони дають істотний виграш у криптостійкості, або практично на порядок дозволяють скоротити розмір поля при порівняній стійкості. Відомо, що порядку 160 біт порівнянний по безпеці з RSA і криптосистемою Eль-Гамала з розміром ключа 1024 біт, причому цей виграш прогресує зі збільшенням довжини ключа .

Щоб оцінити складність ( Elliptic Curve Discrete Logarithm Problem ), представимо на хвилину, що піщина з лінійним розміром 0,1 мм є однією з точок ЕСС. Якої величини буде планета, складена з таких піщин? Якщо  радіус планети в кілометрах, то й км. Це приблизно в раз перевищує радіус нашої планети. Серед цього вражаючого числа піщин потрібно знайти одну. Це й буде розв’язанням, порівнянним за складностю з для із числом точок порядку .

Практично обчислювальна складність виміряється в MIPS-роках ( MIPS – Million Instructions per Second  мільйон інструкцій у секунду). Під однією операцією тут розуміють одне додавання точок кривій. Оцінки часу розвязання за допомогою -методу Полларда залежно від розміру поля й порядку криптосистеми наведені в таблиці 18.2.

Проблема дискретного логарифмування на еліптичній кривій формулюється в такий спосіб відома точка G криптосистеми простого порядку й точка Необхідно знайти ціле число

Термінологія тут успадкована із класичної проблеми дискретного логарифмування ( ) у мультиплікативній групі поля криптосистеми розподілу ключів Діффі-Хеллмана, у якій однобічна функція експоненціювання елементу поля обчислюється швидко (у поліноміальному часі), а зворотна функція дискретного логарифмування  повільно (за експонційний час). Суть цієї проблеми для не міняється, якщо операцію множення замінити операцією додавання ( в адитивної групі точок ), при цьому експоненціювання переходить в -кратне додавання точок.

Таблиця 18.1  Складність і час обчислення розв’язання ECDLP за допомогою -методу Полларда залежно від порядку криптосистеми.

Розмір поля, біт	Порядок криптосистеми біт	Складність	Час обчислень -роки
163	160
191	186
239	234
359	354
431	426

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

Операція експоненціювання в мультиплікативній групі найбільше ефективно здійснюється методом послідовного піднесення у квадрат. Для цього число представляється у двійковій системі числення

як -розрядне двійкове число . Наприклад, мінімальним 5-розрядним числом (з 1 у старшому розряді) є двійкове число (рівне 16 у десятковій системі), а максимальним – число 11111 (рівне 31 у десятковій системі). Тоді експоненціювання елемента зводиться до послідовного піднесення у квадрат і множенню на ( останнє при наявності 1 у двійковому записі від старшого розряду до молодшого)

У першому випадку виконується 4 операції множення , у другому 8 множень. У загальному випадку експоненціювання у двійкову -розрядний степінь цим методом здійснюється за допомогою від до операцій множення за модулем . Об'єм обчислень пропорційний розрядності числа . Така обчислювальна складність називається поліноміальною а - коефіцієнт пропорційності).

Зворотна функція дискретного логарифмування в найгіршому випадку може зажадати перебору до значень, при цьому говорять про експонентну складність обчислень

Взагалі кажучи, поняття обчислювальної складності визначається через співвідношення вхідного й вихідного об'ємів даних деякого обчислювального алгоритму. Алгоритми поліноміального часу ( швидкі алгоритми ) характеризуються лінійним співвідношенням об'ємів даних на виході й вході процесора, а алгоритми експонентного часу ( повільні), відповідно, експонентним. Зі збільшенням об'єму вхідних даних експонентна складність веде до практично нереалізованих обчислювальних витрат.

Сьогодні відомі досить ефективні субекспоненційні методи розвязання DLP над скінченними полями. Це пов'язане з тим, що елемент поля  ціле число, яке можна факторизувати у вигляді добутку ступенів простих чисел. Це за жадано з метою безпеки істотно збільшити розміри поля для криптосистем Діффі-Хеллмана й Ель-Гамала (до тисяч біт). З іншого боку, точку еліптичній кривій факторизувати на зразок цілого числа не вдається. Тому для ЕСС поки не відомі методи розв’язання , більше ефективні, чим класичні методи з експонентною складністю обчислень. Цим і порозумівається високий рівень безпеки криптосистем на еліптичних кривих.

Криптоатаки на прийнято розділяти на дві групи :атаки на загальну структуру й атаки ізоморфізму. До першого звичайно відносять:

• метод Шенкса( Shenks Method- Giant Step-Baby step);

• методи Полларда (Pollards Method)

• метод Поліга- Хеллмана ( Pohlig-Hellman Method);

• метод обчислення степенів ( Index Calculus Method).

Ці методи застосовні для будь-якої скінченної групи, у тому числі й для еліптичній кривій ( крім останнього). Атаки ізоморфізму специфічні для ECC. Серед них найбільш відомі:

• атака Менезиса, Окамото й Ванстоуна, або MOV- атака;

• ізоморфізм Семаєва;

• метод спуска Вейля й ін.

Атаки ізоморфізму базуються на перетвореннях, що переводять абелеву групу точок в елементи мультиплікативної групи поля. Тому що розв’язання у поле набагато простіше, ніж на еліптичній кривій

( при порівнянних порядках), те знаходження ізоморфізму між двома групами істотно знижує безпека ЕСС. Поки відомі кілька класів криптографічно слабких кривих, для яких ці атаки успішні.

Метод Шенкса.

Прямий метод розрахунку дискретного логарифма може використати два варіанти - кратне додавання точки до збігу із точкою ( шлях від точки до точки ) або шлях від точки до точки . У найгіршому разі для визначення числа із точки може знадобитися до додавань точки ( при маємо множина зворотних за знаком точок, - координати яких уже відомі). Обчислювальна складність безпосереднього розрахунку дискретного логарифма оцінюється числом операцій . Щоб скоротити шлях до збігу (колізії) з відомою точкою, природно на всьому шляху поставити маркери , , координати яких визначені на етапі попередніх обчислень. Рухаючись від точки до найближчого маркера, ми істотно скорочуємо зону пошуку (рис 18.1). Виникає лише запитання, як розставити маркери?

2rG 3rG

rG

(i1) = rG

nG =O

D

Q = kG

irG

Рисунок 18.1  Подання елементів циклічної групи точками на

окружності й інтервал аналізу по методу Шенкса.

По суті введення маркерів  це обмін обчислень на пам'ять. Якщо об'єми цих ресурсів зробити рівними, то відстань між маркерами варто вибирати рівною . Ця ідея запропонована Д.Шенксом.

Метод Шенкса часто називають методом великих і малих кроків (Giant step-Baby step). Маркери  це Giant step. Номера цих точок з їх -координатами зберігаються в пам'яті. Baby step – це послідовні додавання точок після чого обчислені -координати порівняюються з координатами маркерів. При збігу координат отримуємо , звідки визначається шукане значення . Метод Шенкса є детерміністським.

Обчислювальна складність методу оцінюється як середнє число малих кроків . Основний недолік методу - надмірний об'єм необхідної пам'яті, пропорційний .

Крім того , на кожному кроці порівняння координат здійснюється по всім точках, що зберігаються в пам'яті. Для задач реального криптоанализа метод не знайшов застосування. Однак, часто метод Шенкса приводиться як теоретична основа для інших, більше практичних методів розв’язання .

Контрольні запитання та завдання

1. Знайти таємний ключ , якщо відомий відкритий ключ для кривої над простим полем , якщо точка порядку та . Розрахувати складність криптографічного перетворення.

2. Назвіть типи криптоатаналітичних атак на .

3. Яка сутність методу Шенкса розв’язання проблеми дискретного логарифмування в групі точок ЕК