Лекція 20

Складність методів розв’язання проблеми дискретного логарифмування в групі точок еліптичної кривої. Метод ділення точок на дві, MOV атака, метод спуска Вейля.

План

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

2. MOV атака.

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

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

. (20.1)

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

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

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

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

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

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

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

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

O

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- атака

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

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

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

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

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

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

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

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

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

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

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

2. 

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

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

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

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

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

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

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

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

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

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

1. У чому суть - атаки, яка заснована на методі спуска Вейля

2. Яка сутність MOV атаки

3. Провести тестування кривих , та над , порядку та на стійкість до MOV атаки ( з верхньою межею ).

ПЕРЕЛІК ПОСИЛАНЬ

1. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии.- М. МЦНМО,2002.

2. А. Бессалов, А. Телиженко. Криптосистемы на эллиптических кривых. Киев,  Політехніка  , 2004, 223 с.

3. Вербицький О.В. Вступ до криптології. Львів. ВНТЛ. 1998. Розділ І,ІІ. с. 12-46.

4. А.В. Бабиш, Г.П. Шанкин Криптография.-М.СОЛОН-Р,2002.

5. Анин Б. Защита компьютерной інформации Изд-во БХВ - Санкт-Петербург, 2000. 384 стр.

6. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях.- М.: КУДИЦ-ОБРАЗ,2001.

7. Ященко В.В. Введение в криптографию. Изд-во МЦНМО-Санкт-Петербург

. 8. Горбенко І.Д. Криптографічний захист інформації .Навч. посібник Харків, ХНУРЕ, 2004 р.

9. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ – Москва ,  Тріумф , 2002.

136