Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

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

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

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

,

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

.

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

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

.

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

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

Таблиця 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  мільйон інструкцій за секунду). Під однією операцією тут розуміють одне додавання точок кривої. Оцінки часу рішення за допомогою -методу Полларда залежно від розміру поля й порядку криптосистеми наведено в таблиці 2

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

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

Таблиця 2  Складність і час обчислення рішення 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- атака;

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

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

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

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

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

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

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

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

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

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

Метод ділення точок на два ( продовження)

Він заснований на використанні точок <P> з максимальним порядком , (коефіцієнт кривої a=0). Задамо рекурентну функцію ділення-відрахування

(1)

Оскільки кожне ділення дає дві точки, повна процедура утворює дерево розв’язків із галузями (  число віднімань точки ). В ідеальному випадку, при правильному виборі точок ділення, одна з галузей найбільш коротким шляхом веде до точки , а інша – . При цьому двійковий запис алгоритму ділення (0) або відрахування – ділення (1) дає шукане число або . Для цього буде потрібно не більше ділень. Зрозуміло, при випадковому виборі точок ділення ймовірність знаходження таких галузей мізерно мала.

Точки групи <P> зручно подати у вигляді еквідистантних точок кола, починаючи відлік від точки ПРО, розташованої ліворуч за годинниковою стрілкою (рис. 2). Будь-якій парній точці групи <P>  відповідають дві точки ділення й , розташовані на одній діагоналі кола й пов'язані співвідношенням із точкою другого порядку. Значення точок , верхнього півкола можна розглядати як додатні, а нижнього півкола  як від’ємні. Координати кожної такої пари збігаються, а . У процедурі ділення, що прагне до точки , можна ігнорувати знак точки, зазначимо, що є лише - координата точки. Назвемо "правильною" точкою ділення точку лівого півкола (на рис 2 – точка ). Послідовний вибір "правильних" точок ділення в процедурі веде до точки й, відповідно до розв’язання . Злом криптосистеми, у такий спосіб зводиться до вирішення еквівалентних проблем:

– визначення, у якому пів кола групи <P> перебуває деяка точка цієї групи;

– визначення співвідношення (більше - менше) між двома довільними
точками й групи <P>;

– визначення парності ( непарності) числа для точки ;

– чи виконується редукція за модулем при подвоєнні довільної точки із групи порядку ?

Доки відповісти на ці запитання не вдається ECC залишається стійкою криптосистемою з експоненційною складністю розв’язання . Для криптоаналізу зовсім необов'язково прийти до точки або , достатньо знайти точку з -координатою точки, що раніше зустрічалася в цій процедурі, або будь-якої іншої відомої точки групи <P>. У першому випадку рішення при колізії близько до - методу Полларда, у другому – до методу Шенкса.

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

крива поле дискретний логарифмування атака

Рисунок 2  Геометрична ілюстрація методу ділення точок кривої на два

Якщо в 1 залишити лише одну операцію ділення на два з вибором точки із групи , то ітераційна процедура ділення на два в остаточному підсумку також призведе до точки (або іншої відомої точки), якщо 2 є примітивним елементом поля . Послідовне ділення точок на два вимагає в НБ лише одне множення в полі на кожному кроці, інші операції практично не вимагають витрат. При цьому, імовірно, можна досягти максимальної швидкості криптоаналізу. Цей метод, однак, рівносильний повному перебору всіх точок. Більш доцільним, можливо, є випадковий пошук колізій зі складністю .

4. Аномальні криві й криві над розширеннями малого поля

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

Позначимо функцію при цьому Для будь-якої точки порядку кривої над полем визначається ендоморфізм Фробеніуса (відображення поля в поле), який задовольняє характеристичне рівняння

Тут операція додавання визначена як додавання в групі E, а параметр називають слідом ендоморфізма Фробеніуса. Зокрема, для кривої Коблиця з коефіцієнтами з поля й параметром маємо

Тому що функція не змінює порядку точки, справедлива рівність , при цьому , а характеристичне рівняння Фробеніуса приймає вигляд

Розв’язання цього квадратного рівняння в кільці дає значення параметра , що визначає всі точки класу еквівалентності

Через те, що їхні координати визначаються послідовним піднесенням у квадрат, простіше всього їх виразити в НБ, у якому їх -бітовий запис утворює циклічний код із слів для кожної координати. Такі точки називають помітними. Задача розв’язання , таким чином, зводиться до пошуку класу еквівалентності з точністю до циклічного зсуву, що практично не вимагає додаткових обчислень. Неважко переконатися, що для підгрупи точок цієї кривої порядку коренем рівняння

є значення , а класи еквівалентності містять точки

Для точок максимального порядку корінь рівняння

дорівнює Один із класів еквівалентності точок даного порядку включає точки . Їхні координати утворюються послідовним піднесенням у квадрат. Усього є 4 класи еквівалентності точок максимального порядку.

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

Аномальні криві над простим полем , визначаються як криві з порядком й, відповідно, слідом Фробеніуса . Такі криві виявилися криптографічно слабкими, тому що порядки групи й адитивної групи поля рівні, що дозволяє порівняно просто побудувати атаку ізоморфізму, що переводить точки кривої в елементи групи . Цей метод уперше був запропонований І. Семаєвим, а також незалежно авторами Т. Сатохом, К. Араки й Н. Смартом. Складність при цій атаці стає поліноміальною, що робить аномальні криві даного типу неприйнятними в криптографії.

5. - атака

Під час вивчення властивостей суперсингулярних кривих виявилося, що порядок групи над полем ділить порядок мультиплікативної групи розширень або . Це дозволяє побудувати ізоморфізм між елементами групи E й мультиплікативної групи розширеного поля, після чого розв’язувати більше просту задачу визначення дискретного логарифма в полі. Ця атака ізоморфізму заснована на використанні спарювання Вейля і була запропонована А. Менезисом , Т. Окамото й С. Ванстоном, у зв'язку із чим називається - атакою.

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

Таблиця 3  Порядки суперсингулярних кривих над полем при непарних степенях

Крива		Порядок
	Непарне

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

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

6. Метод спуску Вейля

Заснована на методі спуску Вейля атака називається - атакою.

Нехай несуперсингулярна крива визначена над композиційним полем з непростим розширенням. Позначимо ,, ( мале поле,  розширення поля ). Тоді

Припустимо, що виконується хоча б одна з умов

1.  непарне число

2. 

3. Тут  магічне число, певне в працях А Менезиса, М.Ку, Гаудрі, Хасе й Смарта. Воно визначає рід якоїсь гіпереліптичної кривої -атака пропонує використати метод спуску Вейля для зведення на кривій до якобіану гіпереліптичної кривої роду над полем

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

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

1. - метод Полларда зі складністю бітових операцій.

2. Метод Енге-Гаудрі, що має субекспоненційну обчислювальну складність

3. Алгоритм Гаудри, який оцінюється складністю

бітових операцій.

Алгоритм Гаудрі швидше, ніж алгоритм Полларда, якщо У зв'язку зі швидким зростанням співмножника цей алгоритм стає непрактичним при . У цьому випадку доцільно використати метод Енге-Гаудрі. Він вважається прийнятним при .

атака вважається успішною, якщо рід гіпереліптичної кривої малий настільки, що алгоритми 2 і 3 більш ефективні, ніж метод Полларда. Нехай, наприклад, крива визначена над полем й , , тоді . У випадку максимального значення величина , тому очікується, що при -атака для майже всіх кривих над полем буде успішною. При приходимо до якобіану ізоморфної кривої з експонентною складністю розв’язання .

Щоб уникнути атаки методом спуску Вейля, розширення поля слід вибирати простим. При цьому й , а рід гіпереліптичної кривої набагато перевищує граничне значення 1024. Практично у всіх сучасних стандартах у цьому зв'язку рекомендується степінь поля вибирати як просте число.